Hashtable

Hashtableとは

沢山のものの中から、一つのものを選び出すのは、なかなか手間のかかる仕事です。 例えば、昔読んだ本の中から、ある言葉の説明を見つけだそうとしても、なかなか 該当箇所が見つからないという経験は、誰にもあると思います。 こうしたとき、本に索引があると、スムーズに求める箇所を見つけられるかもしれ ません。あるいは、辞書で意味を調べてそれで十分なら、もとの本にこだわらなくても 済む場合もあるでしょう。

本の索引にしろ、辞書にしろ、沢山の中かから一つのものを求める際に有効な メカニズムの例です。索引は、ある言葉を、それが出現する本のページに対応させ ます。辞書では、言葉は、あるルールに従って一意の順番に並べられていますので、 任意のページを開いても、検索すべきページの方向は、一意に決まります。 索引でも、キーワードは、辞書式順序で並べられているはずです。

コンピュータは、「リンゴについて知っていることは、何かないか？」といった 類の、質問に答えるのは非常に苦手です。ただ、あるテキストの中から「リンゴ」 という言葉の出現をすべて選び出すことは、コンピュータには出来ます。こうした 「シラミつぶし」は、ある意味で、コンピュータが得意なことと考えてもいいの ですが、データが大きくなれば、計算時間・計算量ともに、全く非効率的な アルゴリズムになってしまうことがあることを忘れてはいけません。 コンピュータが、本質的に得意なのは、数字で指定されたキーを、メモリー上の アドレスに変換して、その内容を読み取ることです。ですから、読み取るべき内容が 文字列の比較などといったまどろっこしい方法を取らずに、配列の添字やポインタを 使って、直接アクセス出来るのなら、無条件でそうした方法を選ぶべきです。

Hashtableは、沢山のものの中から一つのものを選ぶという仕事を、コンピュータ にとって効率的に行おうための工夫です。

HashTableのデータ構造

HashTableは、次のような方法で、データを構造化します。

1. まず、何等かの変換ルールで、キーに整数を対応させます。こ の時、同じキーは、必ず 同じ数に変換される必要があります。この数を、hash code と呼ぶことにしましょう。

2. hash code を、ある数 size を超えないように変換します。 一番簡単なのは、hash code を size で割った余りを利用することです。こうして作られた数字を hashed key と呼ぶことにします。size が 100 なら、全てのキーは、0〜99の数字に対応付け られることになります。この場合、キーがいくら沢山あっても、hashed key の上限は 100に制限されているので、異なるキーが同じ hashed key に対応するということが 起こります。

3. 次に、可能な hashed key の数、すなわち、先のsize の大きさをもつ配列を用意 します。この配列が、HashTableと思ってもらって構いません。 キーから hashed key を得ることが、索引で求めるページ数を見つけることに対応 するとすれば、hashed key を添字にして、この配列にアクセスすることは、ページを 見つけ出すことに対応します。

4. 索引でページが分かったら、そのページを開きます。HashTableの場合にも、 全てのキーは、hashed key に変換され、同じ hashed key を持つキー達が、 同じ場所に整理されることになります。これで、「おおまかな検索」は終わります。 sizaが100の場合なら、おおまかにいって、検索の対象は百分の一に狭められたといって もいいのです。
   

   索引の場合でも、それから先は、求めるキーワードをそのページで逐一探すしかあり ません。 hashed key を添字とする配列を、HashTableと思って構わないと書きましたが、 HashTableで最も基本的な「おおまかな検索」が、この配列上で行われるという意味で あって、実際の情報（キー／値）が、この配列の上に置かれているわけではありま せん。配列は、実際の検索の「出発点」を与えているだけです。 HashTableの場合でも、「こまかな検索」は、次のようにして行われます。

   1. 配列上の「出発点」は、決まった構造を持ったオブジェクトを ポイントしています。 そのオブジェクトは、キーとその hash code 、キーに対応した値とともに、 「次」のオブジェクトへのポインタを持っています。これは、よく知られている 「リスト」と呼ばれる構造になっているわけです。

   2. 「こまかな検索」は、「出発点」がポイントするオブジェクトから始めて、 この「リスト」を順番にたどる形で、まず、その hash code を比較します。 一致しなかったら、リストをたどって次のオブジェクトに進みます。一致したら、 今度は、キー同士を比較します。キーが一致したら、そのオブジェクトが求める ものです。リストの最後まで来ても、見つからなければ、その情報は、この HashTableの中には含まれていないということになります。

HashTableは、「キー」と「値」を設定し、「キー」を与えて「値」を獲得する という点では、先にみた Property とよく似ています。　実際、Property の 最も基本的な機能は、HashTableを継承することによって実現されています。 その意味では、HashTable のほうが、Propertyより、一般的な機能を備えていることに なります。例えば、Property の key/value が、String型に限られていたのに 対して、HashTableでは、任意の Object を、keyにもvalueにも設定することが 出来ます。

put()/get()

ハッシュ・テーブルに対して、あるキーのもとに、ある値を設定するには、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
   一
   二
   三
   四
   七

Uniqunessのチェック

次の例は、同じキーをもつものは、同じ場所に記憶されるという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();
  }
}

cacheとしての利用

Hashtableは、その性質を生かして、繰り返し利用されるリソースの cache としてよく使われます。例えば、大きなイメージデータは、ネットワーク上で やりとりすると時間がかかるのですが、プログラム中で一度使ったイメージを、 Hashtableにしまっておき、同じプログラム中で同じイメージに、再度要求があったら、 こんどは、Hashtableからデータをとるというような使い方をします。