自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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 と b を n で割った余りが等しいときです。余りが等しいことは差 a − b が n で割り切れることと同値なので、a − b が n の倍数であることが条件になります。

選択肢ごとの解説

• ア和が n の倍数でも余りが一致するとは限らない（例：n=5, a=1, b=4）。
• イ正しい。余りが等しいことと a−b が 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