ハッシュ表とは（全体像）
ハッシュ表は、「キー（名前）」と「値」をペアで持ち、キーから一発で値を取り出せるしくみ。プログラミング言語の「辞書（dict）」「連想配列」の正体だ。
カギになるのがハッシュ関数。キーを入れると「何番の棚に置くか」を計算してくれる。だから、先頭から順に探さなくても、計算した番号の棚を直接見るだけで済む——これが速さの理由（平均O(1)）だ。
ただし、ここで避けられない問題が起きる。
- 衝突 … 別のキーなのに、計算結果（置き場所）がたまたま同じになること。
棚の数よりキーの種類のほうが多いので、衝突は必ず起きる（理屈のうえで避けられない）。だから「衝突をどう処理するか」がハッシュ表の肝になる。
詳しく：衝突対応2方式と平均O(1)だけ覚えれば戦える
ここが記事の心臓部。まずは衝突への対応2方式。
衝突対応の2方式
| 方式 | やり方 |
|---|---|
| チェイン法 | 同じ場所に、リストで数珠つなぎにぶら下げる |
| オープンアドレス法 | 別の空いている場所を、決めた規則で探す |
チェイン法は、同じ棚に複数のキーが来たら、そこにリストでつなげてしまう方法。オープンアドレス法は、ぶつかったら別の空き棚を探して置く方法（探し方には「1つ隣」「飛び飛び」などのルールがある）。
次に、混み具合を表す負荷率。
負荷率と速さ
| 項目 | 内容 |
|---|---|
| 負荷率 | 入っている数 ÷ 棚の数（混み具合） |
| 目安 | だいたい0.7以下に保つ |
| 超えたら | 棚を増やして入れ直す（再ハッシュ） |
負荷率が高い（混んでいる）ほど衝突が増えて遅くなる。だから0.7くらいを目安に保ち、超えたら棚を増やす（再ハッシュ）。つまり、混みすぎる前に棚を増やしておくのが速さを保つコツ、というわけだね。
そして速さの注意点。ハッシュ表は平均ではO(1)（一発）だが、衝突が集中する最悪の場合はO(n)（先頭から探すのと同じ）まで遅くなりうる。「つねに一発」ではない、と押さえておく。
わかりやすく言い換えると
要するに、ハッシュ表は「名前から棚番号を計算して、直接その棚を見る下駄箱」だ。
①ハッシュ関数 … 「田中さんは7番」と名前から棚番号を計算する係
②衝突 … 「田中さん」と「鈴木さん」がたまたま同じ7番になること
③対応 … 7番に2人ぶんの場所をつなげる（チェイン法）か、空いている別の棚へ回す（オープンアドレス法）
棚番号が一発で分かるから速い。でも同じ番号が重なる（衝突する）ことは避けられないので、その処理を決めておく——というわけだね。
試験のツボ
🔴 一番出る：衝突は必ず起きる・対応2方式
①別のキーが同じ場所を指す衝突は避けられない
②チェイン法（同じ場所にリストでつなぐ）
③オープンアドレス法（別の空き場所を探す）
🔴 次に出る：速さは平均O(1)（最悪O(n)）
①ふつうは一発で出し入れできる（平均O(1)）
②衝突が集中すると最悪O(n)まで遅くなる
🟡 押さえると安定：負荷率
①負荷率＝入っている数÷棚の数（混み具合）
②0.7くらいを目安に保ち、超えたら再ハッシュ
よくある間違い
①「ハッシュ表では衝突は起きない」→ ✗ 棚よりキーの種類が多いので、衝突は必ず起きる。だから対応方式がある。
②「ハッシュ表はどんなときも必ずO(1)で取り出せる」→ ✗ 平均はO(1)だが、衝突が集中する最悪の場合はO(n)になる。
③「負荷率が高い（混んでいる）ほど速くなる」→ ✗ 逆。混むほど衝突が増えて遅くなる。0.7くらいを目安に保つ。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（衝突）
ハッシュ表の衝突に関する次の記述のうち、正しいものはどれか。
- ハッシュ関数を工夫すれば、衝突をいっさい起こさないようにできるものである
- 衝突はプログラムのバグが原因で起こるので、正しく書けば発生しないものだ
- 衝突が起きるとデータが消えるため、ハッシュ表は実用では使われないものだ
- 別のキーが同じ場所を指す衝突は避けられず、対応方式を用意して処理を行う
解答は 4 だよ。
棚の数よりキーの種類のほうが多いから、衝突は必ず起きる（避けられない）んだ。だからチェイン法やオープンアドレス法といった対応方式を用意しておくよ。
選択肢1は「いっさい起こさない」が誤り。選択肢2は「バグが原因」が誤り。選択肢3は「データが消える・使われない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 衝突は避けられない |
| 2 | ✗ | バグではなく必然 |
| 3 | ✗ | 対応方式で処理でき実用的 |
| 4 | ✓ | 衝突は避けられず対応方式で処理 |
オリジナル問題2（対応方式）
ハッシュ表の衝突対応に関する次の記述のうち、正しいものはどれか。
- チェイン法は衝突した要素を消し、オープンアドレス法は上書きする方式である
- チェイン法は同じ場所にリストでつなぎ、オープンアドレス法は空き場所を探す
- チェイン法もオープンアドレス法も、衝突した要素をすべて捨てる方式である
- チェイン法は別の空き場所を探し、オープンアドレス法はリストでつなぐ方式だ
解答は 2 だよ。
チェイン法は同じ場所にリストでつなぎ、オープンアドレス法は別の空き場所を探すんだ。どちらも要素を捨てずにちゃんと保管するよ。
選択肢1・3は「消す・捨てる」が誤り。選択肢4はチェイン法とオープンアドレス法のやり方が逆だよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 要素は消さない |
| 2 | ✓ | チェイン＝つなぐ・オープン＝別の場所 |
| 3 | ✗ | 要素を捨てない |
| 4 | ✗ | 2方式のやり方が逆 |
オリジナル問題3（計算量）
ハッシュ表の検索の速さに関する次の記述のうち、正しいものはどれか。
- ハッシュ表はどんなときも必ずO(1)で、最悪の場合でも遅くならないものである
- ハッシュ表は平均でO(n)と遅く、配列の先頭から探すのと変わらないものだ
- ハッシュ表は平均でO(1)と速いが、衝突が集中する最悪の場合はO(n)になる
- ハッシュ表は負荷率が高い（混んでいる）ほど、検索が速くなる性質を持つ
解答は 3 だよ。
ハッシュ表は平均ではO(1)で速いけれど、衝突が集中する最悪の場合はO(n)まで遅くなるんだ。「つねに一発」ではない、ってところがポイントだよ。
選択肢1は「最悪でも遅くならない」が誤り。選択肢2は「平均O(n)」が誤り（平均はO(1)）。選択肢4は「混むほど速い」が逆だよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 最悪はO(n)になりうる |
| 2 | ✗ | 平均はO(1)で速い |
| 3 | ✓ | 平均O(1)・最悪O(n) |
| 4 | ✗ | 混むほど遅くなる |
まとめ
押さえどころ
- 🔴 衝突と対応 ＝ 衝突は必ず起きる。チェイン法（リストでつなぐ）／オープンアドレス法（別の空き場所）。
- 🔴 計算量 ＝ 平均O(1)で速いが、衝突が集中する最悪の場合はO(n)。
- 🟡 負荷率 ＝ 入っている数÷棚の数。0.7くらいを目安に保ち、超えたら再ハッシュ。
次に学ぶ
- 配列・リスト ── ハッシュ表の棚（スロット）の土台になる基本データ構造。番号アクセスの速さがハッシュの速さにつながる。
- 計算量（オーダー） ── 平均O(1)・最悪O(n)の意味をはっきりさせる考え方。ハッシュ表の速さを正しく評価できる。
執筆: SikakuQuest編集部