プログラミング作法 第２章 アルゴリズムとデータ構造 ２．９ ハッシュテーブル
ハッシュテーブルは計算機科学の偉大な発明のひとつだ。ハッシュテーブルは配列とリストと多少の数学的処理を組み合わせて、効率よく動的データを記憶し取得できるデータ構造を作り出す。これらの典型的な応用例に、動的な文字列(キー)集合の個々のメンバに何らかの値(データ)を関連づけるシンボルテーブルがある。
ハッシュテーブルの発想は、キーをハッシュ関数に渡して、そこそこの大きさの整数範囲に均等に分布したハッシュ値を生成することにある。このハッシュ値は、情報が記憶されているテーブルのインデックスとして使われる。
実際のプログラミングでは、ハッシュ関数をあらかじめ定義しておき、たいていはコンパイル時に適当なサイズの配列を割り当てることになる。この配列のそれぞれの要素には、１個のハッシュ値を共有する項目同士をチェインするリストが入る。要するに、項目数ｎ個のハッシュテーブルは、平均の長さが(ｎ／配列のサイズ)のリストの配列だと言える。良好なハッシュ関数を選び、リストがあまりに長くなったりしない場合であれば、項目の取得はＯ(1)の処理になる。typedef struct Nameval Nameval; struct Nameval { char *name; int value; Nameval *next; /* チェイン中の次 */ }; Nameval *symtab[NHASH]; /* シンボルテーブル */
配列はどの程度のサイズにすべきだろうか。一般論として言えば、個々のハッシュチェインに含まれる要素がせいぜい２〜３個になる程度に配列を大きくとり、ルックアップ作業がＯ(1)になるようにすればいい。
さて次に、ハッシュ関数hashによって何を計算するのかを決めなければならない。この関数は決定性でなければならず、高速で、配列全体にデータを一様に分布させる必要がある。
ハッシュできるのは何も文字列に限った話ではない。物理シミュレーションで分子の３次元座標をハッシュすれば、３次元配列(Ｏ(xsize*ysize*zsize))ではなく、線形テーブル(Ｏ(分子数))にメモリ量を抑制できるだろう。
ハッシュテーブルはシンボルテーブル用の手法としても優れている。任意の要素に対してＯ(1)のアクセスが期待できるからだ。しかし制約もいくつかある。ハッシュ関数の出来が悪かったりテーブルサイズが小さすぎたりすると、リストが長くなる可能性があるのだ。リストはソートされていないので、これによって動作がＯ(n)になってしまう。ただ、たしかにソートされた順序で要素に直接アクセスできるわけではないが、要素を数えて配列を割り当て、そこに要素のポインタを入れてソートするのは簡単だろう。こういった制約はあるものの、正しく使えばルックアップや挿入や削除が一定時間で済む点は、ほかのテクニックには見られないハッシュテーブルの無類の特性だ。
問題２−１４
ハッシュ値はMULTIPLIER倍されている値を起点として値がつくられるので、NHASHのうちその付近の値にデータがかたよる可能性はある。
問題２−１５
void access(Nameval *val)
{
Namval *p;
int h;
h = hash(val->name);
for (p = symtab[h]; p != NULL; p = p->next) {
アクセス関数(p);
}
}問題２−１６
Nameval *symtab; /* ハッシュテーブル */
int nhash; /* ハッシュテーブルの配列サイズ */
/* ハッシュテーブルの平均リスト長がxを超えると、係数yに従ってハッシュテーブルを伸張する */
void remakeHash(int x, int y)
{
int i;
int cnt, ave;
Nameval *p;
int newnhash;
Nameval *new;
/* 平均リスト長を求める */
for (i = 0; i < nhash; i++) {
for (p = symtab[i]; p != NULL; p = p->next) {
++cnt;
}
}
ave = cnt / nhash;
/* 平均リスト長がxを超えると、ハッシュテーブルを係数yに従って伸張
* ハッシュテーブルはmallocで確保されているものとする
*/
if (ave > x) {
newnhash = nhash * y;
new = realloc(symtab, sizeof(Nameval) * newnhash);
if (new != NULL) {
symtab = new;
nhash = newnhash;
} else {
/* エラー発生時の処理(省略) */
}
}
}問題２−１７
/* ２次元座標を記憶するハッシュ関数 */
int hashXY(int x, int y)
{
int val;
/* アイデア１ 座標をシフトさせて組み合わせ、ハッシュ値を作成 */
val = (y << 16 | x); /* この方法だとハッシュ値の範囲が大きくなりすぎるか？ */
/* アイデア２ 座標を足したものの平方根からハッシュ値を作成 */
val = (int)sqrt(x + y); /* この方法だとハッシュチェインが長くなりそうな気がする */
return val;
}
