平成30年度秋期 ネットワークスペシャリスト 午前Ⅰ 問9

条件の対応関係を丁寧に確認

ハッシュに関する設問では、用語の定義と与えられた条件の対応を切り分け、個別の印象ではなく、問題中で指定された関係が一貫しているかを順に確認しましょう。前提が変わる箇所にも注意します。

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

今回の確認点は、衝突に関する記述と除数に関する記述を混同せず、同じ前提のもとで比較すべき対象・条件・範囲を整理してから判断することです。定義と条件の対応だけに集中しましょう。

視点

まず設問内の条件を、対象・関係・制約に分けて書き出し、それぞれがどの定義に基づく主張かを確認します。数値や記号にすぐ代入せず、条件同士の対応が崩れていないかを先に見直すと、早合点を避けられます。

確認ポイント

• 問題で比較されている対象が何と何かを、言葉の定義に沿って区別できているか。
• 衝突と除数の関係について、設問が置く前提や制約を読み落としていないか。
• 一つの印象や暗記だけで決めず、各記述が同じ条件下で整合するかを確認したか。

正解

ウ

解説

剰余ハッシュで全てのハッシュ値が衝突するには、三つのキー値を同じ除数で割った余りが一致しなければなりません。したがって、キー値同士の差は除数の倍数になります。199で計算すると三つの余りが一致します。

理由

除数を199とすると、571 mod 199＝173、1168 mod 199＝173、1566 mod 199＝173となり、三つのハッシュ値が全て一致します。また、1168−571＝597、1566−1168＝398で、いずれも199の倍数です。

比較

候補の中で、三つのキー値を199で割った余りだけが一致します。剰余ハッシュでは、キー値そのものが異なっていても、同じ余りになれば衝突として扱われるため、共通する除数の条件を確認することが重要です。

選択肢ア

これは不正解だよ。除数を193とすると、571 mod 193＝185、1168 mod 193＝10、1566 mod 193＝22となり、三つの剰余が一致しません。したがって、全てのハッシュ値が衝突するという設問の条件を満たさない数値です。

選択肢イ

これは不正解だよ。除数を197とすると、571 mod 197＝177、1168 mod 197＝183、1566 mod 197＝187となります。三つのキー値から得られる剰余が異なるため、全てのハッシュ値が衝突する条件には合致しません。

選択肢ウ（正解）

これは正解だよ。除数を199とすると、571 mod 199＝173、1168 mod 199＝173、1566 mod 199＝173となり、三つのハッシュ値が全て一致します。したがって、設問の衝突条件を満たす除数です。

選択肢エ

これは不正解だよ。除数を211とすると、571 mod 211＝149、1168 mod 211＝113、1566 mod 211＝89となり、剰余は三つとも異なります。そのため、全てのハッシュ値が衝突したという条件を満たしません。

学習のポイント

剰余の一致と、キー値の差が除数で割り切れる関係を理解する。