問5応用情報技術者 令和4年度 秋期

解説

正解は2。キーaとbが衝突するのは、ハッシュ値が同じとき、つまり a mod n = b mod n のときである。aとbをnで割った余りが等しければ、a−bはnで割り切れる。逆にa−bがnで割り切れれば余りは等しい。したがって衝突の条件は「a−bがnの倍数」になる。たとえばn=10、a=23、b=13なら差は10でnの倍数となり、どちらもハッシュ値は3になる。

• 1は、a+bがnの倍数でも衝突するとは限らない。n=10、a=3、b=7なら和は10だが、ハッシュ値は3と7で違う。
• 3は、倍数の向きが逆。nがa+bの倍数という関係は余りの一致と結び付かない。
• 4も向きが逆。n=10、a=12、b=7なら差5に対してnは5の倍数だが、ハッシュ値は2と7で違う。

根拠：剰余の性質（a mod n = b mod n ⇔ a−b が n で割り切れる）