ハッシュ値が衝突する条件
出典: 令和4年度 秋期 応用情報技術者試験 午前 問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 は 5 の倍数ですが、余りは 1 と 4 で衝突しません。
- イ: a と b を n で割った余りが等しいとき、a − b は n の倍数になるので正しい答えです。
- ウ: n が a ＋ b の倍数かどうかは、余りが等しいかどうかとは関係ありません。
- エ: n が a − b の倍数 (a − b が n の約数) でも、例えば a ＝ 3、b ＝ 1、n ＝ 4 では余りは 3 と 1 で衝突しません。
ポイント
- 衝突するのは h(a) ＝ h(b)、つまり a と b を n で割った余りが等しい ときです。
- 余りが等しければ、差 a − b は余りの部分が打ち消し合って n の倍数 になります。
- 例: n ＝ 5、a ＝ 12、b ＝ 7 → どちらも余り 2、差は 5 (5 の倍数)。