令和4年度 秋期 午前 問5

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

解説

余りが等しい、つまり差が n で割り切れます。

設問は、ハッシュ関数をキーを n で割った余りとしたとき、2 つのキーが衝突する条件を選ばせています。軸になるのは、衝突するとは格納先が同じになること、すなわち 2 つのキーを n で割った余りが等しいことだと読み替える点です。a を商と余りの形で書き、b も同じ余りを持つとすると、a から b を引いた値は商の差に n を掛けた形になります。つまり差が n の倍数であることが、衝突するための条件です。n を 7 として確かめると、10 と 24 はどちらも余りが 3 で同じ場所に入り、差は −14 で 7 の倍数になります。正解は、2 つのキーの差が n の倍数であるという記述です。

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

• アa＋b が n の倍数：2 つのキーの和に着目した条件です。n を 7 とすると、同じ場所に入る 10 と 24 の和は 34 で 7 の倍数になりません。逆に別の場所に入る 3 と 4 の和は 7 の倍数になります。
• ウn が a＋b の倍数：倍数の向きが入れ替わっています。ある数が別の数の倍数であるとは、後者に整数を掛けて前者になることなので、この記述は表の大きさの側が和で割り切れることを求めています。
• エn が a−b の倍数：こちらも倍数の向きが逆です。n を 7、キーを 10 と 24 とすると差は −14 ですが、7 は −14 に整数を掛けて得られないため、同じ場所に入る組でも成り立ちません。