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

問14

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

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

ハッシュ法は、レコードのキー値とハッシュ関数を用いて格納アドレスを計算によって求める方法です。キー値の衝突(シノニム)を避けるため、ある程度大きなメモリ領域が必要にはなりますが、基本的に1回の探索で目的のデータを見つけることができます。

ハッシュ関数 h(x)=mod(x,97)を用いて、キー1094の値が格納されるアドレス値を計算すると、

 1094÷97=11 余り 27

ですから、「mod(1094, 97)=27」になります。割り算の商をnとすると、97で割って余りが27になる数は「97n+27」と表せるので、1~1000の中にこの式を満たす整数(キー)がいくつあるかを考えることになります。

不等式でnを範囲を求めると、

 97n+27≦1000
 97n≦973
 n≦10.03…
 (nは整数かつ0以上なので)
 n=0,1,2,…,10

したがって、余りが27になるキー、すなわちキー1094とハッシュ値が一致するものはキー1~1000の中に「11個」あるとわかります(97×0+27 ~ 97×10+27まで)。

また計算式にしなくても単純に、
  • 27
  • 27+97=124
  • 124+97=221
  • 221+97=318
  • 318+97=415
  • 415+97=512
  • 512+97=609
  • 609+97=706
  • 706+97=803
  • 803+97=900
  • 900+97=997 …計11個
というように列挙していく方法でも正解にたどりつくことができます。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop