ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

ハッシュテーブル

回 2-7　道 2 データ構造とアルゴリズム

ハッシュテーブルは、鍵 (キー) から計算したハッシュ値で入れ場所 (バケツ) を決め、その場所だけを見て値を取り出すデータの置き方です。鍵がばらけていれば件数が増えても見る所はほぼ 1 か所ですが、別の鍵が同じ場所に重なる「衝突」が続くと、重なった鍵を 1 つずつ比べることになります。全部の鍵が同じハッシュ値になると、1000 件を入れるだけで 499500 回比べ、件数の 2 乗の形で遅くなります。

目安 50 分2-7 (2-0〜2-10 の中)

読み終えたら衝突が多いと遅くなる理由を、実際に起きた事例で説明できる

この頁の流れ

  1. 1名前から電話番号を、端から探さずに引けるか
  2. 2ハッシュテーブルはどう動くのか
  3. 3動かして確かめる
  4. 4衝突が重なると、なぜ遅くなるのか
  5. 5ハッシュテーブルは仕事でどう確かめるのか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10もっと深く
  11. 11一次資料
  12. 12次へ

鍵から入れ場所を計算するしくみと、衝突が重なると一気に引けなくなる理由を、比べた回数で切り分けられるようになります。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

名前から電話番号を、端から探さずに引けるか

引けます。名前から「どの棚に入れたか」を計算で決めておけば、探すときも同じ計算をして、その棚だけを開ければ済みます。このしくみがハッシュテーブルで、ハッシュ表とも呼びます。

端から見る線形探索では、1000 人の名簿なら最悪 1000 人を見ます。並べておけば二分探索も使えますが、並べる手間がかかります。

ハッシュテーブルは、名前を数に変える決まった計算 (ハッシュ関数) で出た数 (ハッシュ値) から棚の番号を決めます。

ただし、別の名前が同じ棚に入る衝突が起きます。この回では、衝突が重なると急に遅くなる理由を比べた回数で確かめ、その弱点で Web サーバーが止まり得ると公表された 2011 年の事例を読みます。

鍵から棚番号を計算してその棚だけを開ける様子と、端から 1 つずつ開ける様子を比べた図

ハッシュテーブルはどう動くのか

ハッシュテーブルは、鍵をハッシュ値に変え、ハッシュ値をバケツの数で割った余りを入れ場所にします。同じ鍵からは必ず同じ場所が出るので、探すときもその場所だけを見れば済みます。

鍵からハッシュ値、ハッシュ値から入れ場所

ハッシュテーブルの中身は、バケツ (値を入れる箱) を並べた配列です。入れ場所は次の 2 段で決めます。

  1. ハッシュ関数で、鍵をハッシュ値 (整数) に変える
  2. ハッシュ値をバケツの数で割り、余りをバケツの番号にする

Python では hash() がハッシュ値を返し、小さい整数ならハッシュ値は数そのものです。バケツが 8 個なら、鍵 12 は 8 で割った余りの 4 番、鍵 33 は 1 番に入ります。

ハッシュ値の目的は、文字列でも日付でも、どんな鍵も配列の位置に使える番号に変えることです。

衝突は避けられない

別の鍵が同じバケツに入ることを衝突と呼びます。バケツが 8 個なら、鍵 12 と鍵 20 はどちらも 8 で割った余りが 4 なので、同じ 4 番に入ります。

鍵の種類は無数にあり、バケツの数は限られるので、衝突はゼロにできません。衝突の扱い方の代表は次の 2 つです。

扱い方衝突したとき探すとき
チェイン法 (つなぐ)同じバケツに列をつくってつなぐその列を先頭から比べる
オープンアドレス法 (空きを探す)決まった順で次の空きバケツを探して入れる同じ順で、見つかるか空きに当たるまで比べる

どちらでも、重なった鍵は 1 つずつ比べるしかなく、衝突が 1 か所に集まるほど比べる回数が増えます。

