data-structures - ハッシュテーブルでのチェーニングとプローブの違いは何ですか?

Question

それらはどのように機能しますか？主な違いは何ですか? それぞれのトレードオフは何ですか? それらのタイプは何ですか（ある場合）？どちらかが優先されるのはいつですか (ある場合)?

PS:アナグラム - C でチェーンとプロービングを使用したハッシュと、リストにリンクされた個別のチェーンがある場合、ハッシュ テーブルで線形プロービングを使用するのはなぜですか? 、しかしどちらも2つの方法の間に対照を描いていないようです。

Answer 1

衝突を解決するためにハッシュテーブルでチェーニングとオープンアドレス指定 (リニアプローブに基づく単純な実装) が使用されます。2 つの異なるキーのハッシュ関数が同じ場所を指して値を格納する場合は常に衝突が発生します。

両方の値を格納するために、異なるキーを同じ場所に格納するため、チェーンとオープン アドレッシングは異なるアプローチをとります。open-addressing は、同じハッシュを持つ値を格納する別の場所を見つけようとします。

オープン アドレスの競合解決のためのリニア プローブに代わる興味深い方法は、ダブル ハッシングと呼ばれるものです。

発生する主な違いは、さまざまな条件下でハッシュされる値を取得する速度にあります。

衝突解決としてチェインから始めましょう。ここで、Lisa のハッシュ関数を計算した後、必要な値を取得するためにリストから最初の要素を取得する必要があることに注意してください。したがって、リストの先頭へのポインタにアクセスしてから、値にアクセスします: 2 つの操作。

一方、linear-probingなどのオープン アドレッシングでは、衝突がなければ、求めている値がすぐに得られます。つまり、必要な操作は 1 つだけで、より高速です。

ただし、HashTable がいっぱいになり始め、負荷係数が高くなると、競合がより頻繁に発生するため、必要な実際の値を見つける前に、プロービングで Hashtable の場所をさらに確認する必要があります。約 0.8 の負荷係数で、複数の衝突により連鎖がより効率的になり始めます。プローブで必要な実際の値を見つけるために、多くの空のセルをプローブする必要がありますが、連鎖では値のリストがあります。同じハッシュキーを持つもの。

実際のデータ、キーの配布、使用されるハッシュ関数、および衝突解決の正確な実装によって、実際の速度に違いが生じるため、これは簡単な概要です。