物事はシンプルであればあるほど記憶しやすく,
計算量:ハッシュサーチの場合O(1)
バイナリサーチは十分高速な検索アルゴリズムです。これ以上早いアルゴリズムがあるのでしょうか。結論から書くと,
一般に検索のキーは整数ではなく文字列です。例えば住所録,
ハッシュサーチ
ハッシュサーチの計算量はO(1)です。
ハッシュサーチの計算量
O (1)
もう少し具体的に解説しましょう。
ハッシュとは,
ハッシュを行う関数をハッシュ関数といいます。Java言語では,Hashtable
クラス)
- ※1)
- hash search
ハッシュ関数のコード例
WikiPediaには次のようなハッシュ関数のコードが掲載されています。この関数の計算量はどれだけでしょうか?
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となりました。
では,"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を得ますから, 「ありません」 と返答します。
- ・
これがハッシュ関数をデータ構造に利用した例です。
このコードは決して実用的ではありませんし,
実用的には,
今回はハッシュのおおよその理屈と仕組みを知ってもらえば十分ですから,
- ※2)
- キーとなる文字列の長さをnとしてO(n)です。
- ※3)
- 16進数で61,
10進数で97という意味です。以下, 同様に表記します。 - ※4)
- Java言語もC言語と同じです。連載第3回を参照下さい。
- ※5)
- というのも,
プログラミング言語といえども人の作ったモノですから, 間違いがあったり, 効率の悪いアルゴリズムが使われているかもしれないからです。それに気がついて, 嫌だなぁ, と感じられるところまで登っていきたいですね。
O (1)のアルゴリズムは常に最速か?
誤解を避けるために,
O (1)というアルゴリズムは,
ハッシュのキーは,
オーダー記法は,