ハッシュと衝突

詰まり具合と広げ直し

詰まり具合 (load factor、ロードファクター) は、入っている件数をバケツの数で割った値です。1000 件を 500 個のバケツに入れると、詰まり具合は 2 で、1 つのバケツに平均 2 件が重なります。

詰まり具合が上がると衝突が増えて遅くなり、下げるとメモリがむだになります。そこで、詰まり具合が決めた値を超えたら、バケツを増やした配列を作って全部の鍵を入れ直します。これを広げ直し (リハッシュ) と呼びます。

Java の HashMap の公式文書は、既定の上限を 0.75 とし、件数がバケツの数の 0.75 倍を超えるとバケツをおよそ 2 倍にして入れ直すと書いています。

Python の dict と set もハッシュテーブル

Python の dict (辞書) と set (集合) は、中身がハッシュテーブルです。公式の FAQ は、CPython の辞書を「大きさを変えられるハッシュテーブル」と書いています。

公式文書の計算量の表では、dict の取り出しや入れるは平均 O(1) ですが、全部の鍵が同じハッシュ値になる最悪では O(n) になると書いてあります。set も同じです。

探し方前提1 件を探す手間
線形探索なしO(n)
二分探索並んでいるO(log n)
ハッシュテーブル鍵がばらける平均 O(1)、最悪 O(n)

動かして確かめる

1 本目は、バケツ 8 個のハッシュテーブルをチェイン法で作り、7 つの鍵を入れます。そのあと 4 つの鍵を探し、見つかった値と、列の中で比べた回数を出します。

動かす バケツ 8 個のハッシュテーブル

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

hash(12) 12
0 []
1 [33, 41]
2 []
3 []
4 [12, 20, 28, 4]
5 []
6 []
7 [7]
get 33 (330, 1)
get 7 (70, 1)
get 4 (40, 4)
get 36 (None, 4)

hash(12) は 12 で、小さい整数の鍵はハッシュ値が数そのものです。12、20、28、4 は 8 で割った余りがどれも 4 なので、4 番のバケツに 4 件が重なりました。33 と 41 も 1 番で衝突しています。

33 と 7 は 1 回で見つかり、列の後ろにある 4 は 4 回比べました。無い鍵 36 も 4 番の列を全部比べ、4 回で「無い」と分かりました。衝突した所だけが遅くなります。

2 本目は、散らした 1000 個の鍵を、バケツの数を変えて入れます。出力は左から、バケツの数、詰まり具合、入っている鍵を探す平均の比べた回数、いちばん長い列です。数え方は 1 本目と同じで、列の j 番目の鍵は j 回で見つかります。

動かす 詰まり具合と比べた回数

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

2000 0.5 1.236 4
1000 1.0 1.483 5
500 2.0 1.965 7
250 4.0 2.983 12
125 8.0 4.987 18

詰まり具合が 0.5 なら、平均 1.236 回で見つかります。詰まり具合を 8 まで上げると平均 4.987 回、いちばん長い列は 18 件です。広げ直しは、詰まり具合を低く保ち、平均の回数を 1 回に近いままにする仕組みです。

衝突が重なると、なぜ遅くなるのか

全部の鍵が同じハッシュ値になると、全部が 1 つのバケツに重なり、ハッシュテーブルは端から比べるだけの列と同じになります。1 件入れるたびに、すでに入っている鍵と 1 つずつ比べるので、n 件を入れ終えるまでに比べる回数は 0 + 1 + 2 + … + (n − 1) = n(n − 1) / 2 回です。

次のコードは、ハッシュ値を自由に決められる鍵を作り、Python の本物の dict に入れます。「ばらばら」は鍵ごとに違う値、「同じ」は全部 0 です。比べた回数は == (__eq__) が呼ばれた回数で、出力は左から、件数、ばらばら、同じ、n(n − 1) / 2 の値です。

動かす 全部同じハッシュ値の鍵

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

