令和6年度秋期 応用情報技術者試験 午前 問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において、キーaとbが衝突する(h(a)=h(b)となる)のは、aとbをnで割った余りが等しいとき、すなわちa-bがnで割り切れる=a-bがnの倍数であるときである。 ア: a+bがnの倍数であることは、a mod nとb mod nが等しくなる条件とは一般に一致しないため誤り。 イ: a-bがnの倍数であることはh(a)=h(b)となる条件と一致し、衝突の条件として正しい。 ウ: nがa+bの倍数であることは、余りの一致条件とは論理的に逆の関係であり衝突条件として誤り。 エ: nがa-bの倍数であることは、a、bに対してnが大きくなり得る関係であり、剰余が一致する条件とは一般に一致しないため誤り。 💡 剰余(mod)が一致する条件は、合同式の考え方から「差が法(この場合n)の倍数になること」と覚えると迷わない。
出典：令和6年度 秋期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。