令和6年度秋期 プロジェクトマネージャ 午前Ⅰ 問3

衝突条件を見極める視点整理

ハッシュ表の設問では、キーそのものの値だけでなく、同じ場所に対応づけられる条件に注目し、与えられた定義と前提を順に照合して判断します。異なる入力の対応関係を整理することが重要です。

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

確認の中心は、異なるキー同士が表の同一位置へ対応し得るかという関係です。変換の規則、キーの範囲、表の大きさなど、問題中の前提を分けて整理し、対応先の重なりだけを確認してください。

視点

衝突を考えるときは、キーから格納位置へ至る対応関係を一つの観点として捉えます。個々の値の大小ではなく、異なる入力が同じ位置に結び付く可能性を、設問の前提に沿って確認します。

確認ポイント

• 異なるキーについて、対応先を同じ基準で整理する
• 表の大きさやキーの範囲が判断にどう関係するか確認する
• 設問で示された条件と対応関係に矛盾がないか照合する

正解

イ

解説

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

理由

キー a と b が衝突するとは、h(a)=h(b)、つまり a mod n と b mod n が等しくなることです。二つの整数を n で割った余りが等しい場合、その差 a−b は n の倍数になる。したがって、正しい条件は「a−b が n の倍数」です。

比較

衝突はキーの和ではなく、二つのキーの差が表の大きさ n で割り切れるかどうかで決まる。また、n が別の数の倍数であるという向きの条件ではなく、キー同士の差が n の倍数になるという関係を確認する。

選択肢ア

これは不正解だよ。ハッシュ値はキーを n で割った余りなので、衝突は二つのキーの和が n の倍数になることでは判定できない。余りが同じかどうかに直接関係するのは、二つのキーを差し引いた値が n で割り切れるかという性質である。

選択肢イ（正解）

これは正解だよ。h(a)=a mod n と h(b)=b mod n が等しいとき、a と b は n で割った余りが同じである。この場合、余りを除いた差 a−b は n の整数倍になるため、二つのキーは同じハッシュ値となり衝突する。

選択肢ウ

これは不正解だよ。「n が a＋b の倍数」という条件は、表の大きさ n とキーの和の倍数関係を示しているだけである。ハッシュ値の一致には、各キーを n で割った余りが等しいことが必要であり、和ではなくキー間の差を調べる。

選択肢エ

これは不正解だよ。衝突条件に関係するのは、キーの差 a−b が n の倍数になることである。しかしこの選択肢は、n が a−b の倍数になるという逆向きの関係を述べている。一般には両者は同じ条件ではない。

学習のポイント

剰余が一致する条件を、合同式と整数の倍数の関係で理解する。