ハッシュテーブル(ハッシュ表)
・ キーとそれに対応する 値の集合を、インデックス(索引)で管理する データ構造
・データ操作
　・検索、追加、更新、削除
・データ操作は、データの 格納場所によらず一定時間[ O(1)]で可能
・ キーに対して何らかの 演算を行う
　→演算結果がキーに対するインデックス(索引)の値になればよい
　「 ハッシュ関数」
　　 ハッシュ値…通常、非負整数(≧0)

ハッシュ法
・ハッシュ関数により得られたハッシュ値によって、ハッシュテーブルを参照する アルゴリズム

ところで…
・ハッシュと聞いて、何をイメージしますか？
　・ハッシュドポテト、ハッシュドビーフ、…
　・食べ物以外にも、TwitterXのハッシュタグ
・そもそもハッシュとは
　・細かく切り刻む、粉々にする、細切れにする、または、その断片
・情報科学でいうハッシュ
　・元データを 要約したものを表す数値や文字列を指す用語
　　・元データが細切れにされ「断片」になっている、というイメージに由来
　・ハッシュの持つ情報量は、元のデータより 少ない
　　・ハッシュ値から元データを復元することは 不可能=ハッシュの 不可逆性

ハッシュ関数
・キーからハッシュ値を求める関数
・ハッシュ関数に求められる性質
　・ハッシュ値はハッシュテーブルの 範囲内→テーブルからはみ出したらダメ
　・任意のキーに対するハッシュ値の分布が 一様になる
　　・これは理想…実は難しい
　　・現実には、異なるキーに対するハッシュ値が同じになること[ハッシュ値の 衝突( コリジョン)]は避けられない

衝突(コリジョン)対策
・発生する頻度を少なくする
　・ハッシュテーブルのサイズをできるだけ 大きくする
　　・サイズが大きいほど、ハッシュ値のとれる範囲は拡大→衝突の確率は下がる
　・テーブルを 素数サイズにする
　　・通常ハッシュ関数は、ハッシュ値を求めるのにテーブルサイズで割った 余りを使う
　　　…ハッシュ値がテーブルからはみ出さないようにするため
　　・素数で割った余りは散らばりやすい
・発生したらどうするか
　・ハッシュ値を一定の規則で求め直す(再ハッシュ)　… オープンアドレス法
　・同一ハッシュ値のデータを同じエントリに格納する… チェイン法　　　　
　　・同じハッシュ値を持つデータ= シノニム

オープンアドレス法

・削除の場合はちょっと注意
　削除の際は、削除済みを表す印をつけておく

オープンアドレス法の性能
・1回の探索に要する平均比較回数(理想的なハッシュ関数を想定)
　・再ハッシュ　hash(key, i) = (hash(key, 1) + (i - 1)) % T
　・探索成功　　(1 - a / 2) / (1 - a)
　・探索失敗　　1 / 2 + 1 / (2(1 - a)^2)
　　aはハッシュテーブルの使用率
　　テーブルサイズ:T, 格納データ総数:n
　　a = n / T ( n≦T)

チェイン法

　同じハッシュ値を持つデータ(シノニム)を、 線形リストでつなぐ

チェイン法の性能
・探索の計算量(理想的なハッシュ関数を想定)
　・ハッシュ値の計算…O(1)
　・シノニムが存在するとき…リストの探索が必要
　　・テーブルの各エントリにおける、 平均リスト長( シノニムの個数)が分かればよい
　　　テーブルサイズ:T, 格納データ総数:n　平均何個？ n/T個
　　・シノニムの探索に要する計算量…O(n/T)
　・全体の計算量…O(1+n/T)
　　・テーブルサイズよりデータ数がずっと少ないとき(n << T)
　　　　n/T ≈ 0(ゼロ)なので、O(1+n/T)=O(1+0)= O(1)
　　・テーブルサイズよりデータ数がずっと多いとき　(n >> T)
　　　　n/T ≈ nなので、O(1+n/T)=O(1+n)= O(n)

オープンアドレス法とチェイン法の比較
・オープンアドレス法
　・実装は容易
　・実用できるのは、データ数がテーブルサイズの80~90%程度まで
　　・データ数1000、使用率85%とすると、テーブルサイズは1200程度必要
　　・単純な再ハッシュはデータの塊を作りやすい
・チェイン法 … この授業で実装します
　・実装は若干複雑
　・実用できるのは、データ数がテーブルサイズの数倍程度まで
　　・データ数が1000なら、テーブルサイズは400~500程度でよい
　　・データ数が増えるとシノニムのリストが長くなる

チェイン法での実装(データ構造の定義)

typedef struct hash_element { //ハッシュテーブルに格納される一要素
  char *key;                       //キー
  char *value;                     //キーに対応する値
  struct has_element *next;        //次の要素(シノニム)へのポインタ
} HashElement;

typedef struct {                   //ハッシュテーブルはこのデータ型の配列
  int count;                       //このエントリを共有するシノニムの数
  HashElement *element;            //格納する要素(キーと値)へのポインタ
} HashEntry;

HashEntry tbl[TBL_SIZE];           //TBL_SIZEはハッシュテーブルの大きさ

まとめ
・ハッシュテーブルの特徴
　・原理的には、O(1)の検索が可能
　　・現実には、 ハッシュ関数の作り方と、 テーブルサイズに大きく依存する
　・データに 順序がつけられない
　　・順序づけが必要な場合、別途ソートが必要
　　　・順序づけを優先したいなら、AVL木や赤黒木などの平衡二分探索木を利用
　・データ格納後のテーブルサイズ変更は 難しい
　　・ 全データの再ハッシュが必要
・使用場面
　・ 偏りのないハッシュ関数が用意でき、十分な メモリが使える環境での検索
　　・連想配列、コンパイラやインタプリタでの予約語, 変数名, 関数名等の管理