令和6年度 秋期 プロジェクトマネージャ試験 データベーススペシャリスト試験 エンベデッドシステムスペシャリスト試験 システム監査技術者試験 情報処理安全確保支援士試験 午前 I 問題 【共通】 問3

テクノロジアルゴリズム

この問題は2024(R6)秋 高度試験共通 午前Iに出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

自然数をキーとするデータを，ハッシュ表を用いて管理する。キー xx のハッシュ関数 h(x)h(x) を

h(x)=x mod nh(x) = x \bmod n

とすると，任意のキー aa と bb が衝突する条件はどれか。ここで，nn はハッシュ表の大きさであり，x mod nx \bmod n は xx を nn で割った余りを表す。

解答・解説を読む

正解: 選択肢イ

ハッシュ表において、衝突（コリジョン）とは、異なるキーが同じハッシュ値を持つことを指します。

今回のハッシュ関数は h(x)=x mod nh(x) = x \bmod n です。
キー aa と bb が衝突する条件は、h(a)=h(b)h(a) = h(b) となること、すなわち、a mod n=b mod na \bmod n = b \bmod n となることです。
これは、aa を nn で割った余りと、bb を nn で割った余りが等しいことを意味します。

余りが等しい2つの数の差は、nn で割り切れる、つまり nn の倍数 になります。
したがって、a−ba - b が nn の倍数となる場合が、衝突の条件となります。

各選択肢の解説

  • ア: a+ba+b が nn の倍数
    a mod n+b mod n=na \bmod n + b \bmod n = n などとなるケースであり、a mod n=b mod na \bmod n = b \bmod n とは限りません。例えば n=5,a=2,b=3n=5, a=2, b=3 のとき、a+b=5a+b=5（5の倍数）ですが、h(a)=2,h(b)=3h(a)=2, h(b)=3 であり衝突しません。
  • イ: a−ba-b が nn の倍数
    正解です。差が nn の倍数であれば、余りが等しくなり衝突します。例えば n=5,a=8,b=3n=5, a=8, b=3 のとき、a−b=5a-b=5（5の倍数）で、h(8)=3,h(3)=3h(8)=3, h(3)=3 となり衝突します。
  • ウ: nn が a+ba+b の倍数
    a+ba+b が nn の約数であることを意味します。余りが一致する条件とは関係ありません。例えば n=6,a=1,b=2n=6, a=1, b=2 のとき、a+b=3a+b=3 は 66 の約数（nn は a+ba+b の倍数）ですが、h(1)=1,h(2)=2h(1)=1, h(2)=2 であり衝突しません。
  • エ: nn が a−ba-b の倍数
    a−ba-b が nn の約数であることを意味します。例えば n=6,a=5,b=2n=6, a=5, b=2 のとき、a−b=3a-b=3 は 66 の約数（nn は a−ba-b の倍数）ですが、h(5)=5,h(2)=2h(5)=5, h(2)=2 であり衝突しません。