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