平成25年度 秋期 午前 問7

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

解説

余りが等しいことは、差がハッシュ表の大きさの倍数と同じです。

設問は、キーを表の大きさで割った余りをハッシュ関数とするとき、二つのキーが衝突する条件を選ばせています。見る軸は一つで、衝突という言葉を定義どおりに式へ直すことです。衝突とは二つのキーが同じ場所に割り当てられることですから、それぞれの余りが等しいということにほかなりません。そこで、二つのキーを表の大きさで割った商と余りの形に書くと、余りが共通なので、二つのキーの差を取ったときに余りの部分が打ち消し合います。残るのは商の差に表の大きさを掛けた値ですから、差は表の大きさで割り切れます。つまり、二つのキーの差が表の大きさの倍数であることが、衝突するための条件です。表の大きさを 10 として数で確かめると、23 と 13 は余りがどちらも 3 で衝突し、差の 10 は確かに倍数です。23 と 43 も余りが 3 で衝突し、差の絶対値 20 も倍数です。一方、23 と 17 は余りが 3 と 7 で衝突せず、差の 6 も倍数ではありません。

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

• アa＋b が n の倍数：二つのキーの和が表の大きさの倍数だとしていますが、表の大きさを 10 として 23 と 17 を取ると和は 40 で倍数になるのに、余りは 3 と 7 で割り当て先が分かれます。和がそろうのは余りどうしが補い合う別の話です。
• ウn が a＋b の倍数：表の大きさが二つのキーの和の倍数だとしており、割る側と割られる側が逆になっています。表の大きさを 10 とすると和は多くの場合それより大きく、10 がその倍数になることはまずありません。
• エn が a−b の倍数：こちらも表の大きさを割られる側に置いた形です。表の大きさを 10 として差が 20 になる組を取ると、この条件は成り立たないのに割り当て先は一致するので、条件として用をなしません。