アルゴリズムとデータ構造
演習第 12 回
サーチ３（ハッシュ）

ハッシュ法 （アルゴリズムＣ 第２巻 p.45） によって表を作って、それを元にサーチする方法です。

問題１ ［印刷用 PostScript］

このようなハッシュ関数 hash() と二重ハッシュ関数 hash2() がある。 

int hash(char c){
  return (int)(c-64)%M;
}
int hash2(char c){
  return (int)8-(c-64)%8;
}

(1) 次のデータのハッシュ値を求め、 分離連鎖法でハッシュしたときにできるハッシュ表を書きなさい。 表の長さ M は 11 とする。 

W H I T E C H O C O L A T E

(2) 次のデータのハッシュ値を求め、 線型探査法でハッシュしたときにできるハッシュ表を書きなさい。 表の長さ M は 9 とする。 

P U D D I N G

(3) 次のデータのハッシュ値を求め、 二重ハッシュ法でハッシュしたときにできるハッシュ表を書きなさい。 表の長さ M は 9 とする。 

P U D D I N G

分離連鎖法（アルゴリズムＣ 第２巻 p.48）
分離連鎖法
キーのハッシュ値を求め、そのハッシュ値に対応するリストに繋いでいきます。

線型探索法（アルゴリズムＣ 第２巻 p.51）
線型探索法
キーのハッシュ値を求め、そのハッシュ値に対応する場所に入れます。 その場所がすでに埋まっている場合（衝突）は、空いている場所が見つかるまで 右にひとつずつずれていきます。

二重ハッシュ法（アルゴリズムＣ 第２巻 p.53）
二重ハッシュ法
線型探索法とほぼ同じですが、衝突した場合は二重ハッシュ関数で求めた ハッシュ値分ずつずれていきます。

問題２

次のハッシュ関数を使って、 分離連鎖法でハッシュを行なうプログラムを書きなさい。 データはキーボードから読み込み、最後にハッシュ表を出力すること。 表の長さ M は 5 とする（ex12-2-skel.c） 

int hash(char c){
  return (int)(c-64)%M;
}

実行例：
% ./a.out
Input data: CHOCOLATE
 0: E T O O 
 1: A 
 2: L 
 3: C H C 
 4:

表の長さ M 分だけリストを作成する必要があります。 今までのリストは head がひとつだけでしたが、 ここでは次のように配列にしておくと作りやすくなります。 

NodePointer heads[M];

リストに繋ぐ関数や表示する関数は、演習第２回 を参考にしてください。

注意：キーについて
教科書のプログラムではキーが文字列になっていますが、 演習では文字（char 型）としています。教科書のプログラムを参考にするときは、 その点に注意してください。また通常ではキーと他の情報がセットになっている （例えば教科書の info など）ことが多いですが、 ここでは簡単のため、キーだけを扱っています。
問題３

次のハッシュ関数を使って、 二重ハッシュ法でハッシュを行なうプログラムを書きなさい。 データはキーボードから読み込み、データを入れるたびに ハッシュ表を出力すること。 表の長さ M は 11 とする。（ex12-3-skel.c） 

int hash(char c){
  return (int)(c-64)%M;
}
int hash2(char c){
  return (int)8-(c-64)%8;
}

実行例：
% ./a.out
Input data: CHOCOLATE
      C               
      C         H     
      C O       H     
    C C O       H     
    C C O O     H     
  L C C O O     H     
A L C C O O     H     
A L C C O O     H T   
A L C C O O E   H T

うまくいかない場合は、途中でハッシュ値を表示させて、 うまく計算できているかを確かめてみてください。

Written by わかまつなおき