擬似言語のハッシュ探索とは？線形探索より速くなる仕組みを解説

ハッシュと聞くと、何か難しい暗号の話のように感じてしまう。

線形探索や二分探索は分かったのに、ハッシュ探索だけはどう動いているのか想像できない。そんな状態ではないでしょうか？

安心してください。ハッシュ探索の考え方は、とても身近なものです。

たとえば、図書館で本を探す場面を思い浮かべてみてください。棚を端から1冊ずつ見ていく人はいません。請求記号を見て、この本ならあの棚だと場所を決めてから向かいます。

ハッシュ探索は、これと同じことを計算でやっている方法です。値そのものから置き場所を計算し、そこを直接見に行きます。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務で使うプログラミング言語の辞書型や連想配列も、内部ではこのハッシュの仕組みで動いています。

この記事では、文法の説明ではなく、ハッシュ探索がなぜ速いのか、衝突したらどうなるのかという仕組みを、擬似言語のコードで一つずつ確かめていきます。

科目B全体でアルゴリズムがどう問われるのかを先に確かめたい人は、親記事から読むと位置づけがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

ハッシュ探索とは値から場所を計算する方法¶

はじめに、ハッシュ探索が他の探索とどこが違うのかを押さえましょう。ここがつかめれば、コードを読むときの見通しがぐっと良くなります。

線形探索は、配列の先頭から1つずつ比べていく方法でした。二分探索は、整列済みの配列の真ん中と比べ、調べる範囲を半分ずつ絞っていく方法です。

どちらも、比べながら場所を探しているという点では同じです。一方のハッシュ探索は、比べる前に場所を計算で決めてしまいます。

3つの探索の違いを表にまとめると、次のようになります。

ハッシュ探索の強みは、データが増えても比較回数がほとんど増えないことです。ただし、格納するときにも同じ計算で置いておく必要があります。

線形探索と二分探索の違いをもう一度確かめておきたい人は、こちらの記事で整理しておくと比べやすくなります。

【関連記事】擬似言語の線形探索と二分探索の違いとは？科目Bで差がつく探索の読み方

ハッシュ関数は剰余で作ることが多い¶

値から場所を計算する式のことを、ハッシュ関数と呼びます。そして計算で求めた場所の番号を、ハッシュ値と呼びます。

試験でよく出るのは、値を配列の要素数で割った余りを使う形です。要素数が 7 なら、どんな整数を割っても余りは 0 から 6 のどれかに収まります。

擬似言語の配列は1番目から数えることが多いので、余りに 1 を足して 1 から 7 の番号にそろえます。この +1 は見落としやすいので、コードを読むときに必ず確認してください。

余りの計算そのものに自信がない人は、剰余を扱ったこちらの記事で基本を先に固めておくと安心です。

【関連記事】擬似言語の余り（剰余）と割り算がわからない人へ｜偶数判定と桁の取り出しを解説

格納と探索で同じ計算を使う¶

ハッシュ探索を理解するうえで大事なのは、格納と探索がセットになっている点です。格納するときに計算した場所へ置いておくから、探すときも同じ計算で同じ場所にたどり着けます。

逆に言えば、格納の計算と探索の計算が少しでも違えば、探しても見つかりません。問題を読むときは、格納の関数と探索の関数で同じ式が使われているかを確かめましょう。

衝突が起きたらどうするか¶

ここまでの話だけなら、ハッシュ探索は必ず1回で見つかるように思えます。ところが実際には、違う値なのに同じ場所が計算されることがあります。

要素数が 7 のとき、15 も 22 も、7 で割った余りは 1 です。どちらも同じ番号の場所を指してしまいます。

このように、異なる値のハッシュ値が同じになることを衝突、またはシノニムと呼びます。ハッシュ探索の問題は、ほとんどがこの衝突の扱い方を問うものです。

衝突への対処には、大きく分けて2つの方法があります。

科目Bの擬似言語で出やすいのは、配列だけで書ける線形探査法です。この記事でも、線形探査法を例に動きを追っていきます。

空きを探すときは末尾から先頭に戻る¶

線形探査法では、ぶつかったら1つ隣の場所を見に行きます。では、配列の最後の場所でぶつかったらどうなるでしょうか。

答えは、先頭に戻って探し続けます。配列を輪のようにつなげて使うイメージです。

この戻り方も、剰余を使って1行で書けます。今の番号を要素数で割った余りに 1 を足すと、7 の次は 1 に戻り、それ以外は1つ先に進みます。

ハッシュ探索を擬似言語で読む¶

ここからは、実際のコードで動きを確かめていきます。IPAの公開問題そのものではなく、試験でよく見かける形をもとに作った例です。

表の要素数を 7 とし、格納する値はすべて正の整数とします。まだ何も入っていない場所には 0 が入っているものとします。

○整数型: hashSearch(整数型の配列: table, 整数型: key)
  整数型: m, idx, k
  m ← table の要素数
  idx ← (key mod m) + 1
  for (k を 1 から m まで 1 ずつ増やす)
    if (table[idx] が key と等しい)
      return idx
    endif
    if (table[idx] が 0 と等しい)
      return -1
    endif
    idx ← (idx mod m) + 1
  endfor
  return -1

見つかったら、その場所の番号を返します。空きにたどり着いたら、そこから先に目的の値はないので -1 を返します。

for の回数を m に制限しているのは、表が満杯で目的の値が無い場合に、永遠に回り続けないためです。1周して見つからなければ、最後の return -1 に進みます。

格納の流れをトレース表で追う¶

探索を追う前に、表にどう値が入ったのかを確認しておきましょう。空の表に、15、22、10、30、5 の順で格納したとします。

