令和元年度 秋期 応用情報技術者試験 午前 問7
自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
h(x) = x mod n
とすると，任意のキーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
ハッシュ関数 h(x) = x mod n では，キーaとbが衝突する条件は次のように表されます。
衝突の条件は h(a) = h(b) です。
つまり，
a mod n = b mod n
これを変形すると，
a ≡ b (mod n)
この式は，a − b が n の倍数であることを意味します。
したがって，キーaとbが衝突する条件は「a − bがnの倍数」であるため，イが正解です。
答え
イ: a − bがnの倍数
出典：令和元年度 秋期 応用情報技術者試験 午前 問7
