ハッシュテーブル可視化ツール

キーを入力すると、それらがスロットにどうマッピングされるかを確認できます。衝突が起きたときに何が起こるかも見てみましょう。

計算例 — ハッシュテーブル可視化ツール

負荷率 alpha	0.75
現在の挙動	5 件の衝突
衝突数	11, 19, 27, 35, 43 件が複数回の探査を必要としました
追加の探査回数	15
平均探査回数	3.5
衝突確率	85%

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

「全部衝突」のプリセットは、ハッシュが壊れているのではなく、表の大きさが間違っている 🖖

その鍵は 0、8、16、24、32、40 で、表のスロットは 8 個です。どの鍵も 8 の倍数なので、key mod 8 は六つすべてをスロット 0 に送り、表はただ一本のリストに退化します。ハッシュ関数はどこも悪くありません。約束どおりに働いています。悪いのは、表の大きさが鍵の並びと共通の因数を持っていることです。素数の表サイズが勧められる理由はまさにこれです。大きさ 8 は 8 刻みで進む鍵に対して無防備ですが、素数なら鍵が着地する因数がありません。探査のプリセットに切り替えて、同じ衝突が二通りに処理されるのを見てください。

目的のスロットへ一直線 🖖

ハッシュ表とは、配列に、任意のキーをスロット番号へ変換する規則であるハッシュ関数を組み合わせたものです。要素を一つずつ調べるのではなく、格納先を計算して直接アクセスするため、キーが数百万個あっても検索を高速に保てます。その速さを左右するのは、キーを均等に分散できるかどうかです。いくつか挿入して、二つのキーが同じスロットを求めるまでの早さを確かめてみましょう。

衝突が武器になるとき 🖖

ハッシュテーブルは、多くのキーが同じスロットに集中すると遅い線形探索に劣化します——まさに上で再現できる最悪ケースです。そのため攻撃者がハッシュ関数を知っていれば、わざと衝突する数千個のキーを作れます。2011年、この「ハッシュフラッディング」攻撃は、細工したリクエスト一つでPHP、Java、Python、Rubyのウェブサーバーを機能停止に追い込みました。対策はSipHashのような乱数シード付きハッシュ関数で、今や多くの言語で標準です。

ハッシュ表 — 鍵がどこに落ちるか、そして二つが同じ場所に落ちたら

いま扱っているのはどの衝突の型か

ハッシュ表が O(1) なのは、鍵が散らばっているあいだだけです。決め手は二つの問いです。ハッシュ関数は鍵をばらけさせているか。そして二つが衝突したとき、二つ目をその場所にぶら下げるのか、別の場所を探しに行くのか。占有率 α = n/m が衝突の頻度を決め、戦略が一回あたりの代償を決めます。

衝突なし — O(1) という約束が前提にしている型 h(k) = k mod m, α = n/m

すべての鍵が一つのスロットへ — 連鎖法が連結リストに退化する O(n)

線形探索法 — 開番地法と一次クラスタリング (h + i) mod m

二次探索法 — クラスタは消えるが、挿入に失敗しうる (h + i²) mod m

衝突なし — O(1) という約束が前提にしている型

わかっていること: どの鍵も別々のスロットに入る。占有率 α = n/m は 1 未満で、ハッシュは鍵を表全体に均等にばらけさせている。

探索規則: h(k) = k mod m, α = n/m

計算例: 鍵 0–5 を m = 8 に h(k) = k mod 8 で入れる → スロット 0–5、各 1 回の探索。α = 0.75、平均探索回数はちょうど 1.00

この型を開く: 衝突なし

衝突なし — O(1) という約束が前提にしている型. 六つの鍵が六つの別々のスロットに入り、各 1 回の探索。見るべきは占有率だけ。どの鍵も別々のスロットに入る。占有率 α = n/m は 1 未満で、ハッシュは鍵を表全体に均等にばらけさせている。 — 六つの鍵が六つの別々のスロットに入り、各 1 回の探索。見るべきは占有率だけ。

すべての鍵が一つのスロットへ — 連鎖法が連結リストに退化する

わかっていること: 鍵はすべて表サイズの倍数なので、k mod m はどれも同じスロットを返す。連鎖法は全部を保持するが、たった一本の鎖に。

探索規則: O(n)

