自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x)＝x mod n とすると、任意のキーaとbが衝突する条件はどれか。ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。
h(x)=x mod n の衝突条件は a−b が n の倍数
選択肢
- アa＋bがnの倍数
- イa－bがnの倍数
- ウnがa＋bの倍数
- エnがa－bの倍数
正解と解説
正解：イ a－bがnの倍数
ハッシュ関数がh(x)＝x mod nのとき、キーaとbが衝突するのはa mod n＝b mod n、すなわちaとbをnで割った余りが等しいときである。これはa−bがnで割り切れること、つまりa−bがnの倍数であることと同値である。
選択肢ごとの解説
- アa＋bが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
- 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
- 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
- あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3
最終更新：2026-08-25／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。