自然数を除数とした剰余を返すハッシュ関数がある。
値がそれぞれ571，1168，1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。
このとき使用した除数は幾つか。
正答3
解説
正解は3です。
この問題は、3つのキー値を同じ除数で割った余り（ハッシュ値）が全て等しくなる除数を求めるものです。
2つの数を除数で割った余りが等しいとき、その2つの数の差は除数で割り切れます。
【計算】
1168－571 ＝ 597 です。
1566－1168 ＝ 398 です。
597 ＝ 3×199、398 ＝ 2×199 なので、どちらも199で割り切れます。
確認すると、571 ＝ 199×2＋173 で余りは173です。
1168 ＝ 199×5＋173 で余りは173です。
1566 ＝ 199×7＋173 で余りは173です。
3つとも余りが173で一致するので、除数は199です。
【選択肢別解説】
1：× 差の597を193で割ると3余り18で、割り切れません。
そのため571と1168の余りは一致せず、衝突は起きません。
2：× 差の597を197で割ると3余り6で、割り切れません。
そのため571と1168の余りは一致しません。
3：○ 差の597と398がともに199で割り切れ、3つのキー値の余りが全て173になります。
4：× 差の597を211で割ると2余り175で、割り切れません。
そのため571と1168の余りは一致しません。
【ポイント】
「余りが等しい」ことは「差が除数で割り切れる」ことと同じです。
選択肢の数で差を割ってみると、3つの数をそれぞれ割り算するより速く解けます。