計算例: 鍵 0, 8, 16, 24, 32, 40 を m = 8 に入れる → すべてスロット 0 へ。挿入の総コストは 1+2+3+4+5+6 = 21 回、平均 3.50

この型を開く: 全て衝突

すべての鍵が一つのスロットへ — 連鎖法が連結リストに退化する. 六つの鍵がすべてスロット 0 に。ハッシュ表が連結リストになってしまった状態。鍵はすべて表サイズの倍数なので、k mod m はどれも同じスロットを返す。連鎖法は全部を保持するが、たった一本の鎖に。 — 六つの鍵がすべてスロット 0 に。ハッシュ表が連結リストになってしまった状態。

線形探索法 — 開番地法と一次クラスタリング

わかっていること: 鎖は作らない。衝突したら空きが見つかるまで一つずつ先へ進む。すべての要素は表の中に収まる。

探索規則: (h + i) mod m

計算例: 鍵 3, 11, 19, 6, 14, 22 を m = 8 に入れる → スロット 3, 4, 5, 6, 7, 0、探索回数は 1, 2, 3, 1, 2, 3。平均 2.00 で、六つは切れ目のない一続きになる

この型を開く: 線形探査法

線形探索法 — 開番地法と一次クラスタリング. 埋まったスロットが一つの塊に融合し、その中に落ちた鍵は端まで歩かされる。鎖は作らない。衝突したら空きが見つかるまで一つずつ先へ進む。すべての要素は表の中に収まる。 — 埋まったスロットが一つの塊に融合し、その中に落ちた鍵は端まで歩かされる。

二次探索法 — クラスタは消えるが、挿入に失敗しうる

わかっていること: 衝突したら i ではなく i² スロット分だけ飛ぶ。塊は崩れるが、探索の列はもうすべてのスロットを訪れない。

探索規則: (h + i²) mod m

計算例: 同じ鍵を m = 8 に入れる → 3, 4, 7, 6, 2、そして 22 は完全に失敗する。m が 2 の冪だと i² mod 8 は 0, 1, 4 しか取らず、届くのは三つのスロットだけ

この型を開く: 二次探査法

二次探索法 — クラスタは消えるが、挿入に失敗しうる. 探索の列は飛んでから繰り返す。空きスロットは残り、最後の鍵は行き場を失う。衝突したら i ではなく i² スロット分だけ飛ぶ。塊は崩れるが、探索の列はもうすべてのスロットを訪れない。 — 探索の列は飛んでから繰り返す。空きスロットは残り、最後の鍵は行き場を失う。

全プロセスの詳細解説

75% が埋まったテーブル（検索あたり平均 3.5 回のプローブ） 5 ステップ
テーブルの使用率は75%で、検索1回あたりの探査回数は平均3.5回である。線形探査の標準公式では、その負荷率において2.5回と予測される。どちらが誤っているのかを突き止めよ。
1. どちらも誤ってはおらず、その理由はキーにある。6つのキーそれぞれをテーブル固有の関数でハッシュ化すると、いずれも3を返す。これらは公差8の等差数列であり、テーブルにはちょうど8つのスロットが存在する。
  
  $h (k) = k mod 8 : 3, 11, 19, 27, 35, 43 ⟼ 3, 3, 3, 3, 3, 3$
2. 負荷率は確かに0.75のままである（8つのスロットに6つのキー）。それは単に、キーがどこに入ったかについて何も語っていないだけである。
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
3. したがって、探査列は考えられうる最悪のものとなる。1つ目のキーは空きスロットに入り、2つ目のキーは1スロット進み、3つ目のキーは2スロット進む。6つのキー全体で 1 + 2 + … + 6 = 21 回の探査を要し、そのうち 15 回がパネルの報告する余分な作業である。
  
  $probes = 1, 2, 3, 4, 5, 6 ⟹ \sum = 21, extra = 21 - 6 = 15$
4. これは検索1回あたり平均 3.5 回の探査となる。
  
  $\overset{p}{ˉ} = \frac{21}{6} = 3.5$
5. 教科書の見積もりはキーが一様に分散することを前提としており、α = 0.75 では 2.5 となる。2.5 と 3.5 の差は誤差ではない。テーブルサイズと共通の因数を持つハッシュ関数を、同じく共通の因数を持つキー群に適用したことで生じるコストである。
  
  $\frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5 (random keys) < 3.5$
解答

