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

Question

どのように機能しますか？彼らの主な違いは何ですか？それぞれのトレードオフは何ですか？彼らのタイプ（もしあれば）は何ですか？いつ他の人に好まれるのはいつですか（もしあれば）？

PS：私はすでにAnagrams - Hashing with chaining and probing in CとWhy do we use linear probing in Hash tables when there is separate chaining linked with lists?に行っていますが、いずれもどちらの方法も対照的ではないようです。

Answer 1

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

同じ場所に格納されていた異なるキーを使用して両方の値を格納するには、連鎖とオープンアドレッシングでは異なるアプローチがあります。連鎖は同じハッシュで値のリンクリストを作成して競合を解決します。オープンアドレスは、同じハッシュを持つ値を格納するために別の場所を見つけることを試みようとします。

オープンアドレッシング競合解決のための線形プロービングの興味深い代替案は、ダブルハッシュとして知られているものです。

異なる主な違いは、異なる条件下でハッシュされる値を検索する速度にあります。

衝突の解決としてchainingから始めましょう。 Lisaのハッシュ関数を計算した後、リストから最初の要素を取得して必要な値を取得する必要があります。したがって、リストの先頭へのポインタにアクセスし、value：2操作にアクセスします。

一方、linear-probingのようなオープンアドレッシングでは、衝突がない場合は、直ちに求める値を取得します。つまり、1回の操作で済みます。これは高速です。

しかし、あなたのHashTableがいっぱいになり、より高い数字のload factorを持っていると、衝突が頻繁に起こるため、実際の値を見つける前にHashtableの位置を確認する必要があります。 0.8の負荷係数では、複数の衝突のために連鎖がより効率的になり始めます。プローブを使用して実際の値を見つけるために空のセルをたくさん調べる必要があります。それらは同じハッシュキーを持っています。

これは実際のデータ、キーの分布、使用されるハッシュ関数、衝突解決の正確な実装が実際の速度に影響を与えるため、簡単な概要です。