ハッシュテーブル上のバイナリ検索ツリーの利点

https://stackoverflow.com/questions/4128546

29-09-2019
|

質問

ハッシュテーブル上のバイナリ検索ツリーの利点は何ですか？

ハッシュテーブルは、Theta（1）の任意の要素を調べることができ、要素を追加するのも簡単です。...しかし、逆になる利点がわかりません。

解決

バイナリ検索ツリー（参照ベース）はメモリ効率が高いことに注意してください。彼らは必要以上の記憶を確保しません。

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

他のヒント

他の誰も指摘していない利点の1つは、バイナリ検索ツリーを使用すると、範囲検索を効率的に実行できることです。

私のアイデアを説明するために、私は極端なケースを作りたいです。キーが0〜5000のすべての要素を取得したいとします。実際には、キーが範囲にないそのような要素と10000の要素しかありません。 BSTは、答えを得ることができないサブツリーを検索しないため、非常に効率的に範囲検索を行うことができます。

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

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

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

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

一方、敵があなたのハッシュ機能を知っている場合、敵はハッシュテーブルを強制して衝突を起こすことができ、そのパフォーマンスを大いに妨げます。回避策は、家族からハッシュ機能をランダムに選択することですが、BSTにはこの欠点はありません。また、ハッシュテーブルの圧力が大きすぎると、高価な操作である可能性のあるハッシュテーブルを拡大して再配置する傾向があります。 BSTはここでより単純な動作をしており、多くのデータを突然割り当てて再ハッシング操作を行う傾向はありません。

木は最終的な平均データ構造である傾向があります。それらはリストとして機能し、並列操作のために簡単に分割することができ、順序で迅速な除去、挿入、および検索を行うことができます o（lg n）. 。彼らは何もしません特にまあ、しかし、彼らは過度に悪い行動を持っていません。

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

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

任意のキー値（または最も近い/下）に最も近い（必ずしも等しくない）要素を見つけます
並べ替えられた順序でツリーの内容を繰り返します

2つは接続されています - バイナリツリーはその内容を並べ替えられた順序で保持するため、並べ替えられた順序を必要とするものは簡単です。

（バランスのとれた）バイナリ検索ツリーには、その漸近の複雑さが実際には上限であるという利点もありますが、ハッシュテーブルの「一定の」時間は償却時間です。、一定ではなく。

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

バイナリ検索ツリーは、で実装できます 持続的 新しい木が返されますが、古い木が存在し続けているインターフェイス。慎重に実装されているため、古い木と新しい木はほとんどのノードを共有しています。標準のハッシュテーブルでこれを行うことはできません。

バイナリツリーは検索と挿入が遅くなりますが、Infixトラバーサルの非常に優れた機能があり、本質的には、ツリーのノードを並べ替えられた順序で繰り返すことができます。

ハッシュテーブルのエントリを繰り返すと、それらはすべてメモリに散らばっているため、それほど意味がありません。

BSTSは、O（logn）時間で「FindPredexernear」および「FindSuccessor」操作（次に最小の最大の要素を見つける）を提供します。これは非常に便利な操作でもあります。ハッシュテーブルは、その時間効率では提供できません。

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

バランスの取れたバイナリ検索ツリー（BST）でハッシュテーブルを実装できます。これにより、O（log n）ルックアップ時間が得られます。これの利点は、大規模な配列を割り当てなくなったため、より少ないスペースを使用する可能性があることです。また、キーを順番に繰り返すこともできます。これは時々役立つことがあります。

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

これは、インサートを遅くするだけでなく、Bツリーよりも多くのメモリを消費するという副作用があります。

さらに、Bツリーがソートされているため、結果の範囲を見つけるか、組合または合併を実行するのは簡単です。

また、使用に依存します。ハッシュは正確な一致を見つけることができます。範囲をクエリしたい場合は、BSTが選択です。多くのデータE1、E2、E3 ..... en。

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

E41を超えてE8よりも少ない範囲値を見つけたい場合、BSTはすぐにそれを見つけることができます。

重要なことは、衝突を避けるために使用されるハッシュ関数です。もちろん、衝突を完全に回避することはできません。その場合、チェーンやその他の方法に頼ります。これにより、最悪の場合は検索が一定になりなくなります。

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

HashMapは、セット連想配列です。そのため、入力値の配列はバケットにプールされます。オープンアドレス指定スキームでは、バケツへのポインターがあり、バケツに新しい値を追加するたびに、バケツのどこに自由なスペースがあるかがわかります。これを行うにはいくつかの方法があります。バケットの先頭から始めて、毎回ポインターを増やして、その占有かどうかをテストします。これはリニアプロービングと呼ばれます。次に、ADDのようなバイナリ検索を行うことができます。ここでは、バケツの始まりと、自由スペースを検索するたびに2倍または下に戻る場所の違いを2倍にすることができます。これは二次調査と呼ばれます。わかった。ここで、これらの両方の方法の問題は、バケットが次のバケットアドレスにオーバーフルする場合、あなたがする必要があるということです。

各バケットサイズ - マロック（nバケット）/ハッシュ関数の変更 - 必要な時間：mallocの実装に依存します
以前のバケットデータのそれぞれを新しいバケットデータに転送/コピーします。これはo（n）操作であり、nはデータ全体を表します

わかった。しかし、LinkedListを使用している場合、そのような問題はありませんか？はい、リンクされたリストでは、この問題はありません。各バケットをリンクしたリストから始めることを検討し、バケットに100の要素がある場合は、LinkedListの終わりに到達するためにこれらの100の要素を横断する必要があります。

すべての実装と同様に、要素をバケツにハッシュする - 通常のもの -
時間をかけて、そのバケットO（n）操作で最後の要素を見つけてください。

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

したがって、O（n）操作を最小限に抑える方法は、実装を操作を検索するバイナリ検索ツリーの実装に変換することです。 BSTの追加機能は、ソートされていることです！

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

バイナリ検索ツリーは、キーに合計順序（キーが比較可能）が定義されており、注文情報を保存する場合、辞書を実装するのに適しています。

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

最大
最小
後継
前身

すべてのBST操作のようなこれらすべての操作には、O（H）の時間複雑さがあります。さらに、すべての保存されたキーはBSTでソートされたままであるため、ツリーをオーダーで横断するだけで、キーのソートシーケンスを取得できます。

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

文字列キーで使用すると、バイナリ検索ツリーがより速くなります。特に弦が長いとき。

比較を使用してバイナリ検索ツリーを使用して、文字列の場合は高速/大きい場合（等しくない場合）。したがって、文字列が見つからないときにBSTはすぐに答えることができます。見つかった場合、完全な比較を1つだけ行う必要があります。

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

ハッシュテーブルの主な利点は、〜= o（1）でほぼすべてのOPSを実行することです。そして、その非常に理解し、実装しやすいです。多くの「インタビューの問題」を効率的に解決します。コーディングインタビューをクラックしたい場合は、ハッシュテーブルで親友を作ります;-)

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow