ハッシュ テーブルを使用するよりも、自己均衡ツリー手法を使用してアイテムを保存する方が優先される理由を知りたいです。
ハッシュ テーブルは挿入順序を維持できないことがわかりましたが、リンク リストを常に使用して、挿入順序シーケンスを格納できます。
少数の値の場合、ハッシュ関数のコストが追加されることがわかりますが、ルックアップを高速化するために、ハッシュ関数をキーと一緒にいつでも保存できます。
ハッシュ テーブルは、赤黒ツリーの単純な実装よりも実装が難しいことは理解していますが、実際の実装では、問題を解決するために余計な努力をしたいとは思わないでしょうか?
ハッシュ テーブルでは衝突が発生するのは普通のことですが、ハッシュ テーブル自体にキーを保存できるようにするダブル ハッシュなどのオープン アドレッシング技術では、問題は有利にならないという効果にまで軽減されていません。そのような実装のための赤い黒い木に向かって？
実際のアプリケーション（ファイルシステムなど）で赤黒木を非常に実行可能なデータ構造にするハッシュテーブルの欠点を厳密に見逃しているかどうか、私は興味があります。
これが私が考えることができるものです：
ストレージの割り当ては、もう 1 つの考慮事項です。ハッシュ テーブルのすべてのバケットを埋めるたびに、新しいストレージを割り当てて、すべてを再ハッシュする必要があります。データのサイズが事前にわかっていれば、これを回避できます。一方、バランスの取れたツリーは、この問題にまったく悩まされません。
私の謙虚な意見では、自己平衡木は学術的なトピックとしてかなりうまく機能します。そして、私は「赤黒木の単純な実装」として認定できるものは何も知りません。
現実の世界では、メモリウォールにより、紙よりもはるかに効率が低下します。
これを念頭に置いて、ハッシュテーブルは、特にアカデミックスタイルを実践しない場合は、適切な代替手段です（テーブルサイズの制約を忘れて、テーブルのサイズ変更の問題とほとんどすべての衝突の問題を魔法のように解決します）。
一言で言えば：それをシンプルにしてください。それがあなたにとって簡単なら、それはあなたのコンピュータにとっても簡単です。
追加したいだけです：
バランスの取れた二分木では、データの種類に関係なく、データを取得する予測可能な時間 [log n] があります。多くの場合、アプリケーションの応答時間を見積もる上で、アプリケーションにとって重要になることがあります。[ハッシュ テーブルの応答時間は予測できない場合があります]。ほとんどの一般的なユースケースでは、メモリ内ルックアップのパフォーマンスの違いはほとんど問題にならず、システムのボトルネックは他の場所にあるため、n が小さいことを覚えておいてください。デバッグして分析します。
一般に、ツリーはハッシュ テーブルに比べてメモリ効率が高く、入力キーの分散や衝突の可能性などを分析することなく実装するのがはるかに簡単です。
私が考えることができるいくつかの理由：
ツリーは動的 (スペースの複雑さは N) ですが、ハッシュ テーブルは多くの場合、固定サイズの配列として実装されます。これは、K > N の場合、K サイズで初期化されることが多いことを意味します。 hashmap を使用すると、メモリを占有する 100 個の空のスロットが残っている可能性があります。これによる別の効果は次のとおりです。
配列ベースのハッシュ テーブルのサイズを大きくするとコストがかかります (O(N) 平均時間、O(N log N) 最悪の場合) が、ツリーは一定時間 (O(1)) + (挿入ポイントを見つける時間) で成長する可能性があります。 (O(log N))
自己均衡ツリーとハッシュマップの両方の最悪の場合の効率は、最良の最悪の場合 (ハッシュマップが衝突を処理すると仮定して) で O(log N) ですが、ハッシュマップはより優れた平均ケースのパフォーマンス (多くの場合 O に近い) を持つことができます。 (1))、一方、ツリーは定数 O(log N) を持ちます。これは、ハッシュマップが O(1) の挿入インデックスを見つけることができたとしても、ハッシュ衝突 (同じ配列インデックスへの複数の要素のハッシュ) を考慮する必要があるためです。ツリー (ハッシュマップの Java 実装など)、つまり、ハッシュマップ内の各要素は自己均衡ツリーとして実装でき、指定された配列セルにハッシュされたすべての要素を格納できます。