平成27年度 春期 午前 問5

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

解説

余りが等しいことは、差が n の倍数であることと同じです。

設問は、ハッシュ表の大きさ n で割った余りをハッシュ関数とするとき、二つのキーが衝突する条件を選ばせています。衝突するとは、二つのキーから同じ位置が求まること、つまり n で割った余りが等しいことです。ここを式に開きます。a を n で割った商と余り、b を n で割った商と余りをそれぞれ書き、余りが同じだとして引き算をすると、余りが打ち消し合って、n と商の差の積だけが残ります。よって、二つのキーの差が n の倍数であることが条件になります。数で当てます。n を十として、a が 23、b が 43 のときは余りがどちらも 3 で衝突し、差の 20 は十の倍数です。a が 23、b が 47 のときは余りが 3 と 7 で衝突せず、差の 24 は十の倍数ではありません。衝突する組でも衝突しない組でも、言っていることが合います。除算法のハッシュ表で n に素数を選ぶのは、この差が倍数になりにくくするためです。

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

• アa＋b が n の倍数：和で考えた形です。n を十、二つのキーを 4 と 6 とすると和は十の倍数になりますが、余りは 4 と 6 で別々の位置に入ります。衝突しない組を衝突すると言ってしまうので、条件として成り立ちません。
• ウn が a＋b の倍数：倍数の向きが逆になっています。表の大きさの側が二つのキーの和で割り切れる場面は、表がキーより大きいときに限られ、ふつうの使い方ではまず起こりません。
• エn が a−b の倍数：こちらも倍数の向きが逆です。X が Y の倍数とは、X が Y に整数を掛けた値であるという意味なので、二つを入れ替えると条件がまったく別のものに変わってしまいます。