平成25年度秋期 ITサービスマネージャ 午前Ⅰ 問2

剰余ハッシュの衝突を具体値で確かめる

衝突とは異なるキーが同じハッシュ値になることです。条件を抽象的に考え込む前に、問題で与えられた関数の定義を正確に読み取り、手元でいくつかのキーを当てはめて得られる値を比べることで、条件の意味を自分で確かめる姿勢が役立ちます。

この問題で問われていること

観点は一つ、「二つのキーのハッシュ値が一致するとはどういう状態か」を自分の言葉で説明できるかです。剰余演算の結果が何によって決まるかを振り返り、キーそのものが違っても値が同じになりうる理由を意識して検討してください。

視点

ハッシュ関数はキーを格納位置などの値に変換する仕組みです。異なるキーが同じ値に変換されることを衝突と呼びます。剰余を使う方式では、割る数と余りの関係を丁寧に扱うことが理解の鍵になります。学習の際は、まず定義を式として読み取ります。次に小さな数で試して結果を観察し、そこから一般的な条件へと考えを広げる手順が有効です。

確認ポイント

• ハッシュ関数で何を何で割り、どの値を結果として使うのかを正確に読み取れているか
• 小さな具体例でハッシュ値を求め、一致するか一致しないかを自分で確かめたか
• 確かめた例から、値が一致する場合に共通する性質を自分の言葉でまとめられるか

正解

イ

解説

h(x)=x mod n で衝突するのは、a と b を n で割った余りが等しいときだよ。余りが同じなら a−b は n の整数倍になり、逆に a−b が n の倍数なら余りは一致する。だから正解はイだね。

理由

a=p×n+r、b=q×n+r（p、q は整数、0≦r<n）のように、a と b を n で割った余りがどちらも r だとする。このとき a−b=(p−q)×n となるから、a−b は n の倍数だよ。逆に a−b=k×n（k は整数）なら、a=b+k×n なので、a を n で割った余りは b を n で割った余りと同じになる。つまり h(a)=h(b) と「a−b が n の倍数」は同値で、これが衝突の必要十分条件だよ。例えば n=5、a=11、b=1 なら a−b=10 は 5 の倍数で、h(11)=h(1)=1 だから衝突するね。

比較

ア・ウは和 a+b に注目しているけれど、衝突は余りが等しいかどうかで決まるので、和は判断の基準にならない。n=5、a=1、b=4 は和が 5 の倍数なのに衝突しないよ。エは差に注目している点はよいけれど、倍数関係の向きが逆だね。n=6、a=3、b=1 のように n が a−b=2 の倍数でも、余りは 3 と 1 で衝突しない。正しいのは、差のほうが n の倍数であるというイの関係だよ。

選択肢ア

これは不正解だよ。a+b が n の倍数でも衝突するとは限らないね。n=5、a=1、b=4 なら a+b=5 は 5 の倍数だけど、h(1)=1、h(4)=4 で格納位置は違う。逆に a=6、b=1 は h(6)=h(1)=1 で衝突するのに、a+b=7 は 5 の倍数じゃないよ。見るべきなのは和ではなく、余りが一致するかどうかだね。

選択肢イ（正解）

これは正解だよ。a=p×n+r、b=q×n+r（0≦r<n）のように余り r が同じなら、a−b=(p−q)×n で n の倍数になるね。逆に a−b=k×n なら、a と b を n で割った余りは等しくなる。だから h(a)=h(b)、つまり衝突の必要十分条件は a−b が n の倍数であることだよ。例えば n=5、a=11、b=1 なら差は 10 で、どちらも余りは 1 だね。

選択肢ウ

これは不正解だよ。差ではなく和を見ているうえに、倍数の向きも逆だね。n=6、a=1、b=2 なら n は a+b=3 の倍数だけど、h(1)=1、h(2)=2 で衝突しないよ。反対に n=5、a=6、b=1 は余りがどちらも 1 で衝突するのに、5 は a+b=7 の倍数じゃない。だから衝突の条件として成り立たないね。

選択肢エ

これは不正解だよ。差に注目している点はよいけれど、倍数の向きが逆だね。n=6、a=3、b=1 なら n は a−b=2 の倍数だけど、h(3)=3、h(1)=1 で衝突しない。反対に n=5、a=11、b=1 は余りがどちらも 1 で衝突するのに、5 は a−b=10 の倍数じゃないよ。「a−b が n の倍数」とはまったく別の条件だね。

学習のポイント

剰余が等しい条件（合同）を、差が法 n の倍数であることに言い換える力を身につけよう。