MIT Open course: Introduction to Algorithmsのまとめ(7〜8回)
Hashing
nレコードを持つテーブルSに対して、
以下の操作を行う。(データxまたはキーk)
・insert(S,x)
・delete(S,x)
・search(S,k)
Sを表すデータ構造をTとする。
第七回
◯Direct Access Table
・キーをそのままメモリに対応させる
- ex)T[0]=1, T[2＾15]=20,...
→キーが大きい場合には、大量のメモリを必要とする(大抵は空)
・search time = Θ(1)
◯Hashing
・ハッシュ関数fは、キーをランダムにTのスロットに対応させる。
・既に埋まっているスロットにinsertしようとすると衝突(collision)が起きてしまう。
→①resolving by chaining(スロットをリスト構造にする)
→②resolving by open addressing(ハッシュ関数を工夫し、空きが見つかるようにする)
①resolving by chaining
・特徴
- スロットをlinkedlistの構造にする
- ex)h(49)=h(56)=h(52)=i スロットiから連結が始まる
・分析
- worst case Θ(n)
- average case Θ(1+α)
→search time = Θ(1) if n=O(m)
(load factor α=n/m,仮定：キーからスロットへのマッピングはランダムで独立)
・ハッシュ関数の決定
条件a)キーからスロットへのマッピング一様
条件b)マッピングがキーの分布によらない(キーが偶数ばかりだと特定のスロットに偏るとか×)
- Division method
h(k)=k mod m
mは小さいよく割る数ではだめ、mの例：2＾r
簡単だが、計算量は多い
- Multiplication method
h(k)=(A・k) mod 2^w) rsh(right shift) w-r (Aは2^(w-1)
- ハッシュ関数を使い回して(probe)、空きが見つかるようにする h:キー×番号→スロット
- n
- deleteが困難
- ex)h(496,0)→filled×、h(496,1)→filled×、h(496,2)→empty◯
・ハッシュ関数使い回し例
- linear h(k,i)=(h(k,0)+i) mod m→埋まったスロットを繰り返し調べるので無駄
- double hashing h(k,i)=(h_1(k)+i*h_2(k)) mod m→素晴らしい、普通はm=2^r,h_2(k)は奇数
・分析
- E[#probes]<=1/(1-α) if α<1
(仮定：どのキーもprobe列に対して同等に各スロットにマッピングされる）
- 証明略
第八回
ハッシュ関数の弱点
・worst case(キーのセットによって）では同じスロットに多々マッピングされてしまう
→randomnessで解決!ランダムにハッシュ関数を選択!
◯Universal hashing ハッシュ関数集合Hによるキー集合Uからスロットへのマッピング
・"H is universal":全ての、異なるキーのペアx,yに対して、
(h(x)=h(y)が成立するハッシュ関数の数)=(ハッシュ関数の数/スロット数)
→二つの異なるキーに対して、キー集合によらずcollisionが起きる確率が1/mとなるような、ハッシュ関数集合Hに対する制約
・"H is universal"であれば、ハッシュ関数hをHからランダムに選ぶことで、キーの分布によらずE[#collisions]<αとなる。
・universalなHの例)h_a(k)=(Σ_(i=0)^(r)a_i*k_i mod m
(mは奇数、k=
◯perfect hashing
・特徴
- worst caseでもtime = O(1)
- 二段階のハッシュテーブルで二段階目は衝突なし
(一段階目のスロットiへのハッシュ数がn_iの場合、二段階目のハッシュテーブルの数m_i=n_i^2とする)
- ex)1段階目h(14)=h(27)=1→value=31, 二段階目h_31(14)=1,h_31(27)=2
・二段階目の分析
- P(#collisions>=1)<1/2→衝突起きない(証明略)
・ストレージの分析
- E[total strage]=Θ(n)
今回はやたら長くなってしまった。。
というか、アルゴリズムの部分が適当すぎだったのかな。。今度時間があるときに書きなおそう。
ハッシュのところをしっかり勉強できたのは大きな収穫。
