平成27年度 春期 応用情報技術者 問5

正解 イ

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の倍数なら、余りは等しくなります。例えばn=10のとき、a=23、b=13はa−b=10で、どちらもハッシュ値は3です。

ア：a+bがnの倍数になるのは、aとbの余りを足すとnの倍数になる場合です。例えばn=10、a=3、b=7では、ハッシュ値は3と7で衝突しません。

ウ：倍数の関係が逆です。例えばa=1、b=2、n=6では、nはa+b=3の倍数ですが、ハッシュ値は1と2で衝突しません。

エ：倍数の関係が逆です。例えばa=3、b=1、n=10では、nはa−b=2の倍数ですが、ハッシュ値は3と1で衝突しません。

出典：平成27年度 春期 応用情報技術者試験 問5