令和元年度 秋期 応用情報処理技術者試験 午前 問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\) の倍数