自然数をキーとするデータを，ハッシュ表を用いて管理する。
キーxのハッシュ関数h(x)を
h(x) = x mod n
とすると，任意のキーaとbが衝突する条件はどれか。
ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
正答2
解説
正解は2です。
衝突（シノニム）とは、異なるキーのハッシュ値が等しくなることです。
h(a)＝h(b)、つまりaとbをnで割った余りが等しくなる条件を求めます。
【選択肢別解説】
1：× 和がnの倍数でも、余りが等しいとは限りません。
例えばn＝5、a＝1、b＝4では和が5ですが、余りは1と4で異なります。
2：○ aとbの余りが等しければ、差a−bはnで割り切れます。
逆に差がnの倍数なら余りも等しくなるので、これが衝突の必要十分条件です。
3：× nがa＋bの倍数かどうかは、余りの一致とは無関係です。
例えばn＝6、a＝1、b＝2では、6は3の倍数ですが余りは1と2で異なります。
4：× nがa−bの倍数という関係は、条件が逆向きです。
例えばn＝6、a＝5、b＝2では、6は3の倍数ですが余りは5と2で異なります。
【ポイント】
「余りが等しい」は「差が割る数の倍数」と言い換えられます。
これは合同式a≡b（mod n）の定義と同じです。