ハッシュ値が衝突する条件
出典: 令和6年度 秋期 応用情報技術者試験 午前 問6 (IPA)
自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を 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 の倍数
正解と解説を見る
正解: イ
- ア: a＋b が n の倍数でも、余りが等しいとは限りません。例: n = 5、a = 1、b = 4 は和が 5 ですが余りは 1 と 4 です。
- イ: a と b を n で割った余りが等しいことは、a−b が n の倍数であることと同じなので正しい答えです。
- ウ: n が a＋b の倍数かどうかは、余りが等しいかどうかとは関係ありません。
- エ: 「n が a−b の倍数」は逆の関係です。正しくは「a−b が n の倍数」です。
ポイント
- 衝突とは、異なるキーが同じハッシュ値になることです。
- a mod n ＝ b mod n (n で割った余りが等しい) ⇔ a − b が n で割り切れる (n の倍数) です。
- 例: n = 5 のとき、a = 13、b = 8 はどちらも余り 3 で、13 − 8 = 5 は 5 の倍数です。