自然数をキーとするデータを、ハッシュ表を用いて管理する。
キーx のハッシュ関数をh (x )を
h (x )=x mod n
とする。
ここで、n はハッシュ表の大きさであり、x mod n はx をn で割った余りを表す。
キーa とb が衝突する条件はどれか。
ア | a +b がn の倍数 |
イ | a -b がn の倍数 |
ウ | n がa +b の倍数 |
エ | n がa -b の倍数 |
答え イ
【解説】
問題からa とb のキー値が衝突するのは、キー値を求めるハッシュ関数が剰余計算であるので
a mod n =b mod n
のときである。
この式を変形すると、
a mod n -b mod n =0
(a -b )mod n =0
になり、これはa -b がn の倍数(イ)である。
【キーワード】
・ハッシュ法