ハッシュテーブルの内部（衝突解決とオープンアドレス法）

平均O(1)はどこから来るのか

ハッシュテーブルが検索・追加・削除を平均O(1)でこなせる理由は、キーから格納位置を計算で求める点にあります。比較に基づく木構造がO(log n)に縛られるのに対し、ハッシュテーブルは要素数nに依存しない一定回数の操作で目的のスロットへ到達します。基礎的な使い分けはデータ構造で扱ったので、本稿はその内部、すなわち衝突をどう捌くかに踏み込みます。

仕組みは二段構えです。まずハッシュ関数 h(key) がキーを大きな整数（ハッシュ値）へ写し、次に h(key) mod m（mは配列長）で配列添字に畳み込みます。理想は「異なるキーが異なる添字に均等に散る」ことですが、無限のキー空間を有限のmスロットへ写す以上、鳩の巣原理により同じ添字に複数キーが集まる**衝突（collision）**は必ず起きます。ハッシュテーブルの設計とは、本質的に衝突をいかに安く解決するかの設計です。

ハッシュ関数に求められる性質

良いハッシュ関数は、入力の偏りに関わらず出力を一様に分散させます（均一性）。1ビットの入力変化で出力ビットの約半数が反転する雪崩効果を持つと、連番キーや似たキーが近接スロットに固まる事故を防げます。文字列にはFNV-1aやMurmurHash、整数には乗算ハッシュ（フィボナッチハッシュ）がよく使われます。

なお、悪意あるユーザーが意図的に衝突するキー列を送り込み計算量をO(n)へ劣化させるハッシュフラッディング攻撃への対策として、実行時にランダムな種を混ぜるシード付きハッシュ（SipHash等）が標準ライブラリで採用されています。

チェイン法（separate chaining）

最も素直な衝突解決は、各バケットに連結リスト（または小さな配列）を持たせ、同じ添字に来た要素をそこへ繋ぐチェイン法です。挿入はリスト先頭への追加でO(1)、検索は該当バケットのリストを線形走査します。

添字  バケット
 0 -> null
 1 -> ["cat":3] -> ["dog":7] -> null   // 同じ添字に衝突した2要素
 2 -> ["fox":1] -> null

リストの平均長は負荷率α（後述）に等しく、検索の期待計算量はO(1 + α)です。チェイン法は実装が単純で、αが1を超えても破綻せず緩やかに劣化する堅牢さが利点ですが、要素ごとにポインタを辿るためメモリ局所性が悪く、ノード確保のオーバーヘッドも生じます。Java 8以降のHashMapは、1バケットの要素が一定数（8）を超えると連結リストを赤黒木へ切り替え、最悪計算量をO(n)からO(log n)へ抑えます。

オープンアドレス法（open addressing）

別領域を使わず、衝突したら配列内の別の空きスロットを探すのがオープンアドレス法です。すべての要素が連続配列に収まるためキャッシュ効率が高く、ポインタ追跡が不要で、現代の高速ハッシュマップ（Pythonのdict、RustのHashMap、Googleのswiss table等）の多くが採用します。探索順を決めるプローブ法が肝です。

線形探索（linear probing）は h(k), h(k)+1, h(k)+2, … と隣を順に見ます。実装が単純でメモリアクセスが連続するため最速級ですが、占有スロットが連なると一次クラスタリングが起き、新たな衝突がその塊を伸ばす悪循環に陥ります。ダブルハッシュは刻み幅を第2のハッシュ h2(k) で決め、キーごとに探索経路をばらつかせてクラスタ化を抑えます。

負荷率とリハッシュ

性能を支配する単一の指標が負荷率（load factor） α = 要素数 / スロット数 です。オープンアドレス法では、線形探索の検索失敗の期待プローブ回数が概ね (1/2)(1 + 1/(1-α)²) で近似され、αが1へ近づくと急激に発散します。ゆえに容量を使い切る前に拡張が必要です。

αが閾値を超えると**リハッシュ（rehash / resize）を行います。通常は容量を約2倍の新配列（多くは2のべき乗）に取り直し、全要素を再ハッシュして再配置します。剰余mが変わると h(k) mod m の結果も変わるため、単なるコピーでは済まない点に注意が必要です。リハッシュ1回はO(n)ですが、倍々で拡張するため挿入n回あたりの総コストはO(n)に収まり、1挿入あたりのならし計算量はO(1)**になります（計算量とBig-O記法）。

ロビンフッドハッシュ — 探索距離を均す

線形探索の弱点は、運の悪いキーが長大なプローブ列の末尾に置かれ、検索が極端に遅くなる分散の大きさです。ロビンフッドハッシュは挿入時に各要素のPSL（probe sequence length＝本来位置からの距離）を比較し、「自分より裕福な（PSLが小さい）既存要素」に出会ったらその要素を押しのけて居座り、押し出された要素を代わりに運ぶ戦略です。富める者から奪い貧しい者へ与える、という命名どおりの挙動です。

挿入中の要素のPSL > その位置の既存要素のPSL なら入れ替える
→ 各スロットのPSLが平準化し、最長プローブ列が劇的に短くなる

結果としてPSLの最大値と分散が小さく抑えられ、検索の最悪・テール遅延が安定します。さらに「探索中のPSLが現在スロットの要素のPSLを上回った時点で、目的キーは存在しないと確定」できるため、検索失敗の早期打ち切りも可能になります。高負荷率でも性能が崩れにくく、swiss tableと並んで現代の高性能実装の主流的アイデアです。

まとめ

ハッシュテーブルの平均O(1)は、一様なハッシュ関数と、必ず起きる衝突を安く解決する仕組みの両輪で成り立ちます。チェイン法はバケット外のリスト（または木）で堅牢に捌き、オープンアドレス法は配列内プローブでキャッシュ効率を稼ぐ代わりに墓石やクラスタリングを管理します。性能の支配項は負荷率αで、閾値超過時のリハッシュがならしO(1)を担保し、ロビンフッドハッシュはPSLを均してテール遅延を抑えます。どの方式も「平均O(1)・最悪O(n)」という本質を共有しており、ハッシュ品質・負荷率・衝突解決の三点を押さえて初めて、実測の挙動を正しく見積もれます。