自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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(a)=h(b)、つまりa mod n = b mod nが成り立つことである。これは、aとbをnで割った余りが等しいということなので、差a－bがnで割り切れる（nの倍数である）ことと同値になる。合同式ではa≡b (mod n)と表す関係である。
選択肢ごとの解説
- ア和が倍数になるのは余りが互いに補い合う場合で、余りが一致する条件ではない。
- イ正解。余りが等しいことと差がnの倍数であることは同値。
- ウnのほうが倍数になるという向きが逆で、条件として意味をなさない。
- エこちらも倍数の関係が逆向きで、衝突条件にならない。
この問題に出た用語
同じ分野の他の問題
- 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 午前 問6
- ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 午前 問19
- 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における…2023年度 春期 午前 問6
- 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力…2018年度 秋期 午前 問27
- 探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す…2018年度 秋期 午前 問8
出典・参考
最終更新：2026-10-06／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。