ハッシュテーブルの衝突解決:チェイニング vs オープンアドレッシング
ハッシュテーブルがセパレートチェイニングとオープンアドレッシングで衝突をどのように処理するかを理解します。線形探査、二次探査、二重ハッシングの戦略を例とともに比較します。
Hash Table
詳細な説明
ハッシュテーブルの衝突解決
ハッシュ衝突は、2つの異なるキーが同じハッシュ値を生成する(同じバケットにマッピングされる)場合に発生します。可能なキーの数は通常バケット数よりはるかに多いため、衝突は不可避です。
セパレートチェイニング
各バケットがそのバケットにハッシュされるすべてのエントリの連結リストを格納します:
Bucket 0: -> ("apple", 5) -> ("grape", 8)
Bucket 1: -> ("banana", 3)
Bucket 2: (empty)
Bucket 3: -> ("cherry", 7) -> ("date", 2) -> ("fig", 9)
オープンアドレッシング
すべてのエントリがバケット配列に直接格納されます。衝突が発生すると、アルゴリズムは次の利用可能なスロットを探査します。
線形探査: バケットh、次にh+1、h+2...をチェック。
二次探査: バケットh、次にh+1、h+4、h+9...をチェック。
二重ハッシング: 第2のハッシュ関数で探査ステップを決定。
パフォーマンス比較
| 指標 | チェイニング | 線形探査 | 二重ハッシング |
|---|---|---|---|
| 平均検索(低負荷) | O(1) | O(1) | O(1) |
| キャッシュ性能 | 悪い | 優秀 | 良い |
| 削除 | 簡単 | トゥームストーンが必要 | トゥームストーンが必要 |
トゥームストーン削除
オープンアドレッシングでは、削除時にスロットを単純に空にすることはできません — 他のキーの探査シーケンスが壊れます。代わりに、削除されたスロットはトゥームストーンとしてマークされます。
ユースケース
すべてのハッシュテーブル実装は衝突解決戦略を選択する必要があります。言語の標準ライブラリは様々です:JavaのHashMapはチェイニング、Pythonのdictはオープンアドレッシング、Goのmapはチェイニングの変形を使用します。これらの戦略の理解はシステム設計と適切なデータ構造の選択に不可欠です。