自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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 が条件です。これは a と b を n で割った余りが等しい、すなわち a-b が n で割り切れる（nの倍数である）ことと同値です。合同式で書けば a≡b (mod n) です。
選択肢ごとの解説
- ア和がnの倍数でも余りは一致しません（例：n=5, a=2, b=3）。
- イ正解。余りが等しいことと差がnの倍数であることは同値です。
- ウ倍数の関係が逆で、nのほうが割られる側になっています。
- エこれも倍数の向きが逆であり、差がnの倍数という条件と一致しません。
この問題に出た用語
同じ分野の他の問題
- 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
- A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
- 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
- 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
- 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5
出典・参考
最終更新：2026-10-06／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。