令和4年度 秋期 応用情報技術者試験 午前 問5

ハッシュ関数 h(x) = x mod n を考慮すると，キー a と b が衝突するのは，h(a) = h(b) となる場合です。これは以下のように変形できます：

1. h(a) = h(b)
   a mod n = b mod n

2. 両辺から mod n の定義を考えると：
   a と b を n で割った余りが等しい場合、以下が成立します：
   (a − b) mod n = 0

3. 上式から導かれる条件は：
   a − b が n の倍数である場合に衝突が発生します。

したがって，正解は イ です。

• ア: a + b が n の倍数
  誤り。a + b の条件はハッシュ値の衝突とは無関係です。

• イ: a − b が n の倍数
  正しい。ハッシュ値の衝突条件を正確に説明しています。

• ウ: n が a + b の倍数
  誤り。n と a + b の関係は衝突条件には影響しません。

• エ: n が a − b の倍数
  誤り。n はハッシュ表のサイズであり，a − b が n の倍数でなければなりません。

答え

イ: a − b が n の倍数