１．１ハッシュ法の原理 　ハッシュ法はデータの個数によらずに挿入、探索、削除の操作を実質的にo(1)つまり一定時間で行える優れたデータ構造です。ハッシュ法の原理は、キーの値を、データが格納される位置（配列の添え字の値）に直接関連づけてしまうというものです。ハッシュ法の原理は、線形探索法や二分探索法とは根本的に異なっています。 　ある特定の範囲内に収まる整数（0〜99としたとき）をキーにもつ一連のデータがあるとします。また、話を簡単にするためにキーの重複は許されないことにします。このデータを表に登録して、探索を行うことを考えます。 　もちろん線形探索法や二分探索法を使うこともできます。しかし、キーが特定の範囲に収まる整数であることを利用すれば、きわめて効率よく処理することが可能です。大きさ１００の配列ｘを用意して、キーの値ａをこの配列の添え字とします。つまり、キーが０のデータはx[0]に、キーが３７のデータはx[37]にという具合に対応させるわけです。この方式をとれば、挿入、探索、削除ともにo(1)で実行できることは明らかです。 　ここでもう少し細部をくめておきましょう。配列の各要素について、データがセットされているかどうかを区別する仕組みが必要になります。これには、２つの方式が考えられます。 　１つは明示的にフラグをもたせる方式です。たとえば、次のようにします。 struct { int occupied; DATA your_data; } x[100]; ここで、メンバoccupiedはデータがセットされていることを示すフラグで、0以外であればデータがセットされます。 　またもうひとつは明示的にフラグをもたないもので、データとして決して現れない値によってデータがセットされていないことを示すものです。たとえば、もしデータが（文字列などへの）ポインタだったら、データがセットされていないことを示すのにＮＵＬＬを使うのが自然でしょう。 　さて、話を元にもどせば、たった今考察したケースは、キーが0〜99の整数である、という前提によって成り立っています。しかし、これはあくまでも説明をするための設定で、現実にはキーをそのまま配列の添え字にできるのはまれでしょう。（キーが0〜10000000）の間にほぼ均一に分散している場合を考えてみてください）。 　そこでキーの値xを配列の添え字へ写像する関数h(x)を導入します。この関数をハッシュ関数と呼びます。また、ハッシュ関数が返す値をハッシュ値といいます。ハッシュとはもともと「細かく切りきざむ」という意味です。つまり、キーの値を「切り刻む」ことによって、無理やり配列の添え字にしてしまうわけです。 　ハッシュ関数h(x)を用意すれば、キーの値に応じて配列にデータを格納することができます。データを格納する配列tableがあるとすると、キーａをもつデータは配列の要素table[h(a)]にセットされます。ハッシュ関数として計算量がo(1)のものを選べば、挿入、探索、削除ともにo(1)で実現できることになります。 　データを格納する配列をハッシュ表、ハッシュ表の各要素をパケットと呼びます。キーの値から（ハッシュ関数によって）ハッシュ値を求め、ある特定のパケットに結びつけることによって、高速な探索を実現するのが、ハッシュ法です。 １．２衝突 　さてここまで説明したハッシュ法の説明ですが、実は重大な欠陥があります。それは、ハッシュ関数が異なるキーに対して、同じハッシュ値を生成する可能性があるからです。 　たとえば、文字列をキーとするデータを、大きさが１００の配列に格納することを考えましょう。ハッシュ関数は、文字列中のすべての文字コードを加算します。ハッシュ関数はList1のようになります。これは、最良とはいえませんが計算が簡単なので文字列のハッシュ関数として、しばしば利用されます。最後に１００で除算した余りをハッシュ値としていることに注意しましょう。この操作によって、ハッシュ値は必ず０から９９の範囲に収まります。 　さて、このハッシュ関数にoneからtenまでの文字列を与えて得られたハッシュ値をTable1に示します。ここでfiveとnineのハッシュ値はともに２６となっています。このように異なったキーに対して、同じハッシュ値が得られることを衝突といいます。衝突が起こった場合、何らかの対策をしなければハッシュ法は使いものになりません。 　衝突が発生しても、それを回避して正しく探索を行う方法があるので、実用上は問題ありません。しかし、あまり頻繁に衝突が起こると探索に時間がかかり、高速性というハッシュ法の利点が失われます。ですから、すべてのパケットに均等に振り分けるようなハッシュ関数を選択しなければなりません。ハッシュ関数については、後程考察します。 　衝突の対策には２通りの方法があります。第１の方法は、同じハッシュ値を持つデータを連結リストにつないでおくものです。第２の方法はハッシュ値に対応するパケットがすでにふさがっていたら、ある手順に従って別のパケットにデータを格納するという方法です。 　これら２つの方式の名前ですが、前者をchaining(チェイン法、連鎖法)、後者をopen addressing（オープンアドレス法、開番地法）とよんでいます。 /*list1*/ int hash(char *s){ int i = 0; while (*s) i += *s++; return i % 100; } //Table1：文字列のハッシュ値 　　文字列　　ハッシュ値 -------------------------- one 22 two 46 three 36 four 44 five 26 six 40 seven 45 eight 29 nine 26 ten 27 2.1チェイン法の原理 　まず、最初にチェイン法について説明しましょう。チェイン法は、同じハッシュ値をもつでーたを連結リストにつなぐという方式です。Fig1のようにハッシュ表には連結リストへのポインタを入れ、データはポインタでつないでおきます。fig1ではパケット0（ハッシュ値が0）にはＡ，Ｂという２つのデータが登録されています。また、パケット１は空です。 　探索を行うには、まずハッシュ値を計算しパケットを決めてから、そのパケットに連結されているリストを線形探索します。線形探索には連結リストの長さに比例した計算量がかかりますから、連結リストが長くなりすぎないようにしなければなりません。挿入と削除については、ハッシュ値を求めてパケットを求めてから、連結リストの挿入・削除と同じ処理を行います。 //Fig1：チェイン法 ハッシュ表 --------　　　　　　　ポインタでつながれる 0 ――――→　Ａ　　――→　　Ｂ -------- 1　　空 -------- 2　　　――――→　Ｃ　　 -------- 3　　空 -------- 4　　　――――→　Ｄ　　――→　Ｅ　――→　Ｆ -------- 5　　空 -------- 6　　空 -------- 7　　　――――→　Ｇ -------- 8　　　――――→　Ｈ　　――→　Ｉ -------- 9　　　――――→　Ｊ　　 -------- ２．２チェイン法のプログラム 　それでは実際にチェイン法のプログラムを書いてみましょう。まず、連結リストのセルを定義します。ハッシュ表で管理するデータは、ＫＥＹ型のキーをもち、ＤＡＴＡ型のデータをもつとすると、セルを表す構造体ＣＥＬＬ型は次のようになります（ＫＥＹ型とＤＡＴＡ型は、あらかじめ適当な型としてｔｙｐｅｄｅｆ宣言しておきます） 　typedef struct cell { KEY key; DATA data; struct cell *next; } CELL; 　ハッシュ表の本体は、ＣＥＬＬ型へのポインタの配列として実現されます。ここで、BUCKET_SIZEは、ハッシュ表に含まれるパケットの数を表す定数で、マクロ定義しておきます。 　　　CELL *table[BUCKET_SIZE]; 　また、これらのほかに２つの補助的な関数―hashとkeyequel―を準備しておきます。関数hashは、ハッシュ値を計算する関数で、パラメータとしてキーを与えると、そのキーに対するハッシュ値（int型）を返します。プロトタイプで表現すると次のような仕様になっています。 　　　int hash(KEY key); 　関数keyequalは、キーの値を比較するための関数で、パラメータとして２つのキーを与えると、それらが等しい場合には１を、等しくない場合には０を返します。プロトタイプ宣言は次のようになります。 　　　int keyequal(KEY a, KEY b); 　チェイン法を実現するには、挿入、探索、削除の３つの関数のほかに、ハッシュ表の初期化を行うための関数も必要になります。チェイン法によるプログラムをList2に示します。このリストでは、init,find,insert,deleteという４つの関数が定義されていますが、それぞれ初期化、探索、挿入、削除の処理を行います。 /*List2：チェイン法によるプログラム*/ /*ハッシュ表の定義*/ #define BUCKET_SIZE 50 /*ハッシュ表の大きさ*/ typedef struct cell { KEY key; DATA data; struct cell *next; } CELL; CELL *table[BUCKET_SIZE]; /*init ハッシュ表を初期化する*/ void init(){ int i; for(i=0;inext) if(keyequal(key, p->key)) return &p->data; return NULL; } /*insert　ハッシュ表にデータを挿入する　　　　　　　　　*/ /*　　　　登録に成功したら１を返す　　　　　　　　　　　*/ /*　　　　登録に失敗（すでに同じキーをもつデータがある）*/ /*　　　　したら０を返す　　　　　　　　　　　　　　　　*/ int insert(KEY key, DATA *data){ CELL *p; int h; if(find(key) != NULL) return 0; if((p = malloc(sizeof(CELL))) == NULL){ fprintf(stderr,"out of memory\n"; exit(2); } h = hash(key); p->key = key; p->data = *data; p->next = table[h]; table[h] = p; return I; } /*delete　ハッシュ表から削除する　　　　　*/ /*　　　　削除が成功したら１を返す　　　　*/ /*　　　　データが見つからなければ０を返す*/ int delete(KEY key){ int h; CELL *p, *q; h = hash(key); /*そのパケットは空か*/ if(table[h] == NULL) return 0; /*リストの先端のセルが削除すべきデータかどうか*/ if(keyequal(key, table[h]->key)){ p = table[h]; table[h] = p->next; free(p); return 1; } /*リストの二番目以降のセルについて順番にチェックする*/ for(q = table[h], p = q->next; p != NULL; q = p, p = p->next){ if(keyequall(key, p->key)){ q->next = p->next; free(p); return 1; } } return 0; } 2.3チェイン法の解析 　さてここでチェイン法がどのような性質をもっているかを考察しましょう。パケットの数をＢ、登録するデータの数をＮとします。また、ハッシュ関数は、全データのすべてのパケットに均等に振り分けるようなハッシュ値を生成すると仮定します。このとき、各パケットには平均Ｎ／Ｂ個のデータが入ることになります。 　探索を行うには、まずハッシュ値を求めてどのパケットを探すべきかを決めます。この計算量はo(1)です。次に連結リストを線形探索するわけですが、リストの長さは平均でＮ／Ｂなので毛山稜はo(Ｎ／Ｂ)になります。したがって、探索全体の計算量はo(１＋Ｎ／Ｂ)となります。 　挿入そのものの計算量は、連結リストの先頭に要素を挿入するだけなのでo(１)ですみます。しかし、キーの重複チェックのために探索を行わなければならないので、計算量は結局o(１＋Ｎ／Ｂ)になります。 　削除についても、連結リストからデータを取り除くにはo(1)ですみますが、対象となるデータを探し出すのに同じだけの手間がかかるので、結局は計算量はo(１＋Ｎ／Ｂ)かかります。 　ところで、o(１＋Ｎ／Ｂ)という計算量は、実際にどの程度のものなのかを考えて見ましょう。データの個数Ｎに対してパケットの数Ｂが十分に大きければ、実質的にはＮ／Ｂを定数とみなすことができます。このとき、計算量はo(Ｎ／Ｂ)=o(1)となります。つまり、データの個数に対して十分なパケットを準備しておけば、一定時間で探索挿入削除の各操作を行えることになります。たとえば、５０個のパケットを用意してそこに２００個のデータを登録する場合、これらの操作はo(1)であるとみなすことができるでしょう。しかし、５０個のパケットに１００００個のデータを登録する場合には、もはやＮ/Ｂを定数としてみなすことはできません。計算量はo(1+N/B)=o(N/B)=o(N)となってしまいます。 　チェイン法は、連結リストを用いた線形探索法を改善したものと考えることができます。パケットに振り分けるというまえ処理によって、連結リストの長さを短く保ち、見かけ上、一定時間で探索をできるようにしているわけです。データの数に比べてパケットの数が少なすぎると連結リストが長くなってしまい、探索にかかる時間とみなせなくなります。 　チェイン法ではＮ／Ｂが大きくならないようにする必要があります。つまり、あらかじめデータの個数を見積もり、十分な数のパケットを用意しておかなければなりません。もしメモリ容量が許すのなら、パケットの数をデータの数より大きくしておくこともできます。