AP過去問 令和6年度秋期 午前 問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の倍数
回答・解説
例えば、a=24、b=10で、nが7のときは、b÷nやa÷nの余りはいずれも3で衝突する。このとき、アの関係にあるか確かめると、a+bは34で7の倍数にはなっていないので誤り、イの関係にあるか確かめると、24-10で、14になる7の倍数になるので、成り立っている。ウの関係について確かめると、7は34の倍数ではないので誤り、エは7は14の倍数ではないので誤りとなる。したがってイが正しい。
ハッシュの大きさが7の場合、あまり4となる11に対しても、7の倍数の差があるといずれも同じ値で衝突する、11+7=18で、18÷7は2余り4となる。18+7の25も25÷7は3あまり4となる。同じあまりになるもの同士の関係はつねに差が7の倍数になる。したがって、
イ a-bがnの倍数
が答えです。