応用情報処理技術者試験　過去問　ハッシュ関数　衝突

令和元年度　秋期　応用情報処理技術者試験　午前　問7
あらためて問題と正解

令和元年度　秋期　応用情報処理技術者試験　午前　問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$の倍数の場合、ハッシュ値が同じになります。