令和４年度秋期午前I問題３

問３　自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を

h(x) = x mod n

とすると、任意のキー a と b が衝突する条件はどれか。ここで、nはハッシュ表の大きさであり、x mod n は x を n で割った余りを表す。

出典：　令和４年度　秋期　エンベデッドシステムスペシャリスト試験　午前I　問３

ア　a+bがnの倍数

イ　a-bがnの倍数

ウ　nがa+bの倍数

エ　nがa-bの倍数

解説　

試しにn=8で計算してみました。

ア　例えばa=6,b=2。計算するとh(a)=6,h(b)=2となるので衝突していない。

イ　例えばa=10,b=2。計算するとh(a)=2,h(b)=2となるので衝突する。

ウ　例えばa=1,b=3。計算するとh(a)=1,h(b)=3となるので衝突していない。

エ　例えばa=6,b=2。計算するとh(a)=6,h(b)=2となるので衝突していない。

よって答えはイとなります。