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

ハッシュ表において、異なるキーが同じハッシュ値を持つことを衝突（シノニム）と呼びます。与えられたハッシュ関数 $h(x) = x \bmod n$ において、キー $a$ と $b$ が衝突する条件は、$h(a) = h(b)$ が成り立つことです。式で表すと、以下のようになります。 $$a \bmod n = b \bmod n$$ これは、$a$ を $n$ で割った余りと、$b$ を $n$ で割った余りが等しいことを意味します。このとき、$a$ と $b$ の差をとると、余りの部分が相殺されるため、$a - b$ は $n$ で割り切れる、すなわち $a - b$ が $n$ の倍数 となります。合同式で表すと $a \equiv b \pmod n$ となります。

各選択肢の解説

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