data-structures - ハッシュテーブルに対する二分探索木の利点

Question

ハッシュテーブルに対する二分探索木の利点は何ですか？

ハッシュテーブルはTheta（1）の時間内に任意の要素を検索でき、要素を追加するのも同じくらい簡単です....しかし、逆の利点があるかどうかはわかりません。

score 143 · Accepted Answer

他の誰も指摘していない利点の1つは、二分探索木を使用すると範囲検索を効率的に実行できることです。

私の考えを説明するために、私は極端なケースを作りたいと思います。キーが0から5000の間にあるすべての要素を取得したいとします。実際には、そのような要素は1つだけで、キーが範囲内にない他の要素は10000個しかありません。BSTは、答えを得ることが不可能なサブツリーを検索しないため、範囲検索を非常に効率的に実行できます。

一方、ハッシュテーブルで範囲検索を行うにはどうすればよいですか？O（n）であるすべてのバケットスペースを反復するか、1、2、3、4...最大5000のそれぞれが存在するかどうかを探す必要があります。（0から5000までのキーは無限集合ですか？たとえば、キーは小数にすることができます）

score 102 · Accepted Answer

二分探索木（参照ベース）はメモリ効率が高いことを忘れないでください。必要以上のメモリを予約することはありません。

たとえば、ハッシュ関数に範囲がある場合、R(h) = 0...10020個の要素をハッシュしているだけでも、100個の（ポインタから）要素の配列を割り当てる必要があります。バイナリ検索ツリーを使用して同じ情報を格納する場合は、必要なだけのスペースと、リンクに関するメタデータを割り当てるだけです。

score 81 · Accepted Answer

二分木の「利点」の1つは、すべての要素を順番にリストするためにトラバースできることです。これはハッシュテーブルでは不可能ではありませんが、ハッシュ構造に設計された通常の操作ではありません。

score 56 · Accepted Answer

他のすべての良いコメントに加えて：

一般に、ハッシュテーブルは、バイナリツリーと比較して、必要なメモリ読み取りが少ないキャッシュ動作が優れています。ハッシュテーブルの場合、通常、データを保持している参照にアクセスする前に、1回の読み取りのみが発生します。二分木は、それがバランスの取れたバリアントである場合、定数kに対してk * lg（n）メモリ読み取りのオーダーの何かを必要とします。

一方、敵があなたのハッシュ関数を知っている場合、敵はあなたのハッシュテーブルに衝突を強制し、そのパフォーマンスを大幅に妨げる可能性があります。回避策は、ファミリからランダムにハッシュ関数を選択することですが、BSTにはこの欠点はありません。また、ハッシュテーブルのプレッシャーが大きくなりすぎると、ハッシュテーブルを拡大して再割り当てする傾向があり、コストのかかる操作になる可能性があります。ここでのBSTの動作は単純であり、突然大量のデータを割り当てて再ハッシュ操作を実行する傾向はありません。

ツリーは、最終的な平均データ構造になる傾向があります。それらはリストとして機能し、並列操作のために簡単に分割でき、O（lg n）のオーダーで高速な削除、挿入、およびルックアップが可能です。彼らは特にうまくいくことはありませんが、過度に悪い行動もありません。

最後に、BSTは、ハッシュテーブルと比較して（純粋）関数型言語での実装がはるかに簡単であり、破壊的な更新を実装する必要はありません（上記のPascalによる永続性の議論）。

score 31 · Accepted Answer

ハッシュテーブルに対するバイナリツリーの主な利点は、バイナリツリーがハッシュテーブルでは（簡単に、すばやく）実行できない2つの追加操作を提供することです。

任意のキー値に最も近い（または必ずしも等しくない）要素を見つける（または上/下に最も近い）
ソートされた順序でツリーの内容を反復処理します

2つは接続されています-バイナリツリーはその内容をソートされた順序で保持するため、ソートされた順序を必要とすることは簡単に実行できます。

score 16 · Accepted Answer

（平衡）二分探索木には、その漸近的な複雑さが実際には上限であるという利点もありますが、ハッシュテーブルの「一定の」時間は償却された時間です。不適切なハッシュ関数がある場合、線形時間に低下する可能性があります。、一定ではなく。

