令和6年度 秋期 プロジェクトマネージャ試験 データベーススペシャリスト試験 エンベデッドシステムスペシャリスト試験 システム監査技術者試験 情報処理安全確保支援士試験 午前 I 問題 【共通】 問3

ハッシュ表において、衝突（コリジョン）とは、異なるキーが同じハッシュ値を持つことを指します。

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

余りが等しい2つの数の差は、$n$ で割り切れる、つまり $n$ の倍数 になります。
したがって、$a - b$ が $n$ の倍数となる場合が、衝突の条件となります。

各選択肢の解説

• ア: $a+b$ が $n$ の倍数
  $a \bmod n + b \bmod n = n$ などとなるケースであり、$a \bmod n = b \bmod n$ とは限りません。例えば $n=5, a=2, b=3$ のとき、$a+b=5$（5の倍数）ですが、$h(a)=2, h(b)=3$ であり衝突しません。
• イ: $a-b$ が $n$ の倍数
  正解です。差が $n$ の倍数であれば、余りが等しくなり衝突します。例えば $n=5, a=8, b=3$ のとき、$a-b=5$（5の倍数）で、$h(8)=3, h(3)=3$ となり衝突します。
• ウ: $n$ が $a+b$ の倍数
  $a+b$ が $n$ の約数であることを意味します。余りが一致する条件とは関係ありません。例えば $n=6, a=1, b=2$ のとき、$a+b=3$ は $6$ の約数（$n$ は $a+b$ の倍数）ですが、$h(1)=1, h(2)=2$ であり衝突しません。
• エ: $n$ が $a-b$ の倍数
  $a-b$ が $n$ の約数であることを意味します。例えば $n=6, a=5, b=2$ のとき、$a-b=3$ は $6$ の約数（$n$ は $a-b$ の倍数）ですが、$h(5)=5, h(2)=2$ であり衝突しません。