ハッシュ関数で衝突する条件
出典: 平成27年度 春期 応用情報技術者試験 午前 問5 (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 = 1, b = 4, n = 5 だと a ＋ b = 5 ですが、余りは 1 と 4 で衝突しません。
- イ: 余りが等しいことと、差が n で割り切れることは同じなので正しい答えです。
- ウ: n が a ＋ b の倍数でも、余りが等しいとは限りません。
- エ: n が a − b の倍数 (a − b が n の約数) でも、余りが等しいとは限りません。逆です。
ポイント
- 衝突は h(a) = h(b)、つまり a と b を n で割った余りが等しいときに起きます。
- 余りが等しいとき、a − b は n で割り切れます。よって a − b が n の倍数 です。
例: n = 5 のとき、a = 12、b = 7 はどちらも余り 2 で、12 − 7 = 5 です。