戻る
一覧へ
次へ
自然数をキーとするデータを、ハッシュ表を用いて管理する。
キー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 mod n =b mod n
が成り立つときである。
この式を変形すると
(a mod n )-(b mod n )=0
(a -b )mod n =0
になる。
この式は、a -b がn で割り切れることなので、a -b がn の倍数(イ)である。
【キーワード】
・ハッシュ表