ハッシュ法

5.4 ハッシュ法
ハッシュとは
• ハッシュ法
– ハッシュ関数 h：データ → 格納場所（添え字）
– ハッシュ表配列 t[0..m-1]
• 格納場所（添え字）を計算で求める
関数 h
0
1
…
配列 t
衝突
i
…
m-1
ハッシュ関数の原則
• キーのすべての情報を利用することが基本
• 一部の情報だけでハッシュ値を決めることは
避ける
ナイーブなハッシュ関数の例
 | s|

 s  s1s2 s s 
 ord si  mod m  ord : 文字  整数

 i 1

h yamada   何の情報が欠けて
ord ( y )  ord (a )    ord (a )
 いるのか？
25  1  14  1  4  1  46
humeda   ord (u )  ord (m)    ord (a )

21  14  5  4  1  45
h yoda   ord ( y )  ord (o)    ord (a )

25  15  4  1  45
梅田と与田が衝突
ナイーブなハッシュ関数の例
 s  s1s2 s s 

 | s|
 ord si  mod m  

 i 1
ord : 文字  整数
 ord (n)  ord (a)    ord (a)
hnakataどう変更すれば
よいか？
13  1  11  1  20  1  47

htanaka  ord (t )  ord (a)    ord (a)
20  1  13  1  11  1  47

順番の情報が活きていない
ハッシュ関数の例
• 例えば以下の型を使う
 | s| i

 b  ord si  mod m 
 i 1

b  10, m  107
h yamada  
ord ( y )  ord (a )    ord (a )
(101  25)  (10 2 1)  (103 14)  
  4
 mod 107 
5
6
(10 1)  (10  4)  (10 1)


62
同じ誕生日の確率
• 何人いたら，その中に少なくとも2人が同じ誕生日を
持つ確率が50％以上になるか?
• 全員異なる確率：
1 × (364/365) × (363/365 ) × ( 362/365 ) × ...
× ((365-k+1)/365)
• k=23のとき、全員異なる誕生日である確率は0.4927
• 365個の記憶場所のうちの10％も使われないうちに、
少なくとも1回の衝突が起こる確率は1/2を以上
衝突に対する処理
配列 t
関数 h
0
1
2
…
衝突
• 良いハッシュ → 均等に格納される
m-1
ハッシュ関数の例
• 例えば以下の型を使う
 | s| i

 b  ord si  mod m 
 i 1

b  10, m  107
h yamada  
ord ( y )  ord (a )    ord (a )
(101  25)  (10 2 1)  (103 14)  
  4
 mod 107 
5
6
(10 1)  (10  4)  (10 1)


62
ｂとｍの取り方の注意点
 | s| i

・　 b  ord si  mod m 
 i 1

・ b  m  1とすると何の情報が失われることになるか？
・ m  2 kとすると何の情報が失われることになるか？
ｂとｍの取り方の注意点
 | s| i

・　 b  ord si mod m 
 i 1

・ b  m  1とすると文字の位置情報が失われる
∵ b i mod m  1より
・ m  2 kとすると下桁しかみて
いないことになる
以下部品
ｂとｍの取り方の注意点
 | s| i

・　 b  ord si  mod m 
 i 1

・ b  m  1とすると文字の位置情報が失われる
r n 1
∵ 等比級数の和の公式  r 
から r n  1は r  1で割切れる
r 1
i 0
n -1
i
i文字目と j文字目(i  j )が入替わった文字列 xと yを考える
x y

( xi  yi )b i 1  ( x j  y j )b j 1

b i 1 xi (b j i  1)  b i 1 yi (b j i  1)
 上式はで b  1, つまり mで割切れる
ということは
xと yは mod m　で同じ
・ m  2 kとすると下桁しかみて
いないことになる

Download Report