250 0 31125 31125
500 0 124750 124750
1000 0 499500 499500

ハッシュ値がばらばらなら、1000 件入れても == は 0 回でした。

全部同じだと、250 件で 31125 回、1000 件で 499500 回比べ、どれも n(n − 1) / 2 と同じでした。件数が 2 倍でほぼ 4 倍になる、件数の 2 乗の形です。Python の公式文書も、辞書を作る最悪の手間を O(n²) と書いています。

外の誰かが同じハッシュ値になる鍵をわざと選べると、この「同じ」の行を本番で起こせます。次の節の事例が、まさにそれです。

ハッシュテーブルは仕事でどう確かめるのか

仕事では、言語の dict や set を使い、鍵が外から来るかと件数の上限を確かめます。

  1. 「すでにあるか」を何度も聞くなら、端から比べる list ではなく set や dict を使う
  2. 自分で __hash__ を書いた型は、違う鍵が違うハッシュ値になるかを試験で見る
  3. 鍵が外から来るなら、受け取る件数に上限を置く (次の節の PHP の max_input_vars)
  4. ハッシュ値を外から読めない言語の版を使う。Python 3.3 から文字列のハッシュ値は起動ごとに変わる

データベースの索引にもハッシュがあります。PostgreSQL の公式文書によると、ハッシュの索引は「等しい」の比べだけを扱うので、範囲で探すなら B-tree の索引を選びます。

面接の「合計が目標になる 2 つ」も、dict で 1 周すれば解けます。数を見るたびに「目標から引いた残り」が辞書にあるかを聞き、無ければ自分を入れます。

動かす 合計が目標になる 2 つ

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

[0, 1]
[1, 3]
None
[0, 1]

目標 22 は 7 と 15 で [1, 3] です。目標 4 は 2 を 2 回使わないと作れないので None で、探してから入れる順なので自分自身とは組みません。

探してから登録する

関わる実例

ハッシュの衝突を狙って Web サーバーを止める HashDoS (2011年12月28日)

2011年12月28日、28C3 (第 28 回 Chaos Communication Congress) で Alexander Klink が「Effective Denial of Service attacks against web application platforms」を発表しました。1 回の HTTP の要求で、サーバーの CPU を数分から数時間 99% 使わせられるという内容です。

同じ日の告知 oCERT-2011-003 は、Java、PHP、Python、Ruby などのハッシュの表が予測できる衝突を突かれると CPU を 100% 使い、POST の引数の数に上限が無いと特に危ないと書いています。2003 年に Perl で報告された弱点とほぼ同じだとも書いています。告知の Credit の欄には、弱点の報告と試しのコードを Alexander Klink と Julian Waelde (Wälde) から受け取ったとあります。

Web のサーバーは、フォームの引数を言語のハッシュの表に入れてからプログラムに渡します。引数の名前 (鍵) は送る側が自由に選べるので、同じハッシュ値になる名前を大量に送ると、上の「同じ」の行がプログラムが動く前に起きます。

各言語の対応は次の通りです。

  • PHP は CVE-2011-4885 です。2012年1月10日の 5.3.9 で、受け取る引数の数の上限 max_input_vars が足されました。公式文書の既定の値は 1000 です
  • Python は CVE-2012-1150 です。2.6.8、2.7.3、3.1.5、3.2.3 で、文字列のハッシュ値に起動ごとの乱数を混ぜる「ハッシュのランダム化」が -R で使えるようになりました。辞書の並び順に頼るコードが多いため、既定は切ってありました
  • Python 3.3 から、ハッシュのランダム化は既定で有効です。値を固定したいときは環境変数 PYTHONHASHSEED に数を入れます
  • 混ぜた乱数を外から割り出せると示され、PEP 456 (Python 3.4) で文字列のハッシュ関数を、秘密の値を持つ SipHash に替えました

