応用情報技術者試験 応用情報技術者試験 令和元年度秋期 午前 問7: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mod n とすると，任意のキー a と b

正解

イ. a−b が n の倍数

正答率 61.2%（1,223人中 748人が正解）

問題の解説

衝突するのは、ハッシュ値が等しい、つまり のときである。共通の余りを として 、 と置くと となり、差は の倍数になる。逆に差が の倍数なら余りも等しいので、これが条件である。

選択肢ごとの解説

• ア和が の倍数でも、余りが等しいとは限らない。、、 では和は 5 だが、余りは 1 と 4 で異なる。
• イ正しい。差が の倍数なら、 と を で割った余りが等しく、同じ格納位置になる。
• ウ、、 では は の倍数だが、余りは 1 と 2 で異なり、衝突しない。
• エ、、 では は の倍数だが、余りは 3 と 1 で異なり、衝突しない。倍数の向きが逆である。