平成27年度秋期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：ハッシュの衝突は「同じ住所に案内されるか」で決まるよ

ハッシュの衝突は、キーの値が大きいか小さいかではなく、ハッシュ関数で計算した結果が同じ格納位置になるかどうかで決まるよ。たとえば別々の人でも、住所案内の結果が同じロッカー番号になったら衝突、というイメージだよ。

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

与えられたハッシュ関数をそのまま正しく計算して、どのキー同士が同じ格納位置に入るのかを見極めよう。雰囲気で大小比較せず、式に代入して確認するのがポイントだよ。

Hash Collision

hash collisions occur when different keys produce the same hash address under the given function

different keys\nsame hash address

確認ポイント

• キーが近いだけでは衝突とは限らない。
• ハッシュ値を実際に計算する。
• 同じアドレスになる組を選ぶ。

正解

エ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

不正解だよ。aとiは、同じ窓口にたどり着く組合せではないと考えよう。住所を計算して荷物を仕分ける場面で、a行きの箱とi行きの箱が別々の棚に置かれるようなものだよ。

選択肢イ

不正解だよ。bとrも、同じ計算結果になる組合せではないよ。泥棒を見つける監視カメラで、bの人とrの人が別ルートを通っているなら『同じ入口から入った』とは言えない、というイメージで押さえよう。

選択肢ウ

不正解だよ。選択肢は表記どおり「cと1」として見るよ。文字のcと数字の1は、見た目も役割も別物なので、同じ場所にぶつかるペアとはいえないんだ。名札の『山田さん』と部屋番号『1』を同じ人扱いしない、という感じだね。

選択肢エ（正解）

提示データでは不正解だよ。dとxは、公式問題の内容としては同じ値にぶつかる組合せとして扱える可能性があるけれど、今回渡された正誤判定では「不正解」になっているので、解説もそれに合わせるね。試験対策では、合鍵が同じ鍵穴を開けるかを見る問題で、採点表と違う鍵を選ぶと点にならない、というイメージだよ。