ハッシュ法と衝突解決アルゴリズム：チェイン法・オープンアドレス法とハッシュ探索の実戦解法

大量のデータの中から目的のキーを持つ要素を、データ数に関わらず「ほぼ一撃（平均計算量 O(1)）」で検索できる究極の探索手法が「ハッシュ法（ハッシュ探索：Hash Method）」です。

試験では、ハッシュ関数（剰余法等）の計算手順、異なるキーが同一番地に割り当てられてしまう「衝突（シノニム）」のメカニズム、そしてそれを解決する「チェイン法」と「オープンアドレス法」の違いが頻出します。

本記事では、ハッシュ探索の基礎原理から、2大衝突解決策のアルゴリズム的相違、負荷率（ロードファクタ）と探索性能の関係までを図解で分かりやすく解説します。

1. ハッシュ法の基本原理：なぜ平均 O(1) で探索できるのか

線形探索や二分探索では「データ同士の大小比較」を繰り返して目的の値を探します。これに対しハッシュ法では、「探索キーの値から、格納先の配列インデックス（番地）を計算式で直接算出する」という根本的に異なるアプローチを取ります。

探索手法	事前のデータ整列	平均計算量	最悪計算量	特徴
線形探索 (Linear Search)	不要	O(n)	O(n)	先頭から順に全走査。最も低速。
二分探索 (Binary Search)	★ 必須（昇順ソート済み）	O(log n)	O(log n)	探索範囲を半分ずつ絞り込む。
ハッシュ探索 (Hash Search)	不要	★ O(1)（定数時間！）	O(n)（衝突多発時）	計算一発で番地を特定。データが1億件あっても1回の計算で探索完了。

【代表的なハッシュ関数：剰余法（Division Method）】

配列のサイズ（バケット数）を m としたとき、キー値 k を m で割った「余り（剰余）」を格納番地とする方式が最も一般的です。

text

// 剰余法によるハッシュ関数
hash_index = key mod m

// 例: 配列サイズ m = 7 の場合
// key = 25 の格納番地: 25 mod 7 = 4  → 配列[4] に格納！
// key = 10 の格納番地: 10 mod 7 = 3  → 配列[3] に格納！

2. 衝突（シノニム：Synonym）と負荷率の罠

異なるキー値に対して、ハッシュ関数が偶然同じインデックスを算出してしまい、格納先が重複してしまう現象を「衝突（シノニム / Collision）」と呼びます。

例: 配列サイズ m = 7 のとき、key = 11 (11 mod 7 = 4) と key = 25 (25 mod 7 = 4) は同じ配列[4] を取り合って衝突します。

【負荷率（Load Factor: α）】

text

負荷率 α ＝ 格納要素数 n ／ バケット総数 m

負荷率 α が 1.0 に近づく（または超える）ほど衝突の発生確率は急上昇し、探索性能が O(1) から O(n) へと劣化します。実務では α が 0.7〜0.75 を超えた段階で配列を約2倍に拡張して再ハッシュ（Rehash）を行うのが標準的です。

3. 2大衝突解決アルゴリズム：チェイン法 vs オープンアドレス法

衝突が発生した際、どのようにデータを収容するかによって2つの代表的方式に分かれます。

比較項目	チェイン法 (Chaining)	オープンアドレス法 (Open Addressing)
別名	開ハッシュ法 (Separate Chaining)	閉ハッシュ法 (クローズドハッシュ)
衝突時の解決メカニズム	衝突した要素同士を「連結リスト（ポインタ）」で数珠繋ぎにして同一バケットにぶら下げる。	衝突したら、空いている「別のバケット」を探してそこに格納する（再ハッシュ）。
空きバケットの探索法	不要（同じ場所にポインタ追加するだけ）	線形探索法（+1ずつ進む）、2次探索法（+1, +4, +9...）、ダブルハッシュ法。
バケット数超のデータ格納	可能（リストを伸ばせばいくらでも格納可）	不可能（配列サイズ m が格納上限）
メモリ効率	ポインタ用のメモリオーバーヘッドが発生する。	配列領域のみで完結するためメモリ効率が良い。
データ削除時の注意点	リストのポインタを繋ぎ替えるだけで容易に削除完了。	★ 空き（nil）にしてしまうと後続の探索が途切れるため、「削除済みマーク」を残す必要がある！

