平成27年度春期 応用情報技術者試験 午前 問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(a)=h(b)、すなわちaとbをnで割った余りが等しくなることである。余りが等しいことは、差a−bがnの倍数であること(合同式 a≡b mod n)と同値なので、イが正しい。例えばn=5、a=12、b=7なら余りはともに2で、a−b=5は5の倍数である。 ア: a+bがnの倍数でも余りは一致しない。例: n=5、a=2、b=3では和5は倍数だが余りは2と3で異なる。 イ: 正解。a−bがnの倍数 ⇔ 余りが等しい ⇔ 衝突。 ウ: nがa+bの倍数という条件は余りの一致とは無関係である。 エ: nがa−bの倍数という条件は倍数関係が逆であり、a≠bで|a−b|がnより小さい場合には成立し得ない。 💡 剰余(mod)の問題は「差が法nの倍数なら余りが等しい」という合同式の基本性質で判断する。迷ったら小さな具体値を代入して確かめる。
出典：平成27年度 春期 応用情報技術者試験 午前 問5 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。