ハッシュ

計算で置き場所を決める

ここまでのデータ構造は、目的の値を探すのに先頭からたどるか、木を下りるかしていました。ハッシュはまったく別の発想で、探すのではなく、値からその置き場所を計算します。

使うのはハッシュ関数と呼ばれる計算式です。格納したいデータの鍵 (キー) を渡すと、配列の添字にあたる数を返します。定番は表の大きさで割った余りを使う方法です。表の大きさが 11 なら、鍵 15 の置き場所は 15 を 11 で割った余りの 4 になります。

読み出すときも同じ計算をします。鍵 15 を探したければ、もう一度 15 を 11 で割って 4 番を1回見るだけです。表に何件入っていても計算1回で届くので、探索にかかる手間はデータ件数に関係なく一定、つまり計算量は O(1) です。件数が増えるほど遅くなる線形探索と比べると、この差は決定的です。

衝突をどうさばくか

上の例のように、違う鍵が同じ置き場所になることがあります。これを衝突 (シノニムの発生) と呼びます。鍵の種類は表の大きさよりずっと多いので、衝突は避けられません。ハッシュを使うとは、衝突をどう処理するかを決めることだ、と言えます。対処は大きく2通りです。

1つ目はチェイン法です。同じ置き場所になったデータを連結リストでつないで、その場所からぶら下げます。表の1マスがリストの先頭を指す形になります。探すときは計算で 4 番に来てから、そのリストを順にたどって鍵が一致するものを見つけます。実装が素直で、削除も要素を外すだけで済みます。

2つ目はオープンアドレス法です。ぶら下げずに、表の別の空きマスへ入れます。いちばん単純なのは、埋まっていたら1つ後ろ、それも埋まっていたらさらに1つ後ろ、と空きが見つかるまでずらしていく方法で、線形探索法と呼びます。上の例なら 26 は 5 番に入ります。探すときも同じ規則でずらしながら見ていきます。ずらして入れた事実が表に残らないため、途中のデータを単純に消すと後続が見つからなくなります。削除には印を付けるなどの工夫が要ります。

どこまで詰めてよいか

表がいっぱいに近づくほど衝突が増え、ずらす回数やリストをたどる回数が伸びて、O(1) の利点が薄れます。そこで、表の大きさに対してどれだけ埋まっているかの割合を見ながら、余裕を持った大きさを取ります。表の大きさに素数を選ぶことが多いのも、余りの散らばりをよくして衝突を減らすためです。

試験での問われ方

出題はほぼ2通りです。鍵と表の大きさを与えて格納位置を計算させる問題と、衝突が起きたときの動きや呼び名を答えさせる問題です。前者は余りの計算そのものなので確実に取れます。後者は、チェイン法とオープンアドレス法のどちらの説明かを読み分けられれば足ります。連想配列や辞書と呼ばれる仕組みの多くがハッシュでできているので、実務でも触れる場面が多い構造です。