平成23年度 秋期 午前 問5

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

解説

余りが等しいことを式に直すと差が残ります。

ハッシュ表では、キーをハッシュ関数に通して得た値を置き場所の番号として使います。この設問のハッシュ関数は、キーを表の大きさで割った余りを返すものです。衝突とは、異なる二つのキーが同じ置き場所に割り当てられてしまうことですから、条件は、二つのキーを表の大きさで割った余りが等しい、と言い換えられます。ここから式を作ります。二つのキーを、それぞれ表の大きさの整数倍に共通の余りを足した形で書きます。この二つの差をとると共通の余りが打ち消し合い、表の大きさの整数倍だけが残ります。つまり、二つのキーの差が表の大きさで割り切れることが条件です。具体的な数でも確かめられます。表の大きさを 10 とすると、23 と 43 はどちらも余りが 3 で同じ場所に入り、差の 20 は 10 で割り切れます。読むときに気をつけたいのは、どちらがどちらの倍数かという向きです。倍数という語は二つの数の順序で意味が変わってしまうので、条件をいったん式に直してから選択肢の並びに当て直すと迷いません。なお衝突そのものは避けられないので、実際の仕組みでは起きた後の始末を用意します。

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

• アa＋b が n の倍数：差ではなく和を使った形です。表の大きさを 10、二つのキーを 4 と 6 とすると和は 10 で割り切れますが、余りは 4 と 6 で別々の場所に入るため、同じ場所に入らない例がすぐに作れます。
• ウn が a＋b の倍数：倍数の向きが逆で、表の大きさのほうが二つのキーの和で割り切れると述べています。割る側と割られる側の役割が入れ替わっており、余りが等しいという条件の言い換えにはなりません。
• エn が a－b の倍数：こちらも向きが逆で、表の大きさが二つのキーの差で割り切れるという条件になっています。表の大きさはふつうキーの差より小さいので、この関係が成り立つ場面はごく限られてしまいます。