平成27年 春期 応用情報技術者 午前 問5

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


キーワード
・ハッシュ表

キーワードの解説

戻る 一覧へ 次へ