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

ハッシュ表における衝突（シノニム）とは、異なるキー a と b に対してハッシュ関数の戻り値が同じになる、すなわち h(a) = h(b) となる状態を指します。

本問のハッシュ関数は h(x) = x mod n であるため、衝突が起きる条件は以下の等式が成り立つことです。
a mod n = b mod n

これは、「a を n で割った余り」と「b を n で割った余り」が等しいことを意味します。
数学的に、2つの数を同じ数で割った余りが等しい場合、その2つの数の差は割った数の倍数になります。
したがって、a - b（または b - a）が n の倍数になる場合が衝突の条件となります。

各選択肢の解説

• ア. a+b が n の倍数
  誤りです。例えば n=10, a=7, b=3 の場合、a+b=10 で n の倍数になりますが、h(a)=7, h(b)=3 となり衝突しません。
• イ. a-b が n の倍数
  正解です。 差が n の倍数となる場合、それぞれの数を n で割った余りが等しくなるため、必ず衝突します。（例：n=10, a=23, b=13 のとき、h(a)=3, h(b)=3 で衝突。差は 23-13=10 で n の倍数）
• ウ. n が a+b の倍数
  誤りです。例えば n=10, a=3, b=2 の場合、a+b=5 であり n は a+b の倍数ですが、h(a)=3, h(b)=2 となり衝突しません。
• エ. n が a-b の倍数
  誤りです。例えば n=10, a=5, b=3 の場合、a-b=2 であり n は a-b の倍数ですが、h(a)=5, h(b)=3 となり衝突しません。