平成27年度春期 プロジェクトマネージャ 午前Ⅰ 問3

ハッシュ衝突の条件を定義から確かめる

問題で与えられたハッシュ関数の定義をそのまま使い、どのような場合に異なるキーから同じ格納位置が得られるのかを、自分で選んだ小さな具体例で試しながら確かめることが検討の中心になります。

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

問題文中の除数や計算手順を正確に読み取り、示された条件が常に成り立つのか、特定の場合にだけ成り立つのかを、定義に具体的な値を一つずつ当てはめて区別することが重要です。

視点

ハッシュ法では、キーを計算によって格納位置へ対応付けます。剰余は割る数によって取り得る値の範囲が限られるため、異なるキーが同じ結果になることがあります。どのような条件で結果が一致するかは、推測で決めずに、定義へ実際の値を代入して確かめることが大切です。

確認ポイント

• ハッシュ関数で使われている除数や演算の順序を、問題文から正確に読み取ったか
• 自分で選んだ複数のキーを実際に定義へ当てはめ、得られた結果を比べてみたか
• 一つの例で成り立った関係が、別の値でも常に成り立つかを確かめたか

正解

イ

解説

aとbをnで割った余りが等しいとき、a=pn+r、b=qn+rと表せます。差はa−b=(p−q)nとなり、nの倍数になります。そのため、衝突の条件は「a−bがnの倍数」を示すイです。

理由

衝突はh(a)=h(b)、つまりa mod n = b mod nが成り立つことです。共通の余りをrとすると、a=pn+r、b=qn+r（p、qは整数、0≦r<n）と書けます。差をとるとa−b=(p−q)nで、余りの部分が打ち消されてnの倍数だけが残ります。逆に、a−bがnの倍数ならaとbの余りは一致します。したがって、衝突の必要十分条件は「a−bがnの倍数」です。例えばn=5、a=7、b=2では、a−b=5で、h(7)=h(2)=2となり衝突します。

比較

a+bがnの倍数になるのは、二つの余りの和が0またはnになる場合です。この場合、余りが等しいとは限りません。また「nがa−bの倍数」「nがa+bの倍数」は倍数関係の向きが逆で、nがa−bやa+bで割り切れるという意味になります。いずれも余りが一致する条件にはなりません。「XがYの倍数」はXがYで割り切れることだと、向きに注意して読むことが大切です。

選択肢ア

これは不正解だよ。a+bがnの倍数になるのは、二つの余りの和が0またはnになる場合で、余りが等しいことは保証されないよ。例えばn=5、a=7、b=3ではa+b=10で5の倍数だけど、h(7)=2、h(3)=3で衝突しないね。衝突の条件は和ではなく差で考えるよ。

選択肢イ（正解）

これは正解だよ。衝突はaとbをnで割った余りが等しいことだよ。共通の余りをrとするとa=pn+r、b=qn+rと書けて、a−b=(p−q)nはnの倍数になるね。逆にa−bがnの倍数なら余りは一致するよ。例えばn=5、a=7、b=2ではa−b=5で、h(7)=h(2)=2となり衝突するよ。

選択肢ウ

これは不正解だよ。「nがa+bの倍数」はnがa+bで割り切れるという意味で、倍数関係の向きも使う量も違うよ。例えばn=10、a=3、b=2ではa+b=5で、10は5の倍数だけど、h(3)=3、h(2)=2で衝突しないね。余りが一致する条件にはならないよ。

選択肢エ

これは不正解だよ。差に注目している点は良いけど、倍数関係の向きが逆だよ。例えばn=5、a=12、b=2ではh(12)=h(2)=2で衝突するのに、a−b=10なので5は10の倍数ではないね。逆にn=10、a=3、b=1では10は2の倍数だけど、h(3)=3、h(1)=1で衝突しないよ。

学習のポイント

除算ハッシュ（剰余法）で衝突が起きる条件を、合同式（a≡b mod n）で理解しましょう。