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

正解

イ. a－b が n の倍数

正答率 43.2%（1,469人中 635人が正解）

問題の解説

ハッシュ関数 h(x)＝x mod n で2つのキーが同じ格納位置になる(シノニム、衝突)条件を問う問題。衝突は a mod n ＝ b mod n、つまり a と b を n で割った余りが等しいときに起こる。余りが等しいことは差 a−b がちょうど n で割り切れること、すなわち a−b が n の倍数であることと同値なので、正解はイである。

選択肢ごとの解説

• アa＋b が n の倍数なのは2つの余りが互いに補い合って和が0になる関係であり、余りの一致(衝突)条件ではないので誤り。
• イ正しい。a−b が n の倍数のとき a mod n と b mod n が一致し、同じハッシュ値になって衝突する。
• ウ「n が a＋b の倍数」は割る数 n の側が倍数という逆向きの関係で、余りの一致とは無関係なので誤り。
• エ「n が a−b の倍数」は倍数の向きが逆である。正しくは a−b の方が n の倍数なので誤り。