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

二つのキーが同じ格納先になったら、どう探し分けるのでしょうか？

チェイン法は同じバケットにつなぎ、オープンアドレス法は別の空きを探します。衝突、削除済みマーク、負荷率を具体的な番地で確認します。

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

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

探索手法	事前のデータ整列	平均計算量	最悪計算量	特徴
線形探索 (Linear Search)	不要	O(n)	O(n)	先頭から順に全走査。最も低速。
二分探索 (Binary Search)	★ 必須（昇順ソート済み）	O(log n)	O(log n)	探索範囲を半分ずつ絞り込む。
ハッシュ探索 (Hash Search)	不要	★ O(1)（定数時間！）	O(n)（衝突多発時）	分布と負荷率を適切に保つ場合に平均O(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] に格納！

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

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

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

負荷率（Load Factor: α）

text

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

負荷率の意味は方式によって異なります。チェイン法はα＞1でも格納できますが、鎖が長くなり得ます。オープンアドレス法は空きが必要で、αが1へ近づくと探索が増えます。拡張の閾値は実装によって異なります。

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

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

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

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

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

キーAが[2]に格納され、衝突したキーBが空きを探して[3]に格納されたとする。
キーAを削除し、[2]を「空」にしてしまう。
キーBを探索する際、ハッシュ関数で[2]を計算する。[2]が「空」になっていると、プログラムは「キーBは登録されていない」と誤認して探索を打ち切ってしまう！
探索では通過し、未使用の空きに着いたら未登録と判断します。挿入では削除済み位置を候補として覚え、同じキーが後ろにないか確認してから再利用します。

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

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

サイズ 7（インデックス 0〜6）のハッシュ表がある。ハッシュ関数を「h(key) = key mod 7」、衝突解決法をオープンアドレス法（衝突時はインデックスを +1 ずつ増やし、末尾に達したら 0 に戻る線形探索法）とする。

すでにキー「14, 21, 8」が順に格納されている状態に、新しくキー「15」を格納するインデックスはどれか。

【正解】ウ

14 mod 7＝0で[0]へ、21 mod 7＝0ですが衝突して[1]へ、8 mod 7＝1ですが衝突して[2]へ入ります。15 mod 7＝1も衝突し、[1]、[2]の次の空き[3]へ入るため、正解はウです。

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

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

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

【正解】イ

正解はイです。全キーが同じバケットに入ると、鎖を先頭からたどり最悪O(n)です。アは、チェイン法ではバケット数以上を格納できるため誤り。ウの削除済みマークは通常のオープンアドレス法の処理です。

エは、ハッシュ表がキーの大小順を保持しないため誤りです。

空きと削除済みを分けて探索する

位置の状態	探索時	登録時
同じキー	発見として返す	既存の値を更新する等、仕様に従う
異なるキー	次の候補へ	次の候補へ
削除済み	探索を続ける	再利用候補にする
未使用の空き	未登録と判定	候補位置に登録する

探索は最大で表のm箇所を確認したら終了するようにします。満杯や削除済みだけの表で、未使用の空きを待って循環し続ける処理は誤りです。

線形プロービングで番地6の次は(6＋1) mod 7＝0です。二次プロービングや二重ハッシュでは、設定によって全番地を巡れない場合があるので、表サイズと更新式を確認します。

出典と仕様を確認する

IPA：FEシラバス Ver.9.2

Open Data Structures：ハッシュ表