ハッシュ関数が適切に選択されていれば、ハッシュテーブルの挿入と検索の両方に O(1) の時間がかかることは誰もが知っています。では、二分探索木を使用する理由は何でしょうか? 完全なハッシュ関数を設計するのが難しかったという理由だけでしょうか?
ここで、どうやってこの質問を思い付くのですか？標準C++ STL にはとsetがmapあり、バイナリ検索ツリーで実装されていますが、ハッシュはありません (非標準の , については話していませんhash_set) hash_map。一方、Ruby にはHash. この違いの背後にある合理性を理解したいと思います。
ツリーは順序通りのトラバーションを可能にします。
ハッシュ テーブルの最悪の場合のパフォーマンスは O(N) (1 つのバケットを介した線形検索) であり、二分検索は O(log N) によって制限されます。
注意: これには、ツリーのバランスが取れている必要があります。そのため、典型的な実装では、赤黒ツリーなどの自己バランス ツリーが使用されます。
このような劣化は起こりそうにありませんが、不可能ではなく、適切なハッシュ関数を選択する能力と実際のデータの分布に大きく依存します。
ツリーの実装も必要なサイズまで自明に成長しますが、ハッシュマップはいっぱいになると劣化し始めます (ほとんどの実装では、バケットの約 70% がいっぱいになると言われています)。テーブル全体を再ハッシュするか (これもリアルタイム アプリには不向きです)、新しいテーブルに段階的に移動する必要がありますが、これは単純な実装ではありません。
最終的に、STL はおそらく 1 つの「ベース」コンテナー テンプレートであるツリーを使用して、実装がさらに複雑になるのを回避しました。
peterchen の回答を追加すると、ハッシュ構造は理論的には挿入と削除が高速ですが、実際のデータ、選択したハッシュ関数、およびデータの量に大きく依存します。
最良のケースと最悪のケースの間で大きなパフォーマンスのばらつきがあるため、汎用構造には適していません。一方、二分木は、使用されるデータの量/タイプに関係なく、より予測可能ですが、最良のシナリオでは効率が低下します。
ハッシュテーブルはより複雑であるため、STL は最初はコンテナー間にハッシュテーブルを含めませんでした。ハッシュ関数などは言うまでもなく、オープンアドレス指定とクローズドアドレス指定のどちらかを選択する必要があります。それがすぐに標準に受け入れられるように、それを進めました。
一方、ツリーは比較的単純です。これらはメモリ内のデータ構造であるため、B ツリーの代わりにバイナリ ツリーを使用できることは既に知られていました。次に、AVL ツリーと RB ツリーのどちらかを選択しました。RB ツリーは、私がコメントする立場にない優れたパフォーマンス特性のために選択される傾向がありますが、両方の構造 ( AVLとRB ) に関するウィキペディアの記事では、比較的詳細に説明されています。
それ以外の場合、ツリーとハッシュ テーブルは別の用途に適しています。高速な挿入または検索が必要で、それらが格納される順序を気にすることができない場合は、ハッシュ テーブルが適しています。順序付けの特性と、挿入と取得に対する強力な保証が必要な場合は、バイナリ ツリーが適しています。もう 1 つの優れた経験則は、プロファイルを作成することです。どちらを使用してもほとんどの場合はインターフェイス互換であるため、プロファイリングしてどちらがパフォーマンスを向上させるかを確認することも役立ちます。
二分探索木のデータに順番にアクセスできます。
ツリーを使用するには、ツリー内のアイテムを並べ替える方法が必要です。ハッシュ テーブルを使用するには、ハッシュ テーブル内の項目のハッシュ値を計算する関数が必要です。
興味深いことに、.NET フレームワークでは、GetHashCodeすべてのオブジェクトをハッシュ テーブルに格納できるようにする関数を実装 (または継承) するために、すべてのクラスが必要です。ただし、これにより、クラスをハッシュするつもりがない場合でも、意味的に正しいハッシュ関数を実装する必要がある開発者に追加の負担がかかります。解決策の 1 つは、意味的には正しい定数値を返すことですGetHashCodeが、関数がハッシュに使用されるとあまり効率的ではありません。
検索ツリーは順序付けされていますが、ハッシュは順序付けられていません。
それを回避できる場合は、常にバイナリ検索ツリーよりもハッシュを優先する必要があります。ハッシュはツリーよりもメモリ オーバーヘッドが大きくなりますが、ハッシュが使用するすべてのメモリを 1 つの大きなブロックに割り当てることができます。ツリーの場合、追加されたノードごとに個別の割り当てが必要になるため、断片化が大きくなり、パフォーマンスが低下します。1000 個の異なるファイルから 1 バイトを読み取るよりも、1 つのファイルから 1000 バイトを読み取る方法と同様です。
ハッシュが機能しない場合は、順序付けが重要な場合です。たとえば、メモリ アロケータを記述していて、メモリの空きブロックをデータ構造に格納するとします。キーはブロックのサイズで、値はブロックへのポインタです。
メモリの要求では、このデータ構造を調べて、要求を満たす最小の(順序付けを意味します!) ブロックを見つける必要があります。たとえば、キーが 10、20、30 のブロックがあり、20 バイトのメモリの要求が届いた場合、2 番目のブロックを選択します。ハッシュマップはそれを簡単に行うことができます。
しかし、リクエストが 22 バイトの場合はどうなるでしょうか。値が 20 のキーがないため、ハッシュマップ全体を反復して、O(n) 操作である正しいキー (30) を見つける必要があります。しかし、ツリーを使用した場合、「特定のキーよりも大きい最小のキーを見つける」ことは O(log n) 操作です。
C++ の時代には、人々はまだデータ構造とアルゴリズムに対する筋金入りのアカデミックなアプローチのファンだったので、メモリ フットプリントが小さく、最良の場合と最悪の場合の動作がよく理解されている構造を好みました。
Ruby が登場する頃には、スクリプティングの目的で、生のパフォーマンスよりもシンプルさを好むことに人々は気付きました。ハッシュテーブルは、配列 (シーケンシャル インデックスをキーとして使用する場合) と辞書 (自然キーを使用する場合) の両方のセマンティクスを許可するためです。 、それらはより普遍的なデータ構造と見なされました。