ハッシュ関数が衝突する条件｜科目A-1（応用情報技術者） 令和6年 秋期午前試験 問6
出典：令和6年秋期 午前 問6
分野：アルゴリズムとプログラミング ／ アルゴリズム
自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
h(x) = x mod n
とすると，任意のキーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
h(x) = x mod n
とすると，任意のキーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
- ア：a + bがnの倍数
- イ：a - bがnの倍数
- ウ：nがa + bの倍数
- エ：nがa - bの倍数
TSUNAGARU-ADVICE
まず押さえたいこと
ハッシュ関数がh(x) = x mod nの場合、衝突とは異なるキーaとbをnで割った余りが同じになることです。つまり、a mod n = b mod nとなる条件を考えます。
迷ったときの判断軸
aとbをnで割った余りが同じなら、両者の差a - bはnで割り切れます。例えばn = 10のとき、23と13はどちらも余り3となり、23 - 13 = 10はnの倍数です。「余りが同じ → 差がnの倍数」と覚えると判断しやすくなります。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、ハッシュ表では衝突が起こることを前提に、チェイン法やオープンアドレス法などで処理する点も押さえましょう。探索性能やデータ構造の設計に関する問題につながります。
ハッシュ表で衝突が発生するのは、異なるキーaとbについて、ハッシュ値が同じになる場合です。
したがって、衝突する条件は次のとおりです。
a mod n = b mod n
aとbをnで割った余りが等しいということは、aとbの差がnで割り切れることを意味します。
a - b = nの倍数
例えば、n = 10のとき、a = 23、b = 13なら、どちらも10で割った余りは3であり、差の23 - 13 = 10はnの倍数です。
したがって、イが適切です。
❌他選択肢が誤りの理由ア：a＋bがnの倍数
⇒ハッシュ値が一致する条件は、aとbの和ではなく差に着目します。a + bがnの倍数でも、aとbをnで割った余りが同じとは限りません。
ウ：nがa＋bの倍数
⇒a + bとnの倍数関係は、ハッシュ値の一致を保証しません。衝突の条件とは関係ありません。
エ：nがa－bの倍数
⇒必要なのは「a - bがnの倍数」であり、倍数関係が逆です。「nがa - bの倍数」では衝突の条件になりません。