令和6年度 高度共通 午前I（PM試験） 問3
自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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解説
ハッシュ値の衝突とは、異なるキーaとbのハッシュ値が等しくなること、すなわちa mod n = b mod nとなることである。剰余が等しいとは、aとbをnで割った余りが同じということであり、これは差a-bがnで割り切れる(a-bがnの倍数である)ことと同値である。合同式でa≡b (mod n) ⇔ n|(a-b)と覚えるとよい。 ア: a+bがnの倍数でも余りが等しいとは限らない。例えばn=5、a=1、b=4ではa+b=5は5の倍数だがh(a)=1、h(b)=4で衝突しない。 イ: 正しい。a mod n = b mod n ⇔ (a-b)がnの倍数。例えばn=5、a=12、b=7なら差5が5の倍数で、余りはともに2となり衝突する。 ウ: nがa+bの倍数という条件は剰余の一致と無関係である。例えばn=6、a=1、b=2ではnはa+b=3の倍数だが余りは1と2で衝突しない。 エ: 倍数の関係が逆である。nがa-bの倍数ではなく、a-bがnの倍数であることが衝突条件である。 💡 迷ったら小さな具体値(n=5など)を代入して確かめるのが確実である。「差がnの倍数なら余りが等しい」は合同式の基本性質として頻出する。
出典：令和6年度 秋期 プロジェクトマネージャ試験 午前I 問3 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。