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

正解

イ. a－b が n の倍数

正答率 43.1%（1,474人中 636人が正解）

問題の解説

ハッシュ値が等しいとは、 のことである。共通の余りを r、商を p、q とすると 、 なので、差は となり n の倍数になる。逆に差が n の倍数なら余りは等しい。

選択肢ごとの解説

• ア和が n の倍数でも衝突するとは限らない。n=5、a=2、b=3 では だが、余りは 2 と 3 で異なる。
• イ正しい。余りが等しいキーの差は n の倍数になり、逆に差が n の倍数なら余りも等しくなる。
• ウn と の倍数関係は衝突と無関係である。n=6、a=1、b=2 では n は の倍数だが、余りは 1 と 2 で衝突しない。
• エ倍数の向きが逆である。n=6、a=5、b=3 では n は の倍数だが、余りは 5 と 3 で衝突しない。