O (1)

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]⁠。

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

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

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

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

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

問題　ハッシュサーチのプログラムを作りましょう。

前回までに利用したのと同じ整数の配列をハッシュサーチで検索するプログラムを作ってください。Java言語には、ハッシュ関数を利用したHashtableというデータ構造が用意されていますので、それを利用しましょう。

前回までと同様、検索実行時間を計測し、リニアサーチやバイナリサーチの場合と比較してください。

これまでの検索では「求める整数値が配列の何番目に格納されているか」というように検索しました。今回の問題では、配列の添え字がハッシュテーブルの返値で、配列に格納される整数値がハッシュテーブルの検索のキーとなります。Hashtableクラスを利用しますから、以上のことに注意をしてプログラムを作成してください。

解説

問題　ハッシュサーチのプログラムを作りましょう。

それでは以下にハッシュサーチのコードを示します。お手元の環境での実行時間を計測してみてください。

それにしても、Java言語には便利な道具が数多く用意されていますね。有り難いことです。

01:import java.util.Hashtable;
02:
03:public class HashSearch {
04:
05:  public static int exec(Hashtable vals, int target) {
06:    if (vals.containsKey(target)) {
07:      return (Integer) vals.get(target);
08:    } else {
09:      return -1;
10:    }
11:  }// end of exec
12:
13:  public static void main(String[] args) {
14:    int len = 100000;
15:    int[] data;
16:    data = new int[len];
17:    for(int i=0; i<len; ++i) data[i]=i;
18:    Hashtable <Integer, Integer>hasharray = new Hashtable<Integer, Integer>();
19:    for (int i=0; i<data.length; ++i){
20:      hasharray.put(data[i],i);
21:    }
22:    int result;
23:    int repeat = 10000;
24:    long time;
25:    time = System.currentTimeMillis();
26:    for (int i=0; i<repeat; ++i){
27:      HashSearch.exec(hasharray,3);
28:      HashSearch.exec(hasharray,27);
29:      HashSearch.exec(hasharray,(int)(len/2));
30:      HashSearch.exec(hasharray,(int)(len*2));
31:   }
32:   time = System.currentTimeMillis() - time;
33:   System.out.println(time + "[msec]passed.");
34:  }// end of main
35:
36:
37:  private static void resultPrint(int result){
38:   if (result != -1) {
39:     System.out.println("[ Found ] index key = " + result);
40:   } else {
41:     System.out.println("[Not Found]");
42:   }
43:  }// end of resultPrint
44:
45:}// end of HashSearch

プログラムを実行してみると、私の環境では94ミリ秒で検索が終了しました。リニアサーチに比べると、約50倍高速です。しかし、バイナリサーチに比べるとずいぶん遅いですね。

先だって紹介した、ハッシュ値を計算するコードや、ハッシュを利用したデータ構造にアクセスする、という部分のコードが、バイナリサーチの実際のコードよりもコンピュータにとっては大きな負担になっているのです。もっともっとデータの配列が大きくなれば、ハッシュを利用するメリットがバイナリサーチの場合よりも大きくなるでしょう。少なくとも今回の程度であれば、まだバイナリサーチの方が有利なのですね。

整数の偶奇判定、ある数が偶数か奇数か判定することは、O (1)の代表的な例で、実際これは高速です。計算量が同じオーダーであっても、どのような演算を1回、あるいは一定回数と数えるかで、実際にコンピュータで実行した場合にかかる時間はずいぶんと違うものなのです。

ちょっと実験　データが極端に少ない場合

さて、ここでちょっと実験です。ちょっと疑り深くなってみましょう。現実はいつも理論通りにはならないものです。条件を変えてプログラムを実行してみましょう。

検索対象となるデータの個数を、10万個から10個に変更してみます。検索対象の個数が極端に少ないと、アルゴリズムによる総検索時間の差はどう変化するのでしょうか。

ちょっと実験の結果

皆さんの実行環境に大きく依存しますので、必ずこうなるとは断言できませんが、実行時間は次のような大小関係になったのではないでしょうか。

LinearSearch.java < BinarySearch.java < HashSearch.java

私の環境では、上記のように計算量の値の大小とは逆の順になりました。

処理対象となるデータの量が少ないと、検索に要する時間よりもJava言語が裏で働いている時間の方が多くなってしまうからです。リニアサーチでは2つの数値が一致するかどうかの比較を行うだけですが、バイナリサーチでは中央値を求める処理と値の比較、ハッシュサーチはハッシュ値の計算をします。データの数が極端に少ないと、データの比較に要する時間に対して、検索を効率よく行おうとするため工夫を凝らした部分のコードの実行時間の割合が大きくなってしまったのです。

実際のプログラミングでは、このようなことも意識しておかないと、小さな計算量のアルゴリズムを採用しても、実際の実行時間は長くなってしまった、なんていう見立て違いをしてしまう、という事になる良い例です。

今回はここまで

O (1)となるハッシュサーチを紹介しました。また、少し突っ込んで、計算量の値と実際のコードの実行時間の違いについて、少しだけ詳しく見てみました。

次回は、これまでに紹介できなかった計算量になる代表的なケースをコード例とともに紹介します。お楽しみに。