沢山のものの中から、一つのものを選び出すのは、なかなか手間のかかる仕事です。
例えば、昔読んだ本の中から、ある言葉の説明を見つけだそうとしても、なかなか
該当箇所が見つからないという経験は、誰にもあると思います。
こうしたとき、本に索引があると、スムーズに求める箇所を見つけられるかもしれ
ません。あるいは、辞書で意味を調べてそれで十分なら、もとの本にこだわらなくても
済む場合もあるでしょう。
本の索引にしろ、辞書にしろ、沢山の中かから一つのものを求める際に有効な
メカニズムの例です。索引は、ある言葉を、それが出現する本のページに対応させ
ます。辞書では、言葉は、あるルールに従って一意の順番に並べられていますので、
任意のページを開いても、検索すべきページの方向は、一意に決まります。
索引でも、キーワードは、辞書式順序で並べられているはずです。
コンピュータは、「リンゴについて知っていることは、何かないか?」といった
類の、質問に答えるのは非常に苦手です。ただ、あるテキストの中から「リンゴ」
という言葉の出現をすべて選び出すことは、コンピュータには出来ます。こうした
「シラミつぶし」は、ある意味で、コンピュータが得意なことと考えてもいいの
ですが、データが大きくなれば、計算時間・計算量ともに、全く非効率的な
アルゴリズムになってしまうことがあることを忘れてはいけません。
コンピュータが、本質的に得意なのは、数字で指定されたキーを、メモリー上の
アドレスに変換して、その内容を読み取ることです。ですから、読み取るべき内容が
文字列の比較などといったまどろっこしい方法を取らずに、配列の添字やポインタを
使って、直接アクセス出来るのなら、無条件でそうした方法を選ぶべきです。
Hashtableは、沢山のものの中から一つのものを選ぶという仕事を、コンピュータ にとって効率的に行おうための工夫です。
HashTableは、次のような方法で、データを構造化します。
索引の場合でも、それから先は、求めるキーワードをそのページで逐一探すしかあり ません。 hashed key を添字とする配列を、HashTableと思って構わないと書きましたが、 HashTableで最も基本的な「おおまかな検索」が、この配列上で行われるという意味で あって、実際の情報(キー/値)が、この配列の上に置かれているわけではありま せん。配列は、実際の検索の「出発点」を与えているだけです。 HashTableの場合でも、「こまかな検索」は、次のようにして行われます。
HashTableは、「キー」と「値」を設定し、「キー」を与えて「値」を獲得する という点では、先にみた Property とよく似ています。 実際、Property の 最も基本的な機能は、HashTableを継承することによって実現されています。 その意味では、HashTable のほうが、Propertyより、一般的な機能を備えていることに なります。例えば、Property の key/value が、String型に限られていたのに 対して、HashTableでは、任意の Object を、keyにもvalueにも設定することが 出来ます。
ハッシュ・テーブルに対して、あるキーのもとに、ある値を設定するには、put メソッドを使います。逆に、あるキーに対応する値を、ハッシュ・テーブルから 引き出すためには、getメソッドを使います。
次の例では、キー"one"に"一"という値が、キー"two"に"二"という値という ように、コンストラクタ trans の中でputを用いて、テーブルにキーと値が 登録されてゆきます。
import java.util.*; class trans { Hashtable h = new Hashtable(); trans(){ h.put("one" ,"一"); h.put("two" ,"二"); h.put("three","三"); h.put("four" ,"四"); h.put("five" ,"五"); h.put("six" ,"六"); h.put("seven","七"); } public static void main(String argv[]){ trans t = new trans(); for( int i = 0 ; i < argv.length ; i++ ){ System.out.println( (String)t.h.get(argv[i]) + " "); } } }
mainでは、引数で与えられたキーのテーブル上での対応する値を getで 獲得して、出力します。
$ java trans one two three four seven 一 二 三 四 七
次の例は、同じキーをもつものは、同じ場所に記憶されるというHashtableの 性質を利用して、引数で与えられたテキストに現われる単語の出現数を数える wordsCount.javaプログラムです。
import java.util.*; import java.io.*; class wordsCount { public static void main(String argv[]){ try { Hashtable h = new Hashtable(); FileInputStream in = new FileInputStream(argv[0]); StreamTokenizer st = new StreamTokenizer(in); int ret ; String word ; Integer n ; while(( ret = st.nextToken() )!= st.TT_EOF ) { switch( ret ){ case st.TT_WORD: word = st.sval ; n = (Integer)h.get(word); if ( n == null ){ h.put(word,new Integer(1)); } else { h.put(word,new Integer((int)(n.intValue()+1))); } } } for( Enumeration e=h.keys(); e.hasMoreElements(); ){ word = (String)e.nextElement(); System.out.println( word + ":" + (Integer)h.get(word) ); } } catch ( Exception e ){ System.err.println(e); } } }
次のような形式のファイルがあったとしましょう。 この時、各科目ごとの平均を出すのが、assoc2.javaです。
--------------------------------------- 数学 100 英語 90 国語 93 数学 82 英語 95 国語 78 数学 100 英語 64 国語 82 --------------------------------------- import java.io.*; import java.util.*; class assoc2 { Hashtable h = new Hashtable(); String subject = null ; int points = 0 ; assoc2(String filename){ int ret; try { FileInputStream in = new FileInputStream(filename); StreamTokenizer st = new StreamTokenizer(in); while( ( ret=st.nextToken() ) != st.TT_EOF ){ subject = st.sval ; ret=st.nextToken(); points = (int)st.nval ; System.out.println(subject + ": " + points ); register(subject,points); } } catch ( Exception e){ System.out.println(e); } } void register(String sbj, int p ){ Vector v = null; if ( ( v = (Vector)h.get(sbj)) == null ){ v = new Vector(); } v.addElement(new Integer(p)); h.put(sbj, v); } void show(){ String key=null; Vector v = null ; System.out.println( "--------------------- " ); for( Enumeration e = h.keys(); e.hasMoreElements(); ){ key=(String)e.nextElement(); v = (Vector)h.get(key) ; System.out.println( key + ": " + v.toString() + " --> " + avg(v) ); } } float avg(Vector v){ int n = v.size() ; int sum = 0 ; for( int i = 0 ; i < n ; i++){ sum += ((Integer)v.elementAt(i)).intValue(); } return ( float )( sum/n ); } public static void main(String argv[]){ assoc2 as = new assoc2( argv[0] ); as.show(); } }
Hashtableは、その性質を生かして、繰り返し利用されるリソースの cache としてよく使われます。例えば、大きなイメージデータは、ネットワーク上で やりとりすると時間がかかるのですが、プログラム中で一度使ったイメージを、 Hashtableにしまっておき、同じプログラム中で同じイメージに、再度要求があったら、 こんどは、Hashtableからデータをとるというような使い方をします。