出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．
この授業のトップページから レポートのページに移動し， レポートの提出状況を常に確認せよ．
実用の場面で高速にデータを挿入，検索，削除できるので よく利用される．
たとえばキーが0から99の整数しかありえないことが分っている 場合は大きさ 100 の配列 x を用意してしまってキーが i (0 <= i <= 99) であるデータを x[i] に書くことで定数時間で挿入，検索，削除ができる．
ハッシュ法はこの考え方を拡張したものである．実際にはキーとしてとりうる 値の範囲は大きいので（例えば「科目名」をキーとすると科目名として許される 文字数のすべての文字列がキーの値の範囲）すべてに配列で専用スペースを もたせることはできない．
キーのとりうる範囲よりも小さいサイズの配列（ハッシュ表） を用意し，キーをハッシュ表の添字の範囲の値に変換する関数 ハッシュ関数 を使う．ハッシュ関数は本質的に多対一関数になる． ハッシュ関数の返す値をハッシュ値という．
例えばキーが英語 52 文字の長さ 10 の配列だとする． この場合，キーの取りうる値は 5210 （約14京） となる．これをサイズが 100 のハッシュ表に格納する場合， 0 から 99 の 100 種類の数値に変換するのがハッシュ関数となる． 教科書 p.110 List8.1 の方法ではすべての文字コードの和を計算し， 最後に 100 で割った余りを求めて 0 から 99 の範囲の整数を 計算している．
関数の入力の種類よりも出力の種類が小さいため， 異なる入力が同じ出力になることがある．（多対一関数であるため） これを衝突という．教科書の例では "five" と "nine" が同じ出力値になっているため，ここで衝突が起こっている．
ハッシュ関数は本質的に多対一関数であるから衝突は避けられない． ハッシュ表の同じ添字のスペースにはデータは1個しか 格納できないので衝突の回避策が必須となる．
衝突対策には以下の 2 通りがある．
同じハッシュ値のデータは複数あり，何個あるか事前にわからないのなら， 連結リストで実現すればいい，という発想で作られているのがチェイン法 である．
ハッシュ表には各ハッシュ値のデータの連結リストの先頭要素への ポインタが格納される．
同じハッシュ値のデータの中で探索，削除を行うには 線形探索の処理時間がかかる．
チェイン法は同じハッシュ値のデータが多いと性能が低下する．
p.113 List8.2 に対応するサンプルプログラムは list08_2.c である．以下のように適当なファイル名でコピーせよ．
jtXXXXXX@sirius:~/c$ cp ../algo/list08_2.c mylist08_2.c
図9.1 サンプルプログラムのコピー
サンプルプログラムには教科書List8.2に欠けている stdlib.h, stdio.h の インクルードと KEY, DATA 型の typedef が冒頭部に加えられている． あとは hash, keyequal 関数と main を作れば動作する． 以下の「List8.2追加部分A」をコピーしたサンプルプログラムの init() 関数の前に挿入し， 「List8.2追加部分B」をサンプルプログラムの 最後に追加してコンパイルせよ．
int hash(KEY key)
{
return key % BUCKET_SIZE;
}
int keyequal(KEY a, KEY b)
{
return a == b;
}
図9.2 List8.2 追加部分A
int main(void)
{
DATA d;
init();
if(find(1000) != NULL){
printf("Found\n");
} else {
printf("Not found\n");
}
printf("Insert\n");
d = 1;
insert(1000, &d);
if(find(1000) != NULL){
printf("Found\n");
} else {
printf("Not found\n");
}
printf("Delete\n");
delete(1000);
if(find(1000) != NULL){
printf("Found\n");
} else {
printf("Not found\n");
}
}
図9.3 List8.2 追加部分B
keyequal 関数の
return a == b;
図9.3 keyequal の一部
の部分は a == b が真であれば 1 を返し，偽であれば 0 を返す， すなわち以下と等価である．
if (a == b){
return 1;
} else {
return 0;
}
図9.4 図9.3 と等価な処理
Python など他の言語では真偽値を表すための専用の型をもつものも あるが C では整数型で真偽値を代用している．if 文などの括弧内に 書かれる条件式には結果が整数値となる式を書くことができ， 値が 0 の時は偽，それ以外の時は真として扱われる．
C では >, <, == などの値の比較を行う関係演算子 の式の結果は真であれば 1, 偽であれば 0 となる．例えば a がint 型の変数であるとすると a = ( 2 > 1 ); という文では a に整数値 1 が代入され，a = ( 2 <= 1 ); では a に 0 が 代入される．
バケットの数（ハッシュ表の項目数）を B，データの総数を N とすると，チェイン法の探索時間は O(1 + N/B) となる． 高速に動作させるにはバケット数 B を十分大きくとる必要がある．
チェイン法がハッシュ表の外の記憶領域を使用するのに対し， オープンアドレス法はハッシュ表の中だけで記憶を完結させる方法である．
衝突があった場合に次の空きバケットを探す アルゴリズムをあらかじめ決めておき，それに従って ハッシュ表内空いている別の場所を探し（再ハッシュ）， データを記録する．
再ハッシュの具体的な方法としては，空きバケットが見つかるまで 1つずつ後のバケットをチェックする，などがある． （ハッシュ表の最後まで到達すると最初に戻る）
オープンアドレス法ではデータを削除したときに， 空の場合と区別できる「削除済み」という状態を 記録する必要がある．
p.122 List8.3 に対応するサンプルプログラムは list08_3.c である．適当なファイル名でコピーせよ．
このサンプルプログラムも 図9.2 List8.2 追加部分 と同じものを補うことで動作可能な状態になる．動作を確認せよ．
サンプルコードではデータがまだ一度も格納されたことがない 空の状態をキーのメンバの値 0 で表し， 削除済みの状態をキーのメンバの値 1 で表している． 通常のキーの値としては 0, 1 は使えない実装であることに注意せよ．
再ハッシュが繰り返される状況だと性能が悪化する． 再ハッシュの手順を単純な方法で実現すると再ハッシュが 繰り返されやすく，ハッシュの塊ができてしまう． 乱数を用いた方法でこれを回避できる． 教科書 p.125 下から 4 行目の数列 (6, 1, 4, 7, 2, 9, 8, 3, 5)は， ハッシュ値に加算することで再ハッシュする添え字の系列を得るためのものである． たとえばハッシュ値が 3 のとき，上の系列に 3 を加算 （法を 10 とする加算であることに注意）し数列 (9, 4, 7, 0, 5, 2, 1, 6, 8)を得る．ハッシュ値が 3 だった時，最初に 探す要素はもちろん 3 番だが，先客がある場合は次に 9 番, 4 番， 7 番， 0 番， … という順番で 空きを探してゆく．ハッシュ値が 1 の時の順番は (7, 2, 5, 8, 3, 0, 9, 4, 6) となり，7 番 の次が 2 番となる．異なるハッシュ値からのスタートで バケットのつながり具合が変わるため，塊の発生を防いでる．
ハッシュ関数はランダムに値を返すようにみえることが 理想である．
大きい 2 つのデータが同一であるかどうか調べるとき， 最初にハッシュ値同士を比較することで，本体を 調べなくても違うことがわかる場合がある． ハッシュ関数は多対一関数であるから数学的には，
であるため，元のデータが異なるという判断しかできない．
しかし，現実的には ハッシュ値が同じであれば元のデータは同じとして運用されることが 多いので注意が必要である． 実用的なハッシュ関数のハッシュ値は100ビット以上であるため，安全なハッシュ関数であれば 異なるデータのハッシュ値が偶然一致する確率は1京の1京倍分の1以下である． これを実用的に「ありえない」と考えて，ハッシュ値が一致したときは元データも 同じとして利用されることが多いので注意を要する．
メモリ使用量について，チェイン法は「基本料金＋従量制」， オープンアドレス法は「完全固定制料金」
いずれもハッシュ表を大きくとることが高速に動作させるために 重要だが，実メモリよりも大きく使用するとページングが多発する 問題を起こす可能性があるので注意を要する．
第 9 回課題「キーの表示」 を提出せよ．