解説

ハッシュ関数 h(x) = x mod n において、h(a) = h(b) が衝突の条件。h(a) = a mod n、h(b) = b mod n が等しいとき：a mod n = b mod n、これは a と b の差 (a-b) が n の倍数であることと同値。数式で表すと：a = qn + r、b = pn + r（同じ余りr）とすれば a-b = (q-p)n となり、n が (a-b) を割り切る＝「a-b が n の倍数」。選択肢bが正解。衝突が多いと検索効率が低下するため、ハッシュ表のサイズnには素数を選ぶのが一般的。

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

選択肢 ア

「a+bがnの倍数」は衝突条件ではない。例えばa=1,b=5,n=3のとき、a mod 3=1、b mod 3=2で衝突しないが、a+b=6は3の倍数。

選択肢 ウ

「nがa+bの倍数」はnがa+bを割り切るという意味で、衝突とは無関係。

選択肢 エ

「nがa-bの倍数」はa-bがnの倍数と逆の関係（割る側と割られる側が入れ替わり）。n < |a-b| のときは成立しないケースが多く、一般的な衝突条件ではない。

解くときのポイント

ハッシュの衝突条件：「a mod n = b mod n」 ⟺ 「(a-b) mod n = 0」 ⟺ 「a-b が n の倍数」。ハッシュ衝突対策：チェイン法（連結リスト）・オープンアドレス法（再ハッシュ）。nを素数にすると衝突が減る理由も理解しておく。