ハッシュテーブル — O(1) で見つける魔法と、衝突との戦い

「この鍵はどこ？」を、探さずに計算で一発で当てる。鍵から格納先の番号を作り出すハッシュ関数を軸に、なぜ平均 O(1) で出し入れできるのか、そして避けられない衝突とどう付き合うのかを、玉を落としながら体感します。

1. 鍵から住所を計算する — ハッシュ関数

配列は「何番目？」と番号で聞けば即座に取り出せます。ならば鍵そのものから番号を計算してしまえばいい。鍵を数に変え、バケット数 M で割った余りを添字にする——これが最も素朴なハッシュ関数 h(key) = key mod M です。

下のデモでは、鍵（数字の玉）が落ちてくると h が格納先のバケット番号を計算し、そこへ直行します。バケット数 M を変えたり、鍵を追加してみてください。

鍵が落ちてバケットへ直行する
上に出る式が h(key)=key mod M の計算。玉は「探索」なしで自分のバケットへ飛び込みます。緑＝そのバケット最初の鍵、オレンジ＝同じバケットに後から来た鍵（＝衝突）。M を変えると落ち先がガラッと変わります。
POINT — 探索を「計算」に置き換える ハッシュ関数は鍵を配列の添字に変換する装置。だから「どこにあるか探す」必要がなく、計算した番号のバケットへ直行できる。これがハッシュテーブルの速さの源。
h(key) = key mod M 鍵を M で割った余りが格納先の番号。割り算1回で「住所」が決まる。実際の M には偏りを減らすため素数がよく選ばれる

2. ぶつかったら数珠つなぎ — チェイン法と探索

違う鍵でも計算結果が同じ番号になることがあります。これが衝突（コリジョン）。バケットは M 個しかないのに鍵は無限に作れるので、衝突は原理的に避けられません（鳩の巣原理）。

いちばん素直な対処がチェイン法：同じバケットに来た鍵を連結リストでつなぐだけ。探すときは h で目的のバケットへ飛び、あとはその短い鎖だけを順にたどります。下で鍵を選ぶと、探索の様子が動きます。

探索 — バケットへ飛んで、鎖をたどる
左の縦列がバケット配列、右へ伸びるのが連結リスト（鎖）。まず h で1つのバケットへジャンプ（青のリング）、そこから鎖を1個ずつ比較します。鎖が短ければ比較はほんの数回。見つからない鍵（30）は鎖の端まで見て「なし」と分かります。
注意 — 悪いハッシュ関数は全部を1本の鎖にする もし全鍵が同じバケットに集まると、鎖は長さ n の連結リストになり探索は O(n) に退化する。だから「鍵をバケット全体へ均一にばらまく」のが良いハッシュ関数の絶対条件。偏れば偏るほどハッシュテーブルの利点は消える。

3. 詰め込みすぎると衝突が増える — 負荷率 α

速さを保てるかは、どれだけ混んでいるかで決まります。鍵の数 n をバケット数 M で割った値を負荷率 α = n / M と呼び、これがそのまま1バケットあたりの平均の鎖の長さになります。

下で鍵の数 n とバケット数 M を動かしてみてください。α が上がるほど鎖（＝オレンジの衝突玉）がぐんぐん積み上がっていくのが分かります。

負荷率を上げると衝突が積み上がる
各列が1バケット。緑＝そのバケット最初の鍵、オレンジ＝2個目以降（衝突）。n を増やすか M を減らすと α が上がり、鎖が伸びていきます。上の数字で負荷率と平均鎖長を確認できます。
POINT — α を低く保つ「作り直し」 平均の探索コストは 約 1 + α/2 回の比較。α が小さいほど一定時間に近づく。だから実装は α がしきい値（例: 0.75）を超えたらM を約2倍に増やして全部入れ直す（リハッシュ）。これで α を低く保ち、ならして見れば O(1) を維持する。
α = n / M   →   平均鎖長 = α,   平均比較回数 ≈ 1 + α/2 鍵を均一にばらまけると、空バケットの割合は約 e−α。α=1（鍵数＝バケット数）でも約37%は空という直感に反する事実

4. なぜ速い？ — 配列の線形探索と競争

並べ替えていない配列から目的の鍵を探すには、先頭から1個ずつ照合するしかありません（線形探索、平均 n/2 回）。ハッシュテーブルは h で目的のバケットへ一足飛びし、短い鎖を数回見るだけ。同じ鍵を同時に探させて、歩数を比べてみましょう。

線形探索 vs ハッシュ — 歩数くらべ
上＝並び替えていない配列を先頭から総なめ（黄のスキャナが進む）。下＝ハッシュ表は h で1つのバケットへジャンプし、鎖を少し見るだけ。配列は鍵が奥にあるほど時間がかかり、ハッシュはほぼ一定です。
一歩先へ — 現場のハッシュテーブル 衝突対策にはチェイン法のほか、空きバケットへずらして詰めるオープンアドレス法もある。実務の dict／HashMap／set はこれらの上に、良質なハッシュ関数とリハッシュを組み合わせて平均 O(1) を実現している。用途で使い分けもあり、改ざん検知や暗号で使う暗号学的ハッシュ（SHA-256 など）は「逆算・衝突が困難」という別の強さを持つ。速さ用と安全用でハッシュは目的が違う。

5. まとめ — ハッシュテーブルの設計図