令和4年度秋期 応用情報技術者試験 午前 問5
自然数をキーとするデータを，ハッシュ表を用いて管理する。キー 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の倍数
解答・解説を見る
正解：イ
AI解説
h(x)=x mod nにおいて、キーaとbが衝突する(h(a)=h(b)になる)のは、aとbをnで割った余りが等しくなるとき、すなわちa－bがnの倍数であるときである。 ア: a+bがnの倍数は、余りの差ではなく和に着目した誤った条件である。 イ: 正しい。a－bがnの倍数であることが、h(a)=h(b)となる(衝突する)条件である。 ウ: nがa+bの倍数は、aとbの和がnの約数になるという条件であり、衝突条件とは異なる。 エ: nがa-bの倍数は、aとbの差がnの約数になるという条件であり、正しい条件(a-bがnの倍数)とは主客が逆になっている。 💡 合同式の性質「a≡b (mod n) ⇔ (a-b)がnで割り切れる」を覚えておくと、この種のハッシュ衝突条件の問題にすぐ対応できる。
出典：令和4年度 秋期 応用情報技術者試験 午前 問5 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。