ツールには α = 0.75、余分な作業として 15 回の探査、そして平均 3.5 回が表示される。ここからの教訓は、負荷率は有名な数値であるものの、それ単独で注視すべきではないということである。ここでの値は、良く分散された6つのキーを保持するテーブル（その場合のコストは 2.5）と全く同じである。変化したのは、キーの集合と法（モジュラス）との相互作用である。これこそがテーブルサイズに素数が選ばれる理由であり、構造体をたまたま容量の倍数になっているフィールドでハッシュ化すると、すべての指標が健全に見えるにもかかわらず O(1) が O(n) に悪化する理由である。サイズを 8 から 7 に変更すれば、平均値が激減することが確認できる。

$\overset{p}{ˉ} = 3.5 observed vs 2.5 predicted : α is not the whole story$
負荷係数0.75でリサイズする実際のハッシュマップ 6 ステップ
パネルは 8 個のスロットに 6 個のキーを入れ、占有率 0.75、探索回数 3.5 と報告します。この占有率での成功探索はおよそ 2.5 回——余裕があります。ではなぜ、現実のハッシュマップはどれも満杯にせず、ちょうど 0.75 でリサイズするのでしょうか。
1. パネルの状態から始めます。4 分の 3 が埋まっていて、メモリの使い方としては妥当に聞こえます。
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
2. 成功探索は安心できる数です。目当てのキーが見つかるまでに、平均しておよそ 2.5 個のスロットを調べるだけ。
  
  $S (α) \approx \frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5$
3. 失敗探索は別の式に従い、その違いに答えのすべてがあります。失敗は「無い」ことを示すために、埋まったスロットの連なりを端まで歩き切らねばならない——だから空き具合の項が線形ではなく 2 乗で効きます。
  
  $U (α) \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) = \frac{1}{2} (1 + 16) = 8.5$
4. 占有率を少し上げて、2 乗が何をするか読み取ってください。0.75 から 0.90 は、埋まり具合の変化としては控えめに聞こえます。
  
  $U (0.90) = \frac{1}{2} (1 + 100) = 50.5, U (0.95) = \frac{1}{2} (1 + 400) = 200.5$
5. 同じ一歩に対する 2 つの増え方を比べます。ヒットの費用は 2 倍を少し超える程度、ミスの費用は 6 倍近くになります。
  
  $α : 0.75 \to 0.90 ⟹ S : 2.5 \to 5.5 (\times 2.2), U : 8.5 \to 50.5 (\times 5.9)$
6. だからテーブルは代わりに倍化します。全キーを再ハッシュするので m 回の操作がかかりますが、次にそれが起きるまでに m 回の挿入を買えます。
  
  $m \to 2 m ⟹ α \to \frac{α}{2}, \frac{m}{m} = O (1)$
解答

ミスは 0.75 で 8.5 回、0.90 で 50.5 回、0.95 では 200.5 回かかります。標準ライブラリが軒並み 0.75 をリサイズのしきい値にしているのはこのためで、メモリと速度の折衷というより、崖の手前の最後の一点だからです。そして効いてくるのはミスのほうです。挿入はまずミスから始まり、見つからない探索はミスだけでできているからです。安心できる 2.5 が語っているのは、そもそも心配していなかった場合のことです。

$U (α) = \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) : 2.5 (0.50), 8.5 (0.75), 50.5 (0.90), 200.5 (0.95)$

学習の道すじ

2つの値が衝突するとき

参考文献 (1)

Hashing, collision resolution and why table size matters, at length: Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.4. Addison-Wesley, 1998. ISBN 978-0-201-89685-5.

42Math チーム · 更新 2026-07-27

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

衝突なし - 大きさ8の表にキー0から5を入れると、六つの異なるスロットに収まり、探査は各一回。衝突はありません。負荷率はすでに0.75です。
全て衝突 - すべてのキーが8の倍数なので、六つともスロット0にハッシュされ、連鎖の長さは六つになります。平均探査回数は3.5回。これが例題の出発点となる値です。
線形探査法 - 3、11、19はいずれもスロット3を、6、14、22はいずれもスロット6を求めます。線形探査では六つすべてを格納でき、探査回数は順に1、2、3、1、2、3回、平均は2回です。
二次探査法 - 同じ六つのキーでも、二次探査では最後の一つを格納できません。平方数を8で割った余りは0、1、4だけなので、スロット6からたどれるのは6、7、2に限られます。スロット0、1、5は空いたままです。