ハッシュ値が衝突する条件はどれか 【アルゴリズム】

情報処理試験過去問

令和元年度 秋期 応用情報処理技術者試験 午前 問7

問題

 自然数をキーとするデータを, ハッシュ表を用いて管理する。キー\(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\) の倍数

解説

ハッシュ表(ハッシュテーブル)とは、データ構造の一つです。キーと対応する値のペアでデータを管理します。
この値がハッシュ値で、ハッシュ値を求める関数が、ハッシュ関数になります。ハッシュ値が別のキーでも同じ値になってしまうことを衝突と読みます。
今回のハッシュ関数が、\( h(x) = x \, mod \, n \)ですね。意味は問題文に書いてありますね。\(x \, mod \, n\) は \(x\) を \(n\) で割った余りを表しています。

このような問題は、計算式を考えて解いていくことも可能ですが、証明が必要なわけではないので、値を代入して具体例を考えていくことが早いケースが多いです。

選択肢ごとに値を導入して考えてみます。
ア \(n\)の倍数が必要になるので、\(n < a , \: n < b\)が良さそうです。
  今回は、\(n = 3,\: a = 4,\: b = 5 \)とします。
  \(a + b = 9\) が \(n = 3\) の倍数になっていますよね。
  ハッシュ関数に代入してハッシュ値を計算します。
  \( h(a) = a \, mod \, n = 4 \, mod \, 3 = 1\)
  \( h(b) = b \, mod \, n = 5 \, mod \, 3 = 2\)
    ↓
  同じ値になっていないので、アではないことがわかります。

イ 条件を満たすように、\(n = 3,\: a = 5,\: b = 2 \)とします。
  \( h(a) = a \, mod \, n = 5 \, mod \, 3 = 2\)
  \( h(b) = b \, mod \, n = 2 \, mod \, 3 = 2\)
    ↓
  同じ値になりました。これを選んで良さそうです。もしかするとたまたまの可能性もありますので、別の選択肢も確認してみましょう。

ウ 条件を満たすように、\(n = 3,\: a = 4,\: b = 2 \)とします。
  \( h(a) = a \, mod \, n = 4 \, mod \, 3 = 1\)
  \( h(b) = b \, mod \, n = 2 \, mod \, 3 = 2\)

エ 条件を満たすように、\(n = 6,\: a = 5,\: b = 2 \)とします。
  \( h(a) = a \, mod \, n = 5 \, mod \, 6 = 5\)
  \( h(b) = b \, mod \, n = 2 \, mod \, 6 = 2\)

イのみが同じ値になりました。衝突する条件が分かりました。

試験時は必要ないですが、念の為、計算式でも考えてみましょう。

\(x \, mod \, n\) が同じ値になるということは、
\(a = aをnで割ったときの商 \times n + x \)
\(b = bをnで割ったときの商 \times n + x \)
となります。

これを\(x\)について解くと
\(x = a – aをnで割ったときの商\times n \)
\(x = b – bをnで割ったときの商\times n \)

衝突する際には、\(x\)が等しいということなので、
\(a – aをnで割ったときの商\times n = b – bをnで割ったときの商\times n \)
\(a – b = aをnで割ったときの商\times n – bをnで割ったときの商\times n \)
\(a – b = (aをnで割ったときの商- bをnで割ったときの商) \times n \)

問題文からそれぞれが自然数であることから、\((aをnで割ったときの商- bをnで割ったときの商)\)は整数になります。
というわけで、
\(a-b\)は、整数の\(n\)倍なので、\(n\)の倍数の場合、ハッシュ値が同じになります。


正解

イ \(a – b\) が \(n\) の倍数



あらためて問題と正解

 自然数をキーとするデータを, ハッシュ表を用いて管理する。キー\(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\) の倍数