ハッシュサーチの計算量

O (1)

Wikipediaに掲載されているハッシュ関数の例

1:unsigned int hash(char *s) {
2:    unsigned int h = 0;
3:    for (;*s != '\0'; s++) {
4:        h = h * 137 + *s;
5:    }
6:    return h % 1987;
7:}

この関数がどのように動作するのか見てみましょう。

関数の引数の文字型の配列sには"a\0"と格納されているとします。

• （1）h=0
• （2）*sは配列の先頭要素の値を表します。いまは'a'です。
• （3）aのアスキーコードはx61H(97)（※3）ですから，4行目の式の計算により，h=0*137+97=97となります。
• （4）s++により，*s='\0'なのでループ終了。
• （5）97 % 1987 = 97 。 %は剰余演算の記号（※4）です。

文字列"a\0"のハッシュ値は97となりました。

では，文字列変数sに"ab\0"と格納されていたとします。

• （1）h=0
• （2）*sは配列の先頭要素の値を表します。いまは'a'です。
• （3）aのアスキーコードはx61H(97)ですから，4行目の式の計算により，h=0*137+97=97となります。
• （4）s++で，*s='b'となり，'b'のアスキーコードはx62H(98)ですから，4行目の式の計算により，h=97*137+98=13387となります。
• （5）s++により，*s='\0'なのでループ終了。
• （6）13387 % 1987 = 1465

こうして，文字列"ab\0"のハッシュ値は1465となりました。

こうして計算できたハッシュ値はどのように利用されるのでしょうか。最もシンプルな場合ならば，こうです。

• （1）1987個の文字列変数を要素として持つ配列hasharrayを用意します。初期値は全てNULLをセットしておきます。
• （2）データ"a\0"は，ハッシュ関数値の値を利用して，hasharray[97]に格納します。"ab\0"はhasharray[1465]に格納します。
• （3）このhasharrayに対してデータの検索を行う場合，次のように行います。
  • ・データ"a\0"は格納されているか？という指示に対し，ハッシュ関数を計算し，hasharray[97]をチェックするとNULLではありませんでした。ですから，受けた指示への回答として，「ありますよ」と返答するのです。
  • ・"cd\0"は格納されているか？という指示に対しては，ハッシュ関数の計算と配列のチェックを行った後にNULLを得ますから，「ありません」と返答します。

これがハッシュ関数をデータ構造に利用した例です。

このコードは決して実用的ではありませんし，このコードこそが唯一のハッシュ関数のアルゴリズムではありません。ハッシュ関数の概略をよく示していますが，ハッシュ関数の実装のほんの一例です。

実用的には，用意したメモリスペース内に，格納するデータをまんべんなく配置出来るような工夫をしっかり実装する必要があります。同じところに違うデータを格納できませんから，重複を回避する工夫も必要です。

今回はハッシュのおおよその理屈と仕組みを知ってもらえば十分ですから，この程度の解説で止めます。おおよその理屈を理解した上で，Java言語に標準で用意されているデータ構造を有り難く利用させてもらうのが，たいていは一番です（※5）。

※2）

キーとなる文字列の長さをnとしてO(n)です。

※3）

16進数で61，10進数で97という意味です。以下，同様に表記します。

※4）

Java言語もC言語と同じです。連載第3回を参照下さい。

※5）

というのも，プログラミング言語といえども人の作ったモノですから，間違いがあったり，効率の悪いアルゴリズムが使われているかもしれないからです。それに気がついて，嫌だなぁ，と感じられるところまで登っていきたいですね。

O (1)のアルゴリズムは常に最速か？

誤解を避けるために，ここで一度まとめておきます。

O (1)というアルゴリズムは，「一度しか計算手順を必要としないアルゴリズム」とは限りません。「どんなに入力量が大きくても，およそ一定の計算手順で終了するアルゴリズム」のことです。ハッシュを用いたデータ構造にアクセスするためには，キーを与えてハッシュ値を得れば，求める値が一発で得られます。マクロに見れば，計算手順は「ハッシュ値の計算をする」の1つだけのようです。しかし，先にハッシュ関数のアルゴリズムで見たように，「ハッシュ値を計算する」という計算手順が何がしかの計算量を持っています。今回紹介したハッシュ関数の計算量はO (n)でした。では，ハッシュ関数を用いた検索はO(n)でしょうか？

ハッシュのキーは，たいていの場合で，ごく小さな文字列変数に格納されます。その長さは，取り扱うデータ量に比較すればとても短いはずです。たいていは文字列変数は固定長です。つまり，文字列長には最大値があります。すると，ハッシュ関数の計算実行量は，平均すればある定数，キーを格納する文字列の最大サイズ程度です。ですから計算量が一定，O (1)であると言えるのです。

オーダー記法は，あくまでオーダーであって，O (1)のアルゴリズムは，計算手順が常に1つだけだ，ということではありません。