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

正解

イ. a－b が n の倍数

正答率 64.9%（783人中 508人が正解）

問題の解説

衝突するのは のときである。共通の余りを とすると 、 と書けるので、 となり、 の倍数である。逆に差が の倍数なら余りは等しいので、これが衝突の条件になる。

選択肢ごとの解説

• ア和が n の倍数なのは、余りの和が n になる場合である。n=3 では 1 と 2 の和は 3 だが、余りは 1 と 2 で衝突しない。
• イ正しい。余りが等しい二つの数の差は n の倍数で、逆も成り立つので、衝突の必要十分条件になる。
• ウn が a+b の倍数という関係は、余りの一致と無関係である。n=6、a=1、b=2 では n は a+b=3 の倍数だが、余りは 1 と 2 で衝突しない。
• エn が a-b の倍数という向きは逆である。n=3、a=7、b=1 は余りがともに 1 で衝突するが、n は差 6 の倍数ではない。