自然数をキーとするデータを，ハッシュ表を用いて管理する。
キーxのハッシュ関数h(x)を
h(x) = x mod n
とすると，任意のキーaとbが衝突する条件はどれか。
ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
正答2
解説
正解は2です。
ハッシュ関数h(x)＝x mod nで、二つのキーが同じ格納位置になる（衝突する）条件を問う問題です。
衝突とは、異なるキーaとbでh(a)＝h(b)となることです。
【選択肢別解説】
1：× a+bがnの倍数でも、余りが等しいとは限りません。
たとえばn＝5、a＝1、b＝4ではa+b＝5ですが、余りは1と4で異なります。
2：○ h(a)＝h(b)はaとbをnで割った余りが等しいことです。
余りが等しければ差a−bはnで割り切れ、逆も成り立ちます。
3：× nがa+bの倍数という条件は、余りの一致と関係がありません。
n＝6、a＝1、b＝2では余りは1と2で異なります。
4：× nがa−bの倍数という条件も誤りです。
n＝6、a＝3、b＝1ではa−b＝2でnは2の倍数ですが、余りは3と1で異なります。
【ポイント】
「余りが等しい」と「差が割る数の倍数」は同じ意味です。
これを合同式でa≡b（mod n）と書きます。