ハッシュ関数の衝突条件

正解は イ です。 ハッシュ表において2つのキー $a$ と $b$ が衝突する条件は、$h(a) = h(b)$、すなわち $a$ と $b$ を $n$ で割った余りが等しいことです。 商をそれぞれ整数 $k, l$、共通の余りを $r$（$0 \leqq r < n$）とおくと： $$a = k \cdot n + r$$ $$b = l \cdot n + r$$ 両式の差をとると： $$a - b = (k - l) \cdot n$$ $k, l$ は整数であるため、$k - l$ も整数となり、$a - b$ は $n$ の整数倍となります。 したがって、キー $a$ と $b$ が衝突する条件は「$a - b$ が $n$ の倍数」です。 $a + b = (k + l)n + 2r$ となり、余りの和 $2r$ がたまたま $n$ の倍数になる場合しか成り立たず、余りが等しいことの条件ではありません。 「$n$ が $a + b$ の倍数」は、$a + b$ が $n$ の約数であることを意味し、余りが等しい条件とは無関係です。 「$n$ が $a - b$ の倍数」は、主語と目的語が逆であり、$a - b$ が $n$ の約数であることを表しているため誤りです。 例（n＝7） a mod 7 b mod 7 a−b 衝突 a＝10, b＝3 3 3 7（7の倍数） ○ a＝10, b＝4 3 4 6 ×（a＋b＝14 は7の倍数だが衝突しない）

自然数をキーとするデータを，ハッシュ表を用いて管理する。キー xx のハッシュ関数 h(x)h(x) を

h(x)=x mod nh(x) = x \bmod n

とすると，任意のキー aa と bb が衝突する条件はどれか。ここで，nn はハッシュ表の大きさであり，x mod nx \bmod n は xx を nn で割った余りを表す。

出典令和4年度 秋期 高度情報処理技術者試験 午前Ⅰ 問3
ア
a+ba+b が nn の倍数
イ
a−ba-b が nn の倍数
ウ
nn が a+ba+b の倍数
エ
nn が a−ba-b の倍数