ハッシュ値が衝突する除数
出典: 平成30年度 秋期 応用情報技術者試験 午前 問27 (IPA)
自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ 571，1168，1566 である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
- ア 193
- イ 197
- ウ 199
- エ 211
正解と解説を見る
正解: ウ
- ア: 597 も 398 も 193 では割り切れないので、衝突しません。
- イ: 597 も 398 も 197 では割り切れないので、衝突しません。
- ウ: キーの差 597 と 398 をどちらも割り切るのは 199 なので正しい答えです (どのキーも余り 173)。
- エ: 597 も 398 も 211 では割り切れないので、衝突しません。
ポイント
- 3 つのキーを同じ除数で割った余りが等しいとき、キーどうしの差は除数で割り切れます。
- 1,168 − 571 = 597 = 3 × 199、1,566 − 1,168 = 398 = 2 × 199
- 両方を割り切るのは 199 なので、除数は 199 です。