平成20年 春期 基本情報技術者 午前 問14

キーx のハッシュ関数としてh (x )=mod(x , 97)を用いるとき、キー1094とハッシュ値が一致するものは、キー1〜1000の中にいくつあるか。
ここで、mod(x , 97)はx を97で割った余りを表す。

 ア  9
 イ  10
 ウ  11
 エ  12


答え ウ


解説
ハッシュ関数がh (x )=mod(x , 97)と剰余演算で、1094とハッシュ値はmod(1094, 97)=27なので、ハッシュ値が一致するのは、mod(x , 97)=27になるx である。(x =27, 124, 221, 318, …)
すなわち、x を式で書くとx =97×n+27である。
0〜1000の中に97の倍数は10個あり、10個目の97の倍数970に27を加えると997なので、x =97×n+27x が0〜1000になるのはn=0〜10の11個(ウ)である。


キーワード
・ハッシュ関数

キーワードの解説

戻る 一覧へ 次へ