「アルゴリズム」 「アルゴリズム」
ハッシュテーブル
解説
ハッシュテーブル(hash table)とは、データの挿入と探索が非常に高速にできるデータ構造である。
キーそのものをハッシュ関数という関数によって数値化して、その数値の示す位置にデータを格納する。すなわち、データ自身からデータの保存場所を計算できるため、非常に高速な検索が可能となる。
ハッシュ関数
望ましいハッシュ関数とは、以下のような性質を持つものである
ランダムキー
H(Key) = Key ％ m
計算が容易で、キーがランダムに分布しているなら、ハッシュ関数値も均等に分布する。
衝突の処理
ハッシュ関数 H(Key) により、すべてのデータがユニークな値に割り当てられれば、最も効率よく検索を行うことができるが、現実的には不可能である。実際には、ハッシュ関数値に対応するデータが複数個存在する。これを衝突(collision)という。
ｎ個のデータを長さｍの配列にハッシュするとき、各配列にチェーンされるデータの個数の平均は理想的には(n/m)である。ハッシュ関数の計算に要する時間をｃとすると、1つのデータを検索するのに要する時間は
T(n) = c + n/m
となる。したがって、mを十分大きく取ることができれば、一定時間（≒ｃ）で検索が可能となる。すなわち O（1）。
データ数ｎより多めのテーブルを用意し、ハッシングにより、最初のアドレスをテーブル内に均等にばらまき、衝突が起きたらテーブルの空いている場所を探して割り付ける方法である。空き場所の探し方にはいくつかの方法がある。
- 線形探査（linear probe）法
配列を順番に辿って、前方に空いている場所を探す方法- 平方探査（quodratic probe)法
最初の位置を基に、ｉ 回目には i2離れたところを探す方法- ２重ハッシュ(double hash)法
別のハッシュ関数を用いて、得られた結果分だけ前を探す方法
１次ハッシュH1に対するkey1,key2のハッシュ値が同じ場合、２次ハッシュH２を用いて、C1=H２(key1), C2=H２(key2) 分だけ前に進める
線形探査法 平方探査法 2重ハッシュ法
演習課題
基本１：「サンプルプログラムの実行」
解説中の各ハッシュアルゴリズムについて、サンプルアプレットを実行し、動作を確認しよう。
基本２：「計算量の評価」
H(Key) = Key ％ 100 なるハッシュ関数により、100万個のデータが、チェーン法で記録されているとする。
同じハッシュ値を持つデータについては、線形検索を用いるものとする。データが均等に分類される場合の計算時間を求めよ。但し、ハッシュ関数の計算に要する時間をＣ、ｎ個のデータを線形検索する時間をＴ（ｎ）＝ｃｎとする。
ハッシュを用いずに線形検索をする場合より、約何倍効率が良くなるか考察せよ。
応用：「英単語を対象とするハッシュ法」
Linuxの単語データファイルを対象として、ハッシュ法による探索プログラムを作成せよ。
また、ハッシュ関数として以下のものを作成し、効率を比較せよ。
講義目次