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