ハッシュテーブルとオープンアドレス法
ハッシュテーブルは、データの数に関係なく定数計算量で探索・挿入・削除を行えるデータ構造
データに関連する「キー」という値を、データが格納される配列の添字に用いる
ハッシュ関数
キーの値を配列の添字に変換する関数
ハッシュ関数の返り値をハッシュ値という
バケット (bucket)
ハッシュテーブルの要素
ハッシュ関数の例
除算法 (division method):単純に一定の除数に対する余りをハッシュ値とする
$ h(x) = x\bmod m
中央積算法 (mid-square method):キーとなる数値自身を2乗して、中央付近の位の数字を選択してハッシュ値とする
例) キーが $ 383 の場合、$ 383^2 = 146{,}689 の千/百/十の位を取り出し、ハッシュ値は $ 668となる
折り畳み法 (folding method)
キーとなる数値を複数の部分に分ける (分割する各数値の桁数は、求めたいハッシュ値の桁数と一致させる)
分割された数値の総和から、求めたいハッシュ値の桁数分だけ数値を選択してハッシュ値とする
例) キーが $ 19{,}701{,}219 で2桁のハッシュ値を求めたい場合、2桁ずつ分割して $ 19, 70, 12, 19 となり、総和 $ 19 + 70 + 12 + 19 = 120 から2桁だけ取り出してハッシュ値 $ 20 が得られる
ハッシュ値の衝突
異なるキーに対して、同じ添字が対応づけられてしまった状態
衝突を解決する方法 (collision resolution)
オープンアドレス法 (open addressing)
同じハッシュ値のバケットが登録済みの場合、ハッシュテーブル内の空いている場所を探索してデータを登録する
再ハッシュ (rehashing):別のバケットを探すためのハッシング操作
線形探査 (linear probing)
ハッシュ関数 $ h(x, i) = (h(x) + i) \bmod m ( $ i は再ハッシュの回数)
隣接する空きバケットに登録する
埋まったバケットが連続するプライマリ・クラスタが発生し、探索のパフォーマンスが低下する
平方探査 (quadratic probing)
クラスタの発生を避けるために、離れた場所の空きバケットを探す
ハッシュ関数 $ h(x, i) = (h(x) + c_0i + c_1i^2) \bmod m ( $ i は再ハッシュの回数、$ c_0 と $ c_1 は任意の定数)
再ハッシュのたびに、より遠く離れた場所の添字を算出する
それでも、同じハッシュ値を持つキーが同じ間隔のバケットを探査して空きバケットを見つけようとするセカンダリ・クラスタが発生する
ダブルハッシング (double hashing)
プライマリ/セカンダリ・クラスタの発生を防ぐ方法
毎回間隔の開け方が同じ平方探査とは異なり、キーによって探査の間隔を変化させる
2つのハッシュ関数を用いる (副ハッシュ関数 $ h_1(x), h_2(x) )
ハッシュ関数 $ h(x, i) = (h_1(x) + i \times h_2(x)) \bmod m
$ h_2(x) には制限がある
$ h_1(x) と同じ関数であってはならない
0 を返しうる関数であってはならない
すべてのバケットを探索できるようにしなくてはならない
連鎖法 (chaining)
同じハッシュ値が得られた場合にはハッシュテーブルにデータを連結リストによって追加していく