解説

ハッシュ関数 h(x) = x mod n の場合、キーaとキーbが衝突する条件は h(a) = h(b)、つまり a mod n = b mod n です。これは「a と b を n で割った余りが等しい」ことを意味します。a mod n = b mod n ⟺ (a - b) mod n = 0 ⟺ a-b が n の倍数。したがって「a-b が n の倍数」が衝突条件です。選択肢bが正解です。数学的に表現すると a ≡ b (mod n)（aとbはnを法として合同）のとき衝突が起きます。

なぜ他の選択肢は違うのか

選択肢 ア

「a+b が n の倍数」は a+b ≡ 0 (mod n) を意味し、衝突条件 a ≡ b (mod n) とは異なります。例：n=5, a=2, b=3 のとき a+b=5（nの倍数）ですが h(2)=2, h(3)=3 で衝突しません。

選択肢 ウ

「n が a+b の倍数」は n ≡ 0 (mod a+b) を意味し、衝突条件とは無関係です。

選択肢 エ

「n が a-b の倍数」は a-b が n の約数または n の倍数とは逆の関係です。衝突条件は「a-b がnの倍数」であり「nがa-bの倍数」とは異なります。

解くときのポイント

ハッシュ衝突条件の導出：h(a)=h(b) ⟺ a mod n = b mod n ⟺ (a-b) mod n = 0 ⟺「a-b はnの倍数」の流れを理解する。mod演算の基本性質から論理的に導ける。「n の倍数」か「n での倍数」かの言葉の方向性に注意。