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

データの追加と検索

　今回の連載では、増減するデータの探索がテーマです。新しくデータを登録し、また、あとでそれを探しますが、始めに登録する際にはこのハッシュ関数を使って得られた値をインデックスとしてそこに登録します。

$index = h( $data );
$array[ $index ] = $data;

　配列における場所（インデックス）はデータそのものから決まります。一方、登録されているデータを探すには、次のようにします。

$index = h( $data );
$val = $array[ $index ];

　この$valがnullであれば、$dataが登録されていないことになります。これがハッシング（hashing）の基本的な考え方です。

　ハッシュ関数の処理に一定の時間がかかりますが、その計算量は登録されているデータ件数とは関係ありません。それで検索の性能はＯ(1)である、と言えるのです。

　ほかの文字列についてもハッシュ値を調べてみましょう。実行結果の全体を図2-1に示します。

　あれ？LISPは32ですね。32はすでにCが占めていました。少し下のPrologも同じ32になっています。これでは配列の同じ場所に2つ以上のものを格納することになってしまいます。

　実は、これが起こるのは当たり前です。うまく35カ所に分けて格納しようとしましたが、文字列を表す数値を足し算してそこから値を求めるのでは、その値がすべての文字列について異なるわけがありません。もちろん、"abc"と"bca"や"cba"は足し算の結果が同じ値になるので、これらもみな同じハッシュ値になるでしょう。このようにハッシュ値が同じ値になることを衝突（collision）と呼びます。

　衝突が起こると、データを登録する場合であれば場所が重なってしまうため、同じハッシュ値を持つものを格納することができません。なんとか衝突を回避、または逃げる方法を考えます。

衝突の回避（1）：ハッシュ関数の改良

　まず、衝突を起こさないようにする方法を考えましょう。理想は、ハッシュ関数がうまく値をばらけることです。実は、何が含まれるかわからないあらゆる文字列をうまく決まった範囲の数値に置き換えることは不可能です。そこで、できるだけ分散することを考えましょう。

　「"abc"も"bca"も同じハッシュ値になる」と述べました。これは今使っているハッシュ関数の問題です。一般に、名前を表す文字列にはある傾向があります。なんでもそうですがやはり先頭文字は重要です。イニシャルは大事ですよね。

　そこでハッシュ値を計算するとき、先頭の文字の「重み」を加えたらどうでしょう？そこで2番目のハッシュ関数を考えます（図2-2）。

　このハッシュ関数では、文字を表す数値を足し算するときに、先頭文字を3回加えています（最後に2倍したものを加えているので、最初の足し算の分と併せて3回です）。

　この実行結果は省略しますが、前の例よりも分散するように見えます。しかし、それでも衝突は回避出来ません。

　ハッシュ関数については、いろいろと研究がされており、ここでは先頭の文字に重み付けをした例を紹介しましたが、最後の文字に重み付けをする方法などもあります。

　このようにハッシュ関数を工夫することでハッシュ値を分散させる－理想的には衝突が起こらないようにする－ことを狙うのも重要な作戦ではあります。ただ、重要なことはハッシュ値の計算にあまり時間をかけてはいけない、ということです。Ｏ(1)といいながら、その「一定の時間」がかかりすぎたのでは高速検索の意味がありません。

　ハッシュ関数の研究はとても奥が深いのですが、ここではこれくらいにして別の戦略を立てることにします。