基本情報技術者試験 ap-2022r04a-a 午前 問5: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mod n とすると，任意のキー a と b

問題本文

自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mod n とすると，任意のキー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。

選択肢

• ア.a＋b が n の倍数
• イ.a－b が n の倍数
• ウ.n が a＋b の倍数
• エ.n が a－b の倍数

正解

イ. a－b が n の倍数

解説

ハッシュ関数 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 の倍数なので誤り。