ソースでわかる！ハッシング

ハッシング

　これまでの2回で、増減するデータを格納して検索するための方法を2つ紹介しました。1つはリスト構造（linked list）、もう1つは二分探索木（binary search tree）です。

　この2つは、配列に対する線形探索（linear search）と二分探索（binary search）と同様の探索性能があることを示しました。アルゴリズム性能を表すオーダーＯで表すと、それぞれＯ(n)とＯ(log2(n))です。

　今回は、Ｏ(1)である方法を紹介します。今回もプログラムを使いながら見てみましょう。プログラムはこちら（http://www.thinkit.co.jp/images/article/159/3/15931.zip）からダウンロードできます（15931.zip/2 KB）。

　アルゴリズム性能がＯ(1)であるとは、「いつでも一定の時間でアルゴリズムが停止する」ということです。探索について言えば、「一定時間で目的のものを見つけることができる」ということです。

　そんな夢のような方法があるのでしょうか？

　ここではデータが増えたり減ったりする状況で考えます。ですから、データを新しく「追加／登録」することがあり、また「削除」もします。そのような状況で特定のデータを「検索」します。

　検索する速度を一定にするには、追加／登録する際にも工夫がいるでしょう。そこで、配列を考えます。その配列に文字列を追加／登録するわけですが、配列の何番目に登録すればあとで検索する際に素早く（つまりＯ(1)で）検索できるでしょうか？

　できるかどうかは別として、あるデータに対してそれを格納すべき「場所」（配列のインデックス）がわかればありがたいですね。格納すべき場所がわかるのであれば、逆に検索する際にも探すべき場所がわかることになります。

　図1-1のように、例えば"asm"は配列のAの場所に、"FORTRAN"はB、"COBOL"はCというように、その名前で格納する場所を決めるのです。これがハッシング（hashing）の考え方です。

名前（文字列）から「置き場所」が決まる？

　ここでプログラミング言語の名前のリストを登録することを考えます（図1-2）。

　名前から場所を決めるためにはなんらかの計算をしなければなりません。この計算をする関数をh()とします。いまのところ中身はブラックボックスにしておきますが、この関数に名前（文字列）を渡すと、その名前のための置き場所（配列のインデックス）を返却値として戻してくれるものとします。

　この名前のリストについて関数h()を通した結果を図1-3に示します。関数h()はhash.phpで定義されていますが、それについては後ほど説明します。

　実行結果のはじめのいくつかを見てみると図1-4のようになります。

　どうでしょうか？"asm"はインデックス6のところに格納すればいいわけですね。探すときもインデックスは6であることがすぐにわかります。

　さてh()の種明かしをしますが、その前にいくつか言葉の説明をしておきます。

　ある名前（文字列）に対して、なんらかの計算をして得られた固有の値をハッシュ値（hash value）と呼びます。そして、上の関数h()はまさにこの計算をするものでした。これをハッシュ関数と呼びます。ここで使ったh()を図1-5に示します。

　この関数は、文字列のそれぞれの文字を表す数値を足し算して、それを35で割った余りとしてハッシュ値を計算します。ここでは要素が35個あるので、35個の要素を持った配列に分散させるために35で割ります。これで、35個の名前が配列の決まった場所に収まることになります。

　これはデータを登録する場合のことですが、検索する場合を考えても同じことです。名前からそれが置かれている場所が特定できるので、すぐにそれを見つけることができます。

　どうでしょう？ハッシュ値を計算する手間は若干かかりますが、名前から場所がすぐに決まるのです。ちょっと話がうますぎるようですが、そのことは後ほど説明しましょう。