令和元年度 秋期 午前 問7

✓ これが正解イa−b が n の倍数

解説

余りが等しいことは、差がnで割り切れることと同じです。

衝突とは、異なるキーが同じハッシュ値になることです。h(x)＝x mod n ですから、a と b が衝突する条件は a mod n ＝ b mod n と書けます。ここで両者を n で割った商と余りに分けて差を作ると、余りが等しい場合は余り同士が打ち消し合い、商の差に n を掛けた値だけが残ります。つまり a−b は n の倍数です。逆に a−b が n の倍数であれば、割ったときの余りは必ず一致します。どちらの向きからも言えるので、これが過不足のないちょうどの条件になります。小さな数で試すと確かめやすく、n が5のとき3と8は差が5で衝突します。表の大きさを素数に選ぶと、キーの並びに潜む周期と重なりにくくなり、偏りを抑えられることも知られています。衝突自体は避けきれません。

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

• アa＋b が n の倍数：和が n の倍数でも、余りが等しいとは限りません。n が5、a が2、b が3のとき、和は5で倍数になりますが、余りは2と3で異なります。和ではなく差を見るのが、余りをそろえるための条件です。反例が一つあれば条件になりません。
• ウn が a＋b の倍数：n が a＋b の倍数という向きは、表の大きさが割られる側に回った形です。表の大きさは余りを決めるために割る数であって、割られる数ではありません。倍数の関係が上下さかさまになっており、条件として成り立ちません。
• エn が a−b の倍数：こちらも倍数の向きが逆です。n が6、a が5、b が3のとき、差は2ですから6は2の倍数になりますが、余りは5と3で一致しません。割る数と割られる数を入れ替えると、条件として成り立たなくなります。向きを確かめる癖が必要です。