ハッシュ表探索｜格納位置を計算で決める・衝突したら次の番号へ【基本情報技術者試験 科目B】

現行FE シラバス Ver9.2 準拠擬似言語の記述形式は2022年から変更なし最終更新 2026-10-11

ハッシュ表探索は、値から格納位置を計算して、その場所を見に行く探し方です。前から1つずつ照らし合わせる線形探索とちがい、最初に見る場所が、計算で決まります。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円2,600円中身を見る ›

格納位置を、値から計算する

要素数が 5 の配列 tana に、正の整数を入れていきます。IPAが公開している科目Bの問題と同じく、配列の要素番号は 1 から始まるものとします。はじめは5つとも －1 にしておきます。－1 は「まだ何も入っていない」の印です。入れる値は正の整数だけなので、印と値を取りちがえることはありません。

どの要素番号に入れるかは、入れる値そのものから計算します。

13 と 20 を、この順に入れます。

値を入れておくこの配列をハッシュ表、格納位置を計算する式をハッシュ関数、計算で出た値（ここでは要素番号）をハッシュ値といいます。

探すときも、同じ計算をします。13 を探すなら (13 mod 5) ＋ 1 ＝ 4。4番を見ると、13 があります。入れるときと同じ式で番号を出すので、入れた場所をそのまま見に行けます。前から順に 1番、2番と見ていく必要がありません。

衝突 ── 同じ番号になったら、次の番号へ

続けて 18 を入れます。(18 mod 5) ＋ 1 ＝ 3 ＋ 1 ＝ 4。13 を入れた番号と同じです。このように、別の値なのに同じ番号になることを衝突といいます。

4番に 18 を書くと 13 が消えてしまいます。そこで、ふさがっていたら次の番号を見ると決めておきます。次もふさがっていたら、さらに次へ。空きが見つかるまで続けます。

入れるプログラムを、上から読む

ここまで手でやったことを、プログラムにします。ireru が値を1つ入れる手続、junbi が 13・20・18 を順に入れる手続です。

大域: 整数型の配列: tana

○ireru(整数型: atai)
  整数型: i ← (atai mod tanaの要素数) ＋ 1
  while (tana[i] ≠ －1)
    i ← (i mod tanaの要素数) ＋ 1
  endwhile
  tana[i] ← atai

○junbi()
  tana ← {5個の －1}
  ireru(13)
  ireru(20)
  ireru(18)

当サイトで作った例です。

junbi の1行目 tana ← {5個の －1} は、5つの要素をすべて －1 にする書き方です。junbi を呼び出すと、tana は {20, －1, －1, 13, 18} になります。図で見た並びと同じです。

探す ── 入れたときと同じ順にたどる

探す関数 sagasu です。見つかったらその要素番号を、無ければ －1 を返します（要素番号は 1 からなので、－1 は番号としてありえない値です）。tana は入れるプログラムと同じ大域の配列で、3つの値を入れ終えた {20, －1, －1, 13, 18} になっているとします。

○整数型: sagasu(整数型: atai)
  整数型: i ← (atai mod tanaの要素数) ＋ 1
  while (tana[i] ≠ －1)
    if (tana[i] ＝ atai)
      return i
    endif
    i ← (i mod tanaの要素数) ＋ 1
  endwhile
  return －1

当サイトで作った例です。

最初の番号の出し方も、次の番号への進み方も、ireru と同じです。ちがうのは2か所です。進む前に if で探している値かどうかを確かめ、同じなら return i でその番号を返して終わります。空きに当たって while を抜けたときは、値を入れる代わりに return －1 で「無い」と答えます。

衝突して5番に入った 18 を探します。sagasu(18) が返すのは 5 です。

18 は 4番 → 5番 と進んで入ったので、同じ 4番 → 5番 と進めば必ず出会います。

無い値を探すと、空きで止まる

入れていない 23 を探すと、どこでやめるのでしょうか。sagasu(23) を1行ずつ動かします。5番の次が 1番に戻るところも出てきます。

空きに当たったら「無い」と言い切れるのは、もし 23 を入れていたなら、入れるときも同じ 4番 → 5番 → 1番 → 2番 と進み、空いている2番に入れたはずだからです。この例は 5つのうち 3つが埋まっているので 4か所を見ましたが、空きが多い表ほど、早く空きに当たって止まります。

出題では ── ふさがっていたときの決まりを読む

  return (value mod hashArrayの要素数) ＋ 1

ちがうのは、ふさがっていたときです。この問題は次の番号へ進みません。2つ目の関数 calcHash2 の式で、もう一度だけ番号を計算し直し、そこもふさがっていたら、入れずに false を返します。

この問題を最後まで解く手順は、令和5年度 科目B 問4の解説にあります。

つまずきポイントまとめ

次に読む