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

【正解】イ

【解説】 ハッシュ関数 h(x) = x mod n において，キー a と b が衝突する条件は h(a) = h(b) です。

h(a) = h(b) ということは，a mod n = b mod n です。 これは a と b を n で割った余りが等しいことを意味し，a - b が n の倍数であることと同値です。

よって，イの「a-b が n の倍数」が正解です。

アの「a+b が n の倍数」は，例えば a=3, b=5, n=4 のとき a+b=8 は4の倍数ですが，h(3)=3, h(5)=1 で衝突しません。 ウの「n が a+b の倍数」やエの「n が a-b の倍数」は条件が逆です。

【ポイント】 mod演算の性質として，a mod n = b mod n ⇔ (a-b) mod n = 0 ⇔ a-b は n の倍数，という関係を理解しましょう。