高度試験共通令和6年度秋期午前I問 3

令和6年度秋期高度試験共通午前I 問3

難度

標準

自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n とすると、任意のキーaとbが衝突する条件はどれか。ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。

解説

結論 → 詳細 → 補足の 3 層構成

展開

解説Layer 1

ハッシュ衝突は、異なるキーaとbに対して同じハッシュ値h(a) = h(b)が生成される状況です。ハッシュ関数h(x) = x mod nにおいて、a mod n = b mod nとなる条件は、aとbをnで割った余りが等しいこと、つまり差の(a-b)がnの倍数である場合に衝突が発生します。

ア: a+bがnの倍数
誤りです。a+bがnの倍数でも、余りが等しくなるとは限りません。例えばn=5、a=1、b=4ではa+b=5は5の倍数ですが、h(1)=1、h(4)=4となり衝突しません。このときは余りの和がnになるだけで、衝突の条件である余りの一致にはなりません。
イ: a-bがnの倍数
正しいです。衝突はh(a)=h(b)、つまりa mod n=b mod nのときに起こります。a=qn+r、b=pn+rと表すとa-b=(q-p)nとなり、a-bはnの倍数です。逆も成り立ちます。例えばn=5、a=7、b=2ではa-b=5で、どちらのハッシュ値も2になり衝突します。
ウ: nがa+bの倍数
誤りです。nがa+bの倍数であっても、余りが等しくなるとは限りません。例えばa=1、b=2でa+b=3のとき、n=6は3の倍数ですが、h(1)=1、h(2)=2となり衝突しません。キーの和とハッシュ表の大きさの倍数関係は、余りの一致とは無関係です。
エ: nがa-bの倍数
誤りです。nがa-bの倍数であることは、a-bがnの倍数であることと逆の関係で、衝突の条件ではありません。例えばa=3、b=1ではa-b=2で、n=4は2の倍数ですが、h(3)=3、h(1)=1となり衝突しません。衝突するには、差a-bのほうがnの倍数である必要があります。

この解説は？

AI生成

解説は公式の問題文・公式解答を基に作成しています。事実誤認・選択肢の取り違え・最新法令の反映漏れ等を含む可能性があるため、重要な判断は必ずリンク先の公式資料でご確認ください。

最終更新: 2026年5月5日

検証プロセス・誤り報告フローは運営透明性レポートで公開しています。

この問題の理解を「分野全体の力」に広げるための足がかり

AI コパイロット

用語解説・選択肢分析・類題生成をその場で対話。クイズモードでは解答→解説がゼロ遷移。

AIに質問できる例

高度試験共通の同じ分野を年度をまたいで演習する