平成21年度春期 応用情報技術者試験 午前 問6
自然数をキーとするデータを，ハッシュ表を用いて管理する。キー 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において、h(a)=h(b)となる（衝突する）のは、aとbをnで割った余りが等しい場合であり、これはa-bがnの倍数であることと同値である。 ア: a+bがnの倍数であることは、a mod nとb mod nが等しいことを保証しない。 イ: a-bがnの倍数であることが衝突条件と一致する。これが正解。 ウ: nがa+bの倍数という条件は一般に成立しにくく、衝突条件とは異なる。 エ: nがa-bの倍数という条件は、a-bがnの倍数であることの逆の関係であり、衝突条件としては誤り。 💡 mod演算の衝突条件は「差が法(n)の倍数」が基本形。a≡b (mod n) ⇔ n|(a-b)という合同式の定義を思い出すとよい。
出典：平成21年度 春期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。