キー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+27でx が0〜1000になるのはn=0〜10の11個(ウ)である。
【キーワード】
・ハッシュ関数