令和元年度 秋期 応用情報技術者試験 午前 問7
テクノロジ／アルゴリズム自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mod n とすると，任意のキー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
出典：令和元年度 秋期 応用情報技術者試験 午前 問7
- アa＋b が n の倍数
- イa−b が n の倍数
- ウn が a＋b の倍数
- エn が a−b の倍数
正解：イ
解説
キー a と b が衝突するのは h(a)＝h(b)，すなわち a mod n＝b mod n のときです。両者を n で割った余りが等しいということは，差 a−b が n で割り切れる，つまり a−b が n の倍数であることと同値です。
選択肢ごとの解説
- ア誤り。a＋b が n の倍数でも衝突するとは限りません。例えば n＝5，a＝2，b＝3 では a＋b＝5 ですが，余りは 2 と 3 で異なり衝突しません。
- イ正しい。a mod n＝b mod n は a−b が n で割り切れることと同値なので，a−b が n の倍数であることが衝突の条件です。
- ウ誤り。n が a＋b の倍数という条件は，倍数の関係が逆であり，余りが等しいこととは無関係です。
- エ誤り。n が a−b の倍数という条件も倍数の向きが逆で，a−b の絶対値が n 以下の特殊な場合しか表せません。