格納の処理は探索とほぼ同じで、空きが見つかった場所に値を置きます。それぞれの値がどこに入るかを表にすると、次のようになります。

22 は 15 とぶつかって、隣の 3 に置かれました。30 はもともと 3 を指していたのに、22 と 10 に先を越されて 5 まで押し出されています。

このように、線形探査法では衝突した値が近くに固まっていきます。固まりが大きくなるほど、後から来た値が遠くまで押し出されるのです。

見つかる場合と見つからない場合を追う¶

では、この表で 30 を探してみましょう。30 を 7 で割った余りは 2 なので、最初は場所 3 を見ます。

場所 3 には 22、場所 4 には 10 が入っていて、どちらも 30 ではありません。場所 5 でようやく 30 が見つかり、5 が返ります。

次に、表に無い 23 を探してみます。23 を 7 で割った余りも 2 なので、同じく場所 3 から見始めます。

場所 3 から 6 まではすべて値が入っていて、どれも 23 ではありません。場所 7 が 0、つまり空きだったので、ここで -1 を返して終わります。

見つからない場合のほうが、たくさんの場所を見ていることに気づいたでしょうか。空きに当たるまで止まれないので、固まりの中を最後まで歩くことになります。

探索問題で、見つからない場合をどう追うかをもっと練習したい人は、解き方の手順をまとめたこちらの記事も役に立ちます。

【関連記事】科目Bの探索問題の解き方｜線形探索と二分探索の見分け方

ハッシュ探索が速い理由と弱点¶

ここまでの動きを振り返ると、ハッシュ探索がなぜ速いのかが見えてきます。値から直接場所を計算するので、衝突が少なければ1回か2回見るだけで答えが出ます。

データが100件でも1万件でも、計算する式は変わりません。この性質から、ハッシュ探索は衝突が少ない限り、件数によらずほぼ一定の手間で探せると言われます。

表が埋まってくると遅くなる¶

一方で、弱点もあります。表の空きが少なくなると衝突が増え、先ほどの 30 や 23 のように長い距離を歩くことになります。

極端な場合、すべての値が同じ場所に固まると、線形探索と変わらない手間がかかります。ハッシュ探索が速いのは、あくまで値がうまく散らばっているときの話です。

だから実際の仕組みでは、表の大きさに余裕を持たせたり、値がばらけるように要素数を工夫したりします。要素数に素数を使う例が多いのも、余りが偏りにくくするためです。

ループの回数から処理の手間を見積もる考え方は、計算量の問題を扱ったこちらの記事で詳しく解説しています。

【関連記事】科目Bの計算量問題の解き方｜ループの形からオーダーを判断する

削除がやっかいな理由¶

もう一つの弱点は、値を削除するときです。線形探査法の表から値を消して単純に 0 に戻すと、困ったことが起こります。

たとえば先ほどの表で場所 4 の 10 を消して 0 にしたとします。そのあと 30 を探すと、場所 3 の次の場所 4 が空きなので、見つからないと判断してしまいます。

30 は場所 5 にちゃんと残っているのに、途中の空きで探索が止まってしまうのです。そのため、削除済みを表す特別な印を置くといった工夫が必要になります。

実務でもハッシュの考え方は身近¶

実務でも、ハッシュの考え方はあちこちで使われています。私が以前担当した集計処理では、数万件のデータを突き合わせるときに、毎回リストを先頭から探していたため処理に長い時間がかかっていました。

探す側のデータを辞書型に入れ替えただけで、処理時間は大きく縮みました。やったことは、線形探索をハッシュ探索に置き換えただけです。

試験でハッシュ探索の仕組みを理解しておくと、こうした場面で何が遅さの原因なのかに気づけるようになります。点数のためだけでなく、長く使える知識です。

シミュレーターで動かして確かめる¶

ここまで紙の上で追ってきましたが、最後は実際に動かしてみるのがいちばん確実です。自分で考えた場所と、実際に値が置かれる場所が一致するかを確かめられるからです。

Giji Academyの擬似言語シミュレーターでは、擬似言語のコードを1行ずつ動かし、変数や配列の値が変わる様子を見ることができます。idx が 2、3、4 と進んでいく様子を目で見ると、衝突のイメージがはっきりします。

おすすめは、格納する値の順番を入れ替えて試すことです。30 を先に入れると、30 は場所 3 に入り、22 のほうが押し出されます。

同じ値の集まりでも、入れる順番で置き場所が変わる。これを一度自分の目で確かめておくと、試験で配列の中身を問われても落ち着いて追えるはずです。

自分で手を動かして確かめたい人は、Giji Academyの擬似言語シミュレーターから配列や探索の講座を選んでみてください。読むだけの勉強より、ずっと記憶に残ります。

まとめ¶

ハッシュ探索は、値から格納場所を計算し、そこを直接見に行く探索方法です。端から比べる線形探索や、範囲を半分にする二分探索とは、場所の見つけ方が根本から違いました。

ハッシュ関数には、要素数で割った余りがよく使われます。擬似言語では配列を1番目から数えるため、余りに 1 を足す形が多いので注意しましょう。

違う値が同じ場所を指す衝突が起きたら、線形探査法では隣の空きを探して置きます。末尾まで来たら先頭に戻り、探すときも空きに当たるまで同じ順で見ていきます。

衝突が少なければ速く、表が埋まると遅くなる。この性質を理解しておけば、比較回数を問われても、配列の中身を問われても、落ち着いて答えられます。

最初は表を書きながらゆっくり追えば大丈夫です。何度か動かしてみるうちに、ハッシュという言葉への苦手意識もきっと消えていきます。