Super Technique 講座

ハッシュテーブル

ハッシュテーブルは、中級の基本技である。「ハッカー」と呼ばれる程のプログラマならば、使いなれた自作ハッシュライブラリを持っていて当然である。また、これは非常に検索が速く便利なために、awk から Perl に至るスクリプト言語で、言語仕様に採り入れられてよく「連想配列」などと呼ばれている。要するに、

$List{'http'} = 80;

のように、配列なのに文字列を添字として取るような書き方をするアレである。これは「キー」である文字列に対して、「値」である何かのオブジェクトを返すという動作であり、そういう動作こそが「ハッシュテーブル」以外の何者でもない。ものすごく便利なので、ぜひマスターされたい。→ Java 講座の「ハッシュテーブル」




準備〜リスト版線形探査

ハッシュテーブルは、「キー」である文字列に対して、「値」である何かのオブジェクトを返す、つまり「キー」によって「値」を検索するというアルゴリズムだが、実はこれは線形探査にうまい仕掛けをして、検索効率を上げたものに過ぎない。だから、まず準備として、リストを使った線形探査を復習しよう。

struct List {
   char *name;    /* 検索キー */
   char *value;   /* 値(とりあえず文字列とする) */
   struct List *next; /* 次のデータ */
};

こういうデータ構造を前提として、線形探査をする。

char * searchList( char *key, struct List *l ) {
   while( l != NULL ) {  /* リストの最後まで */
       if( strcmp( key, l->name ) == 0 ) { /* 比較 */
           return l->value; /* 見つかれば値を返す */
       }
       l = l->next; /* 「次」を見る */
   }
  return null;
}

単純である。こういう「キーと値」のペアになったデータを検索することで、「連想リスト」を作ることができるのは、皆さんOKのことだろう。しかし、このリストが長くなるにつれて、検索効率は落ちて来る。期待値はリストの長さの 1/2 であり、リストの長さが長くなれば、それに応じて検索効率が低下し、体感的にも遅くなる。これはなんとかしたい。

ハッシュテーブルの原理

人間がマニュアルでソートをする時に、例えば数値でソートするのならばあらかじめ10の桁で整理しておいて、それから各10の桁の山に対して更にソートするのは、ごく常識的なことである。つまり、あらかじめデータを小分けにしておけば、それを線形探査するのであっても、かなり速くできることは言うまでもない。

だから、ハッシュテーブルでは、データを「小分け」にする。つまり、単純な線形探査ではリストの先頭は1つしかないが、ハッシュテーブルでは、リストがあらかじめ整理されていて、いくつもの先頭が即座にアクセスできる配列に入っているのである。だから、1つの配列に入っているリストの量はたかが知れており、線形探査でも大した負担ではない。

ではどうやって小分けにし、検索すべきデータが「どの配列に入っているか」知ることができるのだろう。これに使うのが「ハッシュ関数」である。

「ハッシュ関数」っていうと、MD5 とか...などという人もいるだろう。実際には MD5 は特別な出来の良いハッシュ関数であり、ここでいう「ハッシュ関数」はもっと一般的で簡単なものである。先程の「10の桁で整理して...」の例で言うと、そのハッシュ関数の定義は次の通りである。

int getHash( int num ) 
{
   return num / 10;
}

つまり、探すべき数(num)と、それがある山(戻り値)の対応関係を計算する関数がハッシュ関数である。要するに「引数」と「ハッシュ関数値」とは、「多対1」の関係にあり、いくつかの数が同じ山にあることになるが、これは線形探査で解決すれば良いのでとりあえず問題ではない。

しかし、文字列の場合にはどうするのだろう。「良いハッシュ関数」とは、典型的なキーに対して「なるべく均等に」、見つけるべき「山」が分散するような値を返すのである。だから、筆者の得意なハッシュ関数の定義はこんな感じである。

#define HASHSIZE  127
struct List *HashTable[HASHSIZE];  /* ハッシュテーブル本体 */

int getHash( char *key ) 
{
    int len;
    int ret;

    /* 0文字目、最後の文字、真中の文字の数値を加算し */
    len = strlen( key );
    ret  = key[0];
    ret += key[len-1];
    ret += key[(len-1)/2];
    /* ハッシュテーブルのサイズ(山の数)で modulo する。*/
    return ret % HASHSIZE;
}

このハッシュ関数値によって、セットし検索すべき「山=ハッシュテーブル」を決定することができる。ハッシュテーブルには線形リストの連想リストが入っているのであり、「山」が決まれば、あとは線形探査をするだけである。

ライブラリの実装

では、まず「キー」と「値」をセットする関数を作ってみよう。

