平成25年度 秋期 応用情報技術者 問7

正解 イ

a mod nとb mod nが等しいとき衝突します。余りが等しいことは、a−bがnの倍数であることと同じです。

衝突（シノニム）とは、異なるキーのハッシュ値が同じになることです。h(a)＝h(b)は、aとbをnで割った余りが等しいという意味です。a＝pn＋r、b＝qn＋rと表すと、a−b＝(p−q)nとなります。したがって、a−bはnの倍数です。逆に、a−bがnの倍数なら、aとbの余りは等しくなります。

ア：余りが等しいかどうかは、和ではなく差で決まります。例えばn＝5、a＝1、b＝4ではa+b＝5ですが、余りは1と4で衝突しません。

ウ：nがa+bの倍数であることは、余りが等しい条件になりません。例えばn＝6、a＝1、b＝2では余りが1と2になり、衝突しません。

エ：倍数の関係が逆です。例えばn＝6、a＝3、b＝1ではnがa−b＝2の倍数ですが、余りは3と1で衝突しません。

出典：平成25年度 秋期 応用情報技術者試験 問7