問題
自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を
h(x) ＝ x mod n
とすると，キー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
選択肢
- 1a＋b が n の倍数
- 2a－b が n の倍数
- 3n が a＋b の倍数
- 4n が a－b の倍数
正解
2. a－b が n の倍数
詳しい解説を見る解説を閉じる
解説
衝突は h(a)＝h(b)、すなわち a mod n ＝ b mod n のときに起きる。これは a と b を n で割った余りが等しいことを意味し、差 a－b が n で割り切れる、つまり a－b が n の倍数であることと同値である。よってイが正解。（出典: 平成23年度 秋期 応用情報技術者試験 午前 問5）
一問一答
全400問を繰り返し学習