崩れた前提は「鍵はばらける」と「鍵を選ぶのはこちらだ」です。平均 O(1) は鍵がばらける仮定の上の数で、外の誰かが鍵を選べると、最悪の O(n²) が本番の障害になりました。

出典は oCERT-2011-003 (oCERT) と 28C3 の発表の頁 (Chaos Computer Club) です。

よくある問い

HashMap や連想配列とハッシュテーブルは違うものですか

連想配列は「鍵から値を引ける入れ物」という使い方の名前で、ハッシュテーブルはそれを作るやり方の 1 つです。Java の HashMap も Python の dict も、中身はハッシュテーブルです。

チェイン法とオープンアドレス法はどちらが良いのですか

詰まり具合を低く保てば、どちらも平均でほぼ 1 回の比べで済みます。チェイン法は列を伸ばせるので詰まり具合が 1 を超えても動き、オープンアドレス法は配列 1 本で済む代わりに空きが要ります。重なった鍵を 1 つずつ比べる弱点はどちらも同じです。

パスワードを守るハッシュと同じものですか

同じ「鍵を数に変える関数」ですが、求める性質が違います。表のハッシュは速くばらけることが大事で、Python の hash() の値は、公式文書によると 64 ビットの版でふつう 8 バイト、32 ビットの版で 4 バイトの大きさに収まります。パスワードを守るハッシュは、値から元へ戻せないことが大事です。

Python の dict は入れた順を覚えていますか

覚えています。公式文書は、Python 3.7 から辞書は入れた順を保つと決めたと書いています。一方 set の並び順は約束されておらず、文字列のハッシュ値が起動ごとに変わると並びも変わることがあります。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。4 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

ハッシュテーブルで、別の鍵が同じバケツに入ることを何と呼びますか。

2 問目

このコードを動かすと何が出ますか。

バケツごとに数える

d = {}
for k in [5, 13, 21, 2]:
    i = k % 8
    d[i] = d.get(i, 0) + 1
print(d)

3 問目

全部の鍵が同じハッシュ値になる 1000 件を Python の dict に入れると、鍵どうしを比べる回数は上のコードで何回でしたか。

4 問目

2011年12月に公表された HashDoS で、Web のサーバーが遅くなった直接の理由はどれですか。

説明課題

ハッシュテーブルで衝突が多いと遅くなる理由を、「同じバケツ」「1 つずつ比べる」「HashDoS」という言葉を使って、3〜4 文で説明してください。書いたら、下の模範解答を開いて比べてください。

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

辞書や連想配列は毎日のように使う道具で、衝突で遅くなる仕組みを知っていると、外から届く鍵をそのまま入れる危うさに気づけます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

もっと深く

この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

次へ

前の回 2-6木と二分探索木たどる順、片寄り次の回 2-8ダイクストラ法と最短経路点と線、幅優先、重みのある道

道 2 データ構造とアルゴリズムの回

  1. 2-0アルゴリズムとは順次、分岐、反復の 3 つで書く手順頁で読む
  2. 2-1線形探索と二分探索100 万件でも 20 回で見つかる頁で読む
  3. 2-2バブルソートと挿入・選択ソート遅いソート 3 つ、2 倍で約 4 倍頁で読む
  4. 2-3クイックソートとマージソート速いソート 2 つ、平均と最悪頁で読む
  5. 2-4スタックとキュー積む順と並ぶ順頁で読む
  6. 2-5再帰自分を呼んで小さくする頁で読む
  7. 2-6木と二分探索木たどる順、片寄り頁で読む
  8. 2-7ハッシュテーブル鍵から一気に引く、衝突この回
  9. 2-8ダイクストラ法と最短経路点と線、幅優先、重みのある道頁で読む
  10. 2-9動的計画法同じ計算を 2 度しない頁で読む
  11. 2-10試験と面接で確かめる基本情報 科目B、道場 10 問、面接 20 問頁で読む

道 2 の頁へ戻るほかの道を見る