score 11 · Accepted Answer

ハッシュテーブルは、最初に作成されたときに、より多くのスペースを占有します-まだ挿入されていない要素（挿入されているかどうかに関係なく）に使用可能なスロットがあり、バイナリ検索ツリーは必要なだけ大きくなりますなれ。また、ハッシュテーブルがより多くのスペースを必要とする場合、別の構造への拡張には時間がかかる可能性がありますが、それは実装に依存する可能性があります。

score 10 · Accepted Answer

二分木は検索と挿入に時間がかかりますが、中置走査の非常に優れた機能を備えています。つまり、ツリーのノードを並べ替えられた順序で繰り返すことができます。

ハッシュテーブルのエントリを反復処理しても、それらはすべてメモリに分散しているため、あまり意味がありません。

score 8 · Accepted Answer

バイナリ検索ツリーは、永続的なインターフェイスを使用して実装できます。この場合、新しいツリーが返されますが、古いツリーは引き続き存在します。注意深く実装すると、新旧のツリーはほとんどのノードを共有します。標準のハッシュテーブルではこれを行うことはできません。

score 6 · Accepted Answer

BSTは、O（logn）時間に「findPredecessor」および「findSuccessor」操作（次に小さい要素と次に大きい要素を検索する）も提供します。これも非常に便利な操作です。ハッシュテーブルは、その時間の効率を提供することはできません。

score 6 · Accepted Answer

コーディングインタビューのクラッキングから、第6版

平衡二分探索木（BST）を使用してハッシュテーブルを実装できます。これにより、O（log n）ルックアップ時間が得られます。これの利点は、大きなアレイを割り当てる必要がなくなるため、使用するスペースが少なくなる可能性があることです。キーを順番に繰り返すこともできます。これは、場合によっては便利です。

score 2 · Accepted Answer

GCCC++のケーススタディ

また、世界で最も重要な実装の1つからいくつかの洞察を得ましょう。これから見ていくように、それは実際には理論と完全に一致しています！

に示されているように、C ++で設定されたSTLの基礎となるデータ構造は何ですか？、GCC 6.4では：

std::mapBSTを使用
std::unordered_mapハッシュマップを使用

したがって、これは、ハッシュマップを効率的に横断できないという事実をすでに指摘しています。これは、おそらくBSTの主な利点です。

次に、ハッシュマップとBSTの挿入時間と、ヒープとバイナリ検索ツリー（BST）のヒープのベンチマークを行いました。これにより、主要なパフォーマンス特性が明確に強調されます。

BST挿入はO（log）、ハッシュマップはO（1）です。そして、この特定の実装では、ハッシュマップは、比較的小さいサイズであっても、ほとんどの場合BSTよりも高速です。
ハッシュマップは、一般的にははるかに高速ですが、ズームアウトされたプロットで単一のポイントとして表示される非常に遅い挿入がいくつかあります。

これらは、実装がサイズを大きくする時期であると判断し、より大きなサイズにコピーする必要がある場合に発生します。

より正確に言えば、これは、その償却された複雑さのみがO（1）であり、最悪の場合ではなく、実際には配列コピー中のO（n）であるためです。

これにより、より強力な時間保証が必要な特定のリアルタイムアプリケーションにはハッシュマップが不十分になる可能性があります。

関連している：

score 1 · Accepted Answer

ソートされた方法でデータにアクセスする場合は、ソートされたリストをハッシュテーブルと並行して維持する必要があります。良い例は.Netの辞書です。（http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspxを参照してください）。

これには、挿入が遅くなるだけでなく、Bツリーよりも大量のメモリを消費するという副作用があります。

さらに、bツリーはソートされているため、結果の範囲を見つけたり、結合やマージを実行したりするのは簡単です。

score 1 · Accepted Answer

また、用途にもよりますが、ハッシュを使用すると完全に一致するものを見つけることができます。範囲をクエリする場合は、BSTが選択されます。大量のデータe1、e2、e3.....enがあるとします。

ハッシュテーブルを使用すると、任意の要素を一定時間で見つけることができます。

e41より大きくe8より小さい範囲値を見つけたい場合、BSTはそれをすばやく見つけることができます。

