「応用情報技術者試験/令和元年秋期午前問7」

問題

出典:応用情報技術者令和元年秋期午前問7

自然数をキーとするデータを、ハッシュ表を用いて管理する。
キーxのハッシュ関数h(x)を「h(x) = x mod n」とすると、
任意のキーaとbが衝突する条件はどれか。

ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。

ア:a+bがnの倍数
イ:a-bがnの倍数
ウ:nがa+bの倍数
エ:nがa-bの倍数

解説

実際にキーが衝突する具体例を挙げて、選択肢の式に合致するかを確認して精査する。

まず簡単なのが、
a=5
b=3
n=2
である。
すると、aもbも余りが1で衝突する。

選択肢ア
5+3=8が2の倍数
→合致

選択肢イ
5-3=2が2の倍数
→合致

選択肢ウ
2が5+3の倍数
→2は8の倍数ではないので、合致しない。

選択肢エ
2が5-3の倍数
→2は2の倍数だから合致。

これでは、選択肢ウしか除外することができなかった。

別の衝突する値を観察する。
a=24
b=52
n=7
で確認する。

選択肢ア
24+52が7の倍数
→76は7の倍数ではないので、合致しない。

選択肢イ
24-52が7の倍数
→-28は7で割り切れるので、合致する。

選択肢エ
7が24-52の倍数
→7は-28の倍数ではないので、合致しない

よって残った選択肢はイである。

解答

正解:イ

アドセンス
改行

テックキャンプ