void setValue( char *key, char *value )
{
    int hash;
    struct List *add;
    hash = getHash( key );  /* ハッシュ値を計算 */

    if( HashTable[hash] == NULL ) {  /* もしハッシュテーブルが空ならば */
       add = newList();             /* データノードを作成し */
       add->name = (char *)strdup( key );
       add->value = (char *)strdup( value );
       add->next = NULL;
       HashTable[hash] = add;        /* 単にセット */
    } else {  /* 線形探査が必要 */
       struct List *at = HashTable[hash];  /* 先頭をセット */
       while( at != NULL ) {
           if( strcmp( at->name, key ) == 0 ) {  /* すでにあれば... */
               at->value = (char *)strdup( value ); /* 値のみ更新 */
               return;
           }
           at = at->next;  /* 次のチェーンを辿る */
       }
       /* key がなかった → 先頭に追加 */
       add = newList();  /* malloc +エラー処理 */
       add->name = (char *)strdup( key );  
       add->value = (char *)strdup( value );
       add->next = HashTable[hash];  /* 以前の先頭を自分の次にする */
       HashTable[hash] = add;        /* 先頭に追加 */
    }
}

実にこの程度の内容に過ぎない。では、値の検索はどうするのか。

char *getValue( char *key )
{
    int hash;
    hash = getHash( key );  /* ハッシュ値を計算 */

    if( HashTable[hash] == NULL ) {  /* もしハッシュテーブルが空ならば */
       return NULL;        /* ない */
    } else {  /* 線形探査が必要 */
       struct List *at = HashTable[hash];  /* 先頭をセット */
       while( at != NULL ) {
           if( strcmp( at->name, key ) == 0 ) {  /* 見つけた! */
               return at->value;
           }
           at = at->next;  /* 次のチェーンを辿る */
       }
       return NULL;  /* 探したがなかった */
    }
}

まあ、こっちのが簡単である。それほどヘヴィなロジックでもない。この程度のロジックで、連想配列が簡単に手に入るのである。使わなくては損であるし、一度書いてしまえば、大概のプログラムで転用が効くタイプのライブラリになってくれるのも嬉しい。

また、ハッシュテーブルのサイズは「素数が良い」という実験結果がある。要するに、素数であると、データが均等にばらける可能性が高いのである。ハッシュテーブルの効率は1にも2にもデータが均等にばらけることにかかっている。最悪ハッシュ関数が裏をかかれた場合には、単に線形探査になるだけである。

他の応用

実はリストの線形探査を使わない方法もある。これは固定したサイズのハッシュテーブルに対して、検索開始点をハッシュ関数によって定める。あとは一種のリングバッファとしてハッシュテーブル自身に対して探して行く。セットするときには、すでにそのハッシュ値に対応した値が使われていれば、その次以降で空いている場所を探して入れる。このロジックはハッシュテーブルのサイズに対して、実際に使われるサイズがかなり小さい場合に、検索が速いというメリットがある。また、要求された内容に適当に同時にはダブらない番号を振っていくのにも使えるロジックである。よくこれを「オープンハッシュ」というような言い方で区別する。

いわゆる MD5 のようなメッセージ・ダイジェスト関数も、実際にはハッシュ関数の仲間である。MD5 は、テキストに対して演算を行うことで、適当な数値をハッシュ値として得る。これはいわゆる「ハッシュ関数」の動作そのものであり、理屈上、複数のテキストが同一のハッシュ値を得ることもありうる。しかし、MD5 の偉いところは次の特徴があることである。

  1. 複数のテキストから同一のハッシュ値が得られることは論理的にはありうるが、常識的なテキスト(テキストらしいテキスト)の範囲では、同じハッシュ値を取ることはほとんどありえない。
  2. 特に「似たテキスト(一部だけを変更したテキスト)」では、まったく違うハッシュ値が得られるべきである。つまり、1文字を変更しただけで、得られるハッシュ値は全然違うものになるべきである。

だから、テキストの変造がないことの証明に使われ、デジタル署名などの手段となっているのであるが、このようなメッセージダイジェスト関数も、動作自体はハッシュ関数であることは御理解いただけるのではないかと思う。

Java の Hashtable クラス

Java ではシステムが提供するデフォルトのライブラリ java.util.Hashtable でこのハッシュテーブルを実装している。今見て来たハッシュテーブルの機能が実装されているが、いくつかの特徴がある。本質的なものについてのみ指摘する。→ Java 講座の「ハッシュテーブル」

  1. 自己拡大型ハッシュテーブルである。デフォルトでは 101 個のテーブルを持っているが、これの使用率が 75% を越えると(つまり入っている要素が75個以上になったら)、自動的にテーブルサイズを拡大して、各エントリを割り当て直す(rehash メソッドを参照)。新しいテーブルサイズは (古いサイズ * 2 + 1) になる。これは検索効率を低下させないための工夫であるが、rehash する時には意外なスピード低下があるかもしれない。
  2. JDK 1.2 から、Collection フレームワークに対応したメソッドを追加している。要するに、キーや値を全体を「集合」として捉えようとする抽象レベルの工夫がなされている。
  3. すべてのキー値を Enumeration で列挙できる。
  4. 同一キーに対する値の重複は、古い値が新しい値に置き換わり、put メソッドの戻り値として、古い値が返る。



copyright by K.Sugiura, 1996-2006