問題
自然数をキーとするデータを、ハッシュ表を用いて管理する。キー 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 で割り切れる（n の倍数である）ことと同値である。よってイが正解。a＋b ではなく差が n の倍数である点に注意する。（出典: 令和6年度 秋期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習