最終更新日：2026年8月18日
fe fe-technology algorithm
まず結論
ハッシュ表の衝突（collision）とは、異なるデータから同じハッシュ値が求められ、同じ格納位置を使おうとすることです。
FE試験では、次の流れで判断すると分かりやすいです。
データを順番に見る
↓
ハッシュ値を求める
↓
過去に出たハッシュ値か確認
↓
初めて同じ値が出たところ
→ 最初の衝突
同じデータだから衝突するのではなく、同じハッシュ値になったら衝突する。
直感的な説明
8個の箱が並んでいるとします。
0 1 2 3 4 5 6 7
データをどの箱に入れるかを、次の式で決めます。
h(x) = x mod 8
たとえば、18なら、
18 mod 8 = 2
なので、箱2へ入れます。
次に26を入れると、
26 mod 8 = 2
となります。
18と26は別のデータですが、どちらも箱2を使おうとします。
18 → 2
26 → 2
同じハッシュ値
→ 衝突
これがハッシュ表の衝突です。
定義・仕組み
ハッシュ表とは
ハッシュ表は、データから計算したハッシュ値を使って、格納位置を決めるデータ構造です。
データを一つずつ先頭から探すのではなく、ハッシュ値から格納位置をすばやく決められるのが特徴です。
データ
↓
ハッシュ関数
↓
ハッシュ値
↓
格納位置
ハッシュ関数とは
ハッシュ関数は、データからハッシュ値を計算する関数です。
FE試験では、次のように余りを使う形がよく出ます。
h(x) = x mod n
mod は、割り算の余りを表します。
25 mod 7 = 4
これは、25を7で割った余りが4という意味です。
衝突とは
ハッシュ関数を使っても、異なるデータから同じハッシュ値が出ることがあります。
11 mod 7 = 4
25 mod 7 = 4
11と25は異なるデータですが、ハッシュ値はどちらも4です。
このような状態が衝突です。
科目Aでどう出る？
科目Aでは、複数のデータを順番にハッシュ表へ入れ、最初に衝突するデータを選ばせる問題が出ます。
基本の解き方
たとえば、
11, 25, 18, 30, 33
をこの順で、
h(x) = x mod 7
で格納するとします。
順番に計算します。
| データ | ハッシュ値 |
|---|---|
| 11 | 4 |
| 25 | 4 |
25のハッシュ値4は、11ですでに使われています。
したがって、25で最初の衝突が起こります。
「最初に衝突する」ときは、全データを最後まで計算せず、同じハッシュ値が再登場したところで止めます。
16進数とmod 8のショートカット
16進数の値に対して mod 8 を求める問題では、すべてを10進数へ変換しなくても求められる場合があります。
16進数 XY は、
16 × X + Y
と表せます。
ここで、16は8で割り切れるので、
(16 × X + Y) mod 8
では、上位桁の 16 × X は余りに影響しません。
そのため、下1桁だけ見ればよいことがあります。
たとえば、
1A
→ A = 10
→ 10 mod 8 = 2
B2
→ 2 mod 8 = 2
なので、1A と B2 は同じハッシュ値になります。
どんな場面で使う？
ハッシュ表は、キーから対応する値を高速に検索したい場面で使われます。
たとえば、
- 会員番号から会員情報を探す
- 商品コードから商品データを探す
- 文字列から登録済み情報を探す
- 辞書型や連想配列を実装する
といった場面です。
Pythonのdictのような連想配列も、ハッシュを利用する代表例です。
よくある誤解・混同
同じデータが入ったら衝突する
衝突のポイントは、データそのものが同じかどうかではありません。
異なるデータ
↓
同じハッシュ値
↓
衝突
ハッシュ値は必ず異なる
違います。
限られた数の格納位置へ多数のデータを対応させるため、異なるデータから同じハッシュ値が出る可能性があります。
最初の衝突は、最初のデータを見る
違います。
1件目には、まだ比較対象となる格納済みデータがありません。
2件目以降について、過去に出たハッシュ値と同じかを確認します。
衝突したらハッシュ表は使えない
違います。
実際のハッシュ表では、衝突が起きたときの処理方法を用意します。
代表的な方式には、
- チェイン法
- オープンアドレス法
などがあります。
FE試験では、問題文で衝突時の処理方法まで指定されている場合に、そのルールに従います。
確認問題（FE試験対策）
10進数のデータを次の順番でハッシュ表へ格納する。
11, 25, 18, 30, 33
ハッシュ関数を、
h(x) = x mod 7
とする。
最初に衝突するデータはどれか。
- ア. 25
- イ. 18
- ウ. 30
- エ. 33
▶ クリックして答えと解説を見る（ここを開く）
正解：ア
順番にハッシュ値を求めます。
11 mod 7 = 4
25 mod 7 = 4
11ですでにハッシュ値4を使用しているため、25を入れようとした時点で最初の衝突が起こります。
👉 判断ポイント
過去に出たハッシュ値が初めて再登場したデータを探すと考えます。
まとめ（試験直前用）
- ハッシュ表は、ハッシュ値から格納位置を決める
modは割り算の余り- 異なるデータでも同じハッシュ値なら衝突する
- 「最初の衝突」は、順番に計算して同じ値が初めて再登場したところ
mod 8と16進数の組合せでは、下1桁だけで判断できる場合がある- 衝突時にはチェイン法やオープンアドレス法などで対応する
データが同じかではなく、ハッシュ値が同じかを見る。