基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

ハッシュ法は、レコードのキー値とハッシュ関数を用いて格納アドレスを計算によって求める方法です。キー値の衝突（シノニム）を避けるため、ある程度大きなメモリ領域が必要にはなりますが、基本的に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個

というように列挙していく方法でも正解にたどりつくことができます。