4. オープンアドレス法における「削除済みマーク」の超頻出論点

オープンアドレス法でデータを削除する際、配列要素を単に「未登録（空）」に戻してはならないという落とし穴があります。

登録時: キーAが[2]に格納され、衝突したキーBが空きを探して[3]に格納されたとする。
誤った削除: キーAを削除し、[2]を「空」にしてしまう。
その後の探索: キーBを探索する際、ハッシュ関数で[2]を計算する。[2]が「空」になっていると、プログラムは「キーBは登録されていない」と誤認して探索を打ち切ってしまう！
正しい対策: 削除したバケットには「空」ではなく「削除済み（墓石マーク）」を設定する。探索時は「削除済みなら次を探索」、新規登録時は「削除済みなら上書き可能」と判定する。

5. 実戦演習問題とステップ別解説

【問1：剰余法とオープンアドレス法による格納番地トレース】

サイズ 7（インデックス 0〜6）のハッシュ表がある。ハッシュ関数を「h(key) = key mod 7」、衝突解決法をオープンアドレス法（衝突時はインデックスを +1 ずつ増やし、末尾に達したら 0 に戻る線形探索法）とする。すでにキー「14, 21, 8」が順に格納されている状態に、新しくキー「15」を格納するインデックスはどれか。

ア：1
イ：2
ウ：3
エ：4

【正解】ウ

【解説】登録ステップを順番に追跡します。1. キー 14: 14 mod 7 = 0 → [0] は空なので、[0] に格納。2. キー 21: 21 mod 7 = 0 → [0] は衝突！ +1 して [1] を確認。[1] は空なので、[1] に格納。3. キー 8: 8 mod 7 = 1 → [1] は衝突！ +1 して [2] を確認。[2] は空なので、[2] に格納。ここまでで [0]=14, [1]=21, [2]=8 が埋まっています。4. 新規キー 15: 15 mod 7 = 1。・[1] は 21 で埋まっているため衝突！・+1 して [2] を確認するが、8 で埋まっているため再衝突！・さらに +1 して [3] を確認すると、[3] は空いている！したがって、キー 15 は「インデックス 3」に格納されます。正解はウです。

【問2：チェイン法の特徴と計算量】

ハッシュ表の衝突解決法としてチェイン法を採用した場合の特徴として、適切なものはどれか。

ア：ハッシュ表のサイズ（バケット数）を超える個数のデータを格納することはできない。
イ：衝突が発生した同一バケットの要素を単方向リスト等で連結して管理するため、最悪の場合の探索時間は O(n) となる。
ウ：データの削除時に、探索の中断を防ぐための専用の削除フラグを記録する必要がある。
エ：キー同士の大小関係がそのまま保持されるため、範囲指定検索（範囲スキャン）を高速に実行できる。

【正解】イ

【解説】各選択肢を検討します。・ア：誤り。チェイン法はポインタでリストを伸ばせるため、バケット数を超える要素数（負荷率 α > 1.0）でも格納可能です（オープンアドレス法は不可能）。・イ：適切。すべてのキーが運悪く同一のバケットに衝突した場合、単一の長い連結リストになってしまい、先頭から順にたどるため最悪計算量は線形探索と同じ O(n) に劣化します。正解はイです。・ウ：誤り。削除フラグが必要なのはオープンアドレス法です。チェイン法はポインタの付け替えで安全に要素を物理削除できます。・エ：誤り。ハッシュ関数はキー値をランダムな番地に分散させるため、大小関係は失われ範囲検索には適しません（範囲検索にはB-Tree等が使われます）。