令和元年度秋期 応用情報技術者試験 午前 問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 の倍数
解答・解説を見る
正解：イ
AI解説
ハッシュ関数h(x)=x mod nにおいて、2つのキーa,bが衝突する(同じハッシュ値になる)条件はa mod n=b mod nであり、これはa-bがnの倍数であることと同値である。 ア: a+bがnの倍数であることは、a mod n=b mod nが成り立つための条件とは一致しない(例えばa=1,b=n-1などで成立してしまうが、必ずしも衝突を意味しない)。 イ: a-bがnの倍数であることは、a mod nとb mod nが等しくなるための必要十分条件であり、これが衝突条件として正解である。 ウ: nがa+bの倍数であることは、衝突条件とは無関係な式であり、a,bの余りの一致を保証しない。 エ: nがa-bの倍数であることは、a-bがnの倍数であることの逆の関係を述べており、条件として不適切である(正しくは「a-bがnの倍数」)。 💡 「a mod n = b mod n」⇔「(a-b) mod n = 0」⇔「a-bがnの倍数」という同値変形を押さえておくとハッシュ衝突条件の問題に素早く対応できる。
出典：令和元年度 秋期 応用情報技術者試験 午前 問7 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。