令和4年度 秋期 応用情報技術者試験 午前 問5

ハッシュ表において、異なるキーからハッシュ関数によって同じハッシュ値が算出されることを衝突（シノニム）と呼びます。

今回のハッシュ関数は $h(x) = x \bmod n$ と定義されています。
したがって、任意のキー $a$ と $b$ が衝突する条件は、$h(a) = h(b)$ すなわち $a \bmod n = b \bmod n$ が成り立つことです。
これは、「$a$ を $n$ で割った余り」と「$b$ を $n$ で割った余り」が等しいことを意味します。

2つの自然数を同じ数で割った余りが等しい場合、その2つの数の差は必ず割る数の倍数になります。
よって、$a - b$（または $b - a$）は $n$ の倍数となります。

各選択肢の解説

• ア: 「$a+b$ が $n$ の倍数」は誤りです。例えば $n=10, a=3, b=7$ の場合、$a+b=10$ で $n$ の倍数になりますが、$3 \bmod 10 = 3$、$7 \bmod 10 = 7$ となりハッシュ値は異なり、衝突しません。
• イ: 「$a-b$ が $n$ の倍数」は正しいです。これがハッシュ値が衝突する条件です。
• ウ: 「$n$ が $a+b$ の倍数」は誤りです。例えば $n=10, a=2, b=3$ の場合、$a+b=5$ で $n(10)$ は $a+b(5)$ の倍数になりますが、$2 \bmod 10 = 2$、$3 \bmod 10 = 3$ となり衝突しません。
• エ: 「$n$ が $a-b$ の倍数」は誤りです。例えば $n=10, a=7, b=2$ の場合、$a-b=5$ で $n(10)$ は $a-b(5)$ の倍数になりますが、$7 \bmod 10 = 7$、$2 \bmod 10 = 2$ となり衝突しません。