自然数をキーとするデータを、ハッシュ表を用いて管理する。 キーx のハッシュ関数をh (x )を h (x )=x mod n とする。 ここで、n はハッシュ表の大きさであり、x mod n はx を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 の倍数(イ)である。
【キーワード】 ・ハッシュ法
戻る 一覧へ 次へ