自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。このとき使用した除数は幾つか。

選択肢

• ア193
• イ197
• ウ199
• エ211

正解と解説

正解：ウ 199

剰余が等しい値どうしは差が除数の倍数になる。三つのキー値の差は1168−571=597、1566−1168=398、1566−571=995であり、これらの最大公約数は199である。597=199×3、398=199×2、995=199×5と割り切れるため、除数は199とわかる。

選択肢ごとの解説

• ア193では597も398も割り切れず、剰余は一致しない。
• イ197でも差の値を割り切れないため衝突しない。
• ウ正しい。差597・398・995をいずれも割り切る199が除数である。
• エ211では差を割り切れず、三つの剰余は一致しない。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 午前 問6
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 午前 問6
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 午前 問19
• 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における…2023年度 春期 午前 問6
• 探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す…2018年度 秋期 午前 問8