自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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の倍数

衝突するのはa mod n ＝ b mod n となるときである。両者をnで割った余りが等しいということは、その差a－bがnで割り切れる、すなわちnの倍数であることと同値である。

選択肢ごとの解説

• ア和がnの倍数でも余りが等しいとは限らない（例：n=5、a=2、b=3）。
• イ正解。余りが等しいことは差a－bがnの倍数であることと同値である。
• ウnがa＋bの倍数という条件は、余りが等しいこととは無関係である。
• エnがa－bの倍数では割る側と割られる側が逆で、条件を満たさない。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 問6