重要なのは、衝突を回避するために使用されるハッシュ関数です。もちろん、衝突を完全に回避することはできません。その場合、連鎖または他の方法に頼ります。これにより、最悪の場合、取得が一定時間ではなくなります。

いっぱいになると、ハッシュテーブルはバケットサイズを増やし、すべての要素を再度コピーする必要があります。これは、BSTにはない追加コストです。

score 1 · Accepted Answer

キーにいくつかの全順序が定義されていて（キーは同等である）、順序情報を保持したい場合は、バイナリ検索ツリーが辞書を実装するのに適しています。

BSTは注文情報を保持するため、ハッシュテーブルを使用して（効率的に）実行できない4つの追加の動的セット操作を提供します。これらの操作は次のとおりです。

最大
最小
後継
前任者

すべてのBST操作と同様に、これらすべての操作にはO（H）の時間計算量があります。さらに、保存されているすべてのキーはBSTでソートされたままなので、ツリーを順番にトラバースするだけで、ソートされたキーのシーケンスを取得できます。

要約すると、必要なのが挿入、削除、削除の操作だけである場合、ハッシュテーブルのパフォーマンスは（ほとんどの場合）無敵です。ただし、上記の操作の一部またはすべてが必要な場合は、BST、できれば自己平衡BSTを使用する必要があります。

score 0 · Accepted Answer

ハッシュテーブルはインデックス作成には適していません。範囲を検索する場合は、BSTの方が適しています。これが、ほとんどのデータベースインデックスがハッシュテーブルの代わりにB+ツリーを使用する理由です。

score 0 · Accepted Answer

ハッシュマップは、セットの連想配列です。したがって、入力値の配列はバケットにプールされます。オープンアドレッシングスキームでは、バケットへのポインタがあり、バケットに新しい値を追加するたびに、バケット内のどこに空き領域があるかがわかります。これを行うにはいくつかの方法があります。バケットの先頭から開始し、毎回ポインターをインクリメントして、ポインターが占有されているかどうかをテストします。これは線形プロービングと呼ばれます。次に、addのような二分探索を実行できます。この場合、バケットの先頭と、空き領域を検索するたびに上下に2倍にする差が2倍になります。これは、2次プロービングと呼ばれます。わかった。これらの両方の方法の問題は、バケットが次のバケットアドレスにオーバーフローした場合、次のことを行う必要があることです。

各バケットのサイズを2倍にする-malloc（Nバケット）/ハッシュ関数を変更する-必要な時間：mallocの実装によって異なります
以前の各バケットデータを新しいバケットデータに転送/コピーします。これはO（N）演算であり、Nはデータ全体を表します

わかった。しかし、リンクリストを使用する場合、そのような問題はないはずですよね？はい、リンクリストではこの問題は発生しません。各バケットをリンクリストで開始することを検討します。バケットに100個の要素がある場合は、それらの100個の要素をトラバースしてリンクリストの最後に到達する必要があるため、List.add（要素E）は次のように時間がかかります。

要素をバケットにハッシュする-すべての実装と同様に通常
上記のバケット-O（N）操作の最後の要素を見つけるために時間をかけてください。

リンクリスト実装の利点は、オープンアドレッシング実装の場合のように、メモリ割り当て操作とすべてのバケットのO（N）転送/コピーを必要としないことです。

したがって、O（N）操作を最小化する方法は、実装をバイナリ検索ツリーの実装に変換することです。ここで、検索操作はO（log（N））であり、その値に基づいてその位置に要素を追加します。BSTの追加機能は、ソートされていることです。

score 0 · Accepted Answer

文字列キーとともに使用すると、二分探索木が高速になります。特に弦が長い場合。

文字列に対して高速なless/greatの比較を使用した二分探索木（等しくない場合）。したがって、文字列が見つからない場合、BSTは迅速に応答できます。見つかったら、完全な比較を1回だけ実行する必要があります。

ハッシュテーブル内。文字列のハッシュを計算する必要があります。これは、ハッシュを計算するために少なくとも1回はすべてのバイトを調べる必要があることを意味します。次に、一致するエントリが見つかったとき。

data-structures - ハッシュテーブルに対する二分探索木の利点

18 に答える 18

Related

Reference