令和4年度秋期 データベーススペシャリスト 午前Ⅰ 問3

衝突条件を整理する視点

ハッシュ関数の衝突条件を検討するときは、入力の関係と出力の扱いを切り分け、定義に照らして「同じ結果」と「異なる入力」の組合せに注目しましょう。選択肢の表現をそのまま判断せず、条件の成立範囲を丁寧に確認します。

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

一つの観点として、衝突と呼ぶために同時に満たす必要がある入力側と出力側の関係が、各選択肢で整合しているかを確認してください。用語の印象ではなく定義の構造に注目します。

視点

衝突条件を確認する際は、複数の入力とそれぞれの出力の対応関係を整理し、条件がどの関係を指しているかを定義に沿って読み取りましょう。

確認ポイント

• 入力同士の関係を確認する
• 出力同士の関係を確認する
• 両者の対応が同じ条件を示しているか確認する

正解

イ

解説

ハッシュ値が衝突するとは、aとbをnで割った余りが等しいことです。余りが等しい二つの数の差はnで割り切れるため、a−bがnの倍数となる条件が衝突条件になります。

理由

h(a)=a mod n、h(b)=b mod nです。両者の余りが等しいとき、aとbはnを法として同じ値を持つため、a−bはnで割り切れます。したがって衝突条件は「a−bがnの倍数」です。

比較

和がnの倍数であることは、一般に二つの余りが等しいことを意味しません。また、「nがある数の倍数」という向きの表現も、ハッシュ値の一致条件を正しく表していません。

選択肢ア

これは不正解だよ。a＋bがnの倍数であっても、aとbをnで割った余りが同じになるとは限りません。例えばn＝5、a＝1、b＝4では和は5ですが、余りは1と4で異なるため、ハッシュ値は衝突しません。

選択肢イ（正解）

これは正解だよ。h(a)とh(b)が等しいとき、aとbをnで割った余りが一致します。余りが一致する二つの整数の差はnで割り切れるので、a−bがnの倍数であることが、二つのキーが衝突する条件になります。

選択肢ウ

これは不正解だよ。nがa＋bの倍数であるという条件は、二つのキーの和に関する関係であり、aとbの剰余が一致する条件ではありません。ハッシュ値の一致は、和ではなく二つのキーの差とnの割り切れ方で判断します。

選択肢エ

これは不正解だよ。nがa−bの倍数という表現は、a−bがnの倍数という正しい条件とは向きが逆です。例えばa−b＝6、n＝3なら正しい条件ですが、nがa−bの倍数とは限らず、選択肢の形では一般条件を表せません。

学習のポイント

剰余が一致する条件を、二つの数の差が割り切れる関係として理解する。