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