平成19年 秋期 ソフトウェア開発技術者 午前 問12

自然数をキーとするデータを、ハッシュ表を用いて管理する。
キー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 の倍数(イ)である。


キーワード
・ハッシュ法

キーワードの解説

戻る 一覧へ 次へ