令和元年度 秋期 応用情報技術者 問7

正解 イ

a mod n＝b mod n となるのは、aとbの差がnの倍数のときです。

衝突は、異なるキーのハッシュ値が同じになることです。a＝pn＋r、b＝qn＋r のように、nで割った余りrが等しいとします。このとき a−b＝(p−q)n となり、a−bはnの倍数です。逆に、a−bがnの倍数なら、aとbをnで割った余りは等しくなります。例えばn＝5、a＝12、b＝7なら、a−b＝5で、h(12)＝h(7)＝2です。

ア：a+bがnの倍数になるのは、余りの和がnか0になるときです。余りが等しいとは限りません。例えばn＝5、a＝2、b＝3では、h(2)＝2、h(3)＝3で衝突しません。

ウ：倍数の関係が逆です。例えばn＝6、a＝1、b＝2ではnがa+bの倍数ですが、h(1)＝1、h(2)＝2で衝突しません。

エ：倍数の関係が逆です。例えばn＝6、a＝4、b＝2ではnがa−bの倍数ですが、h(4)＝4、h(2)＝2で衝突しません。

出典：令和元年度 秋期 応用情報技術者試験 問7