物事はシンプルであればあるほど記憶しやすく、
計算量：ハッシュサーチの場合O(1)
バイナリサーチは十分高速な検索アルゴリズムです。これ以上早いアルゴリズムがあるのでしょうか。結論から書くと、
一般に検索のキーは整数ではなく文字列です。例えば住所録、
ハッシュサーチ
ハッシュサーチの計算量はO(1)です。
O (1)もう少し具体的に解説しましょう。
ハッシュとは、
ハッシュを行う関数をハッシュ関数といいます。Java言語では、Hashtableクラス）
ハッシュ関数のコード例
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を得ますから、 「ありません」 と返答します。
- ・
これがハッシュ関数をデータ構造に利用した例です。
このコードは決して実用的ではありませんし、
実用的には、
今回はハッシュのおおよその理屈と仕組みを知ってもらえば十分ですから、
O (1)のアルゴリズムは常に最速か？
誤解を避けるために、
O (1)というアルゴリズムは、
ハッシュのキーは、
オーダー記法は、
問題 ハッシュサーチのプログラムを作りましょう。
前回までに利用したのと同じ整数の配列をハッシュサーチで検索するプログラムを作ってください。Java言語には、
前回までと同様、
これまでの検索では
解説
問題 ハッシュサーチのプログラムを作りましょう。
それでは以下にハッシュサーチのコードを示します。お手元の環境での実行時間を計測してみてください。
それにしても、
ソースコード：HashSearch.
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プログラムを実行してみると、
先だって紹介した、
整数の偶奇判定、
ちょっと実験 データが極端に少ない場合
さて、
実験
ソースコードLinearSearch.int len = 100000; をint len = 10; に変えて実行してみてください。同様に、検索対象となるデータの個数を、
ちょっと実験の結果
皆さんの実行環境に大きく依存しますので、
LinearSearch.
私の環境では、
処理対象となるデータの量が少ないと、
実際のプログラミングでは、
今回はここまで
O (1)となるハッシュサーチを紹介しました。また、
次回は、