ハッシュ法

　ハッシュ法（hashing）は、メモリ上でデータを高速に検索するための手法である。各種のツリー構造とは異なり、静的な配列だけで簡単に実装でき、効率も極めて高い。このため、非常に実用的な手法として重宝である。
　配列上でデータを検索する手法には、ハッシュの他いくつかある。以下、単純な手法から順に説明していき、ハッシュ法の説明に至ることにしよう。
　ある小さな会社の社員情報をメモリ上で処理する場合を考えてみよう。社員情報のキーとして社員番号（整数）を用いることだけを決めておき、その他については考えないことにする。

（１）単純配列

　データの出現順に配列につめていく。もっとも単純かつ基本的な方法。
　データの挿入は高速だが、検索は端から順に見ていく（リニアサーチという）しかないため、平均するとデータ件数（社員数）の半分について処理が必要となる。
　この手法は遅いので、データ件数が多い場合には使われない・・・と良いのだが、多くのプログラマがこの方法しか知らないが故に、現実には件数が多い場合にも使われていると思われる。

（２）ソート済み配列

　あらかじめ配列上のデータをキー(この場合は社員番号）の順に整列しておく。こうすると、データの挿入には時間がかかる（後述）が、検索にバイナリサーチという手法が使えるので、高々log(N)回の処理ですむ。100万件のデータでも log(N)≒20 [*1]だから膨大なデータでも非常に高速である。
　一方、データの維持にはコスト（処理時間）がかかる。データの内容が固定的なもの（例：Visual Basicのキーワード・・・printなど）である場合や、データが発生するフェーズと参照されるフェーズがはっきり分れている場合（DXFの線種や複合図形定義）には、データをまとめてソートできるから、クイックソートなどの高速アルゴリズムを使用すれば N * log(N) の手間である[*2]。これは各種のツリー構造と遜色ない。しかし、データをためつつ使用する場合は、ソート済みの配列にデータを挿入するしかなく、処理時間はNの二乗のオーダーを要する（つまり遅い）。

（３）逆引き表

　小さな会社という前提なので、特殊なケースとして、社員番号が3桁の整数である場合を考えてみよう。この場合、社員番号は（0番がないとして）００１～９９９の1000種類弱しかない。このため、あらかじめ1000要素の配列を用意しておき、社員番号をインデックスとして配列に入れてしまうという方法がある。これを逆引き表という。鈴木さんの情報をいれる場合の擬似コードは以下のようになる。

    社員マスター[鈴木.社員番号] = 鈴木

　逆引き表の利点は、登録も検索も極めて高速であり、処理も単純なことである。一方欠点は、キーの範囲が小さくないと使えないことである。例えば、KCCSの社員番号は９桁だから10億通りの可能性があり、逆引き表は現実的でない。このため、逆引き表はあまり一般的ではない。

（４）ハッシュ表

　前述のようにKCCSの社員番号は９桁だが、社員数は1000人そこそこである。このため、社員番号を適当な関数で０～１０００（現実には余裕を見て1200くらいにとる）に写像できれば、逆引き表が使える。これをハッシュ関数といい、ハッシュ関数を使った逆引き表をハッシュ表という。
　簡単なハッシュ関数としては、社員番号を配列のサイズで割り算した余り、というのがある。今、配列のサイズを1201 [*3]とすると、

    h(n) = n mod 1021   (mod は剰余を求める演算子） 
    
    社員マスター[h(鈴木.社員番号)] = 鈴木

とすればよい理屈だが、一つ問題がある。一例として、筆者の社員番号は850604014 であり、1021で割った余りは746だが、他にも余り（ハッシュ値）が746の社員がいるかもしれない。これを衝突（collision：コリジョン）という。衝突があった場合の処理にはいろいろあるが、単純な対処としては、隣の欄を用いていく方法などがある。
　ハッシュ法は登録・検索とも極めて効率がよく、データ量が増えても検索の手間が変わらない[*4]という際立った特徴がある。にも関わらずハッシュ法が実務ではあまり使用されないのは、

1. ハッシュ法を知らない人が多い[*5]
2. ハッシュ表のデータはソートされていないし、キーの順に並べるに も手間が掛かる。
3. メモリ上のハッシュは簡単だが、ディスクファイル上では手間が掛かる

などの理由が想起される。
　上記のハッシュ関数は非常に単純だが、文字列（例えば氏名）によるハッシュ関数にはもう少し工夫が必要である。文字列のハッシュとして、筆者は以下のような関数を愛用している[*6]（C言語記述）。

long hash(char *s)
{
    int i;
    int L = strlen(s);

    for (i = 0; i < L; i++) {
        h = h * 37 + s[i];
    }
    return labs(h);
}

　ハッシュ関数は、キーの値から「でたらめな値」を作り出す関数だから、乱数生成のアルゴリズムと関連がある。上記は「線形合同法」という乱数生成法と良く似ている。他の著名な乱数生成法の中では「平方採中法」もハッシュ関数として利用できる。
　また、ハッシュ関数は、元の値からできるだけ重複しない値を作り出すわけだから、データの特徴を示す「電子指紋」としてハッシュ関数と類似の関数が使用されるケースがある。この場合は関数の値域を十分大きくし、関数を工夫することにより、現実のデータではまず重複の起り得ない関数が工夫されている。電子指紋は、データが改竄（かいざん）されていないことを示す場合などに使用されるので、電子商取引などに今後重要な分野である。
　さらに、ハッシュ関数は元のデータからでたらめな値を作り出すことから、一種の暗号化のことをハッシュと呼ぶ場合がある。これは不正確な用法だと思うのだが、ハッシュという語感[*7]からはぴったりくる。

目次