平成21年度 春期 午前 問6

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

解説

割った余りが等しくなる条件を式で表したものです。

このハッシュ関数は、キーを n で割った余りを表番地とする形です。異なるキー a と b が衝突するのは、両者を n で割ったときの余りが等しくなる場合のことを言います。二つの数を同じ数で割った余りが等しくなる条件は、割り算の一般的な性質から導けます。a を n で割った商と余り、b を n で割った商と余り、をそれぞれ書き下して、両者の差を取ります。余りの側は等しいと仮定したので互いに打ち消し合い、差は n に整数を掛けた形にまとめられます。すなわち、a と b の差が n の倍数になっていることが、二つの余りが一致する必要十分の条件です。したがって、衝突の条件は差が n の倍数であること、として表せます。

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

• アa+b が n の倍数：二数の合計 a+b が n の倍数になるという条件を挙げています。合計が割り切れることを述べているだけで、それぞれを n で割った余りが等しくなることを保証する式にはなりません。
• ウn が a+b の倍数：n が a+b の倍数になるという条件を挙げています。表の大きさが二数の合計の倍数という関係を意味し、割った余りが等しくなる条件とは主語と目的語が入れ替わった別の話です。
• エn が a−b の倍数：n が a−b の倍数になるという条件を挙げています。表の大きさが差の倍数という関係で、二数の差が表の大きさの倍数になるという実際の条件とは大小の向きが逆になっています。