iT邦幫忙

2021 iThome 鐵人賽

DAY 25
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 25

Day-25 Hash Function(雜湊函數), 乘法雜湊法, 除法雜湊法

Hash function

一個好的雜湊函數,可以把https://chart.googleapis.com/chart?cht=tx&chl=key均勻的分佈在雜湊表的每一個slot中,也就是盡量滿足簡單均勻雜湊的假設,而且https://chart.googleapis.com/chart?cht=tx&chl=key分布的均勻性,不會受到元素的影響,也就是說,一個好的雜湊函數,我們希望它所產生的雜湊值,可以獨立於輸入的元素。

Division method(除法雜湊法)

在雜湊函數中,除法雜湊法是很常見的雜湊函數,令https://chart.googleapis.com/chart?cht=tx&chl=keyhttps://chart.googleapis.com/chart?cht=tx&chl=k,雜湊表https://chart.googleapis.com/chart?cht=tx&chl=Thttps://chart.googleapis.com/chart?cht=tx&chl=m個槽,我們通過取https://chart.googleapis.com/chart?cht=tx&chl=khttps://chart.googleapis.com/chart?cht=tx&chl=m的餘數,將https://chart.googleapis.com/chart?cht=tx&chl=k映射到https://chart.googleapis.com/chart?cht=tx&chl=T的其中一個槽中,可以用以下的式子表示這個雜湊函數

https://chart.googleapis.com/chart?cht=tx&chl=h(k)%20%3D%20k%5C%20mod%5C%20m

使用這個雜湊函數時,我們需要避免一些情況的發生。

  1. 雜湊表可用的槽需要夠多,假設https://chart.googleapis.com/chart?cht=tx&chl=m%3D2,則產生出的雜湊表分布的將不夠平均,只有兩條鏈結串列,導致效率低落。
  2. 如果我們給定的https://chart.googleapis.com/chart?cht=tx&chl=keyhttps://chart.googleapis.com/chart?cht=tx&chl=m都恰好為偶數,那麼我們只能使用https://chart.googleapis.com/chart?cht=tx&chl=T一半的槽,不僅浪費許多空間,且違反的我們對於雜湊函數的期望,也就是https://chart.googleapis.com/chart?cht=tx&chl=key分布的均勻性不受到輸入元素的影響。
  3. 如果我們給定https://chart.googleapis.com/chart?cht=tx&chl=m%3D2%5Ep,則https://chart.googleapis.com/chart?cht=tx&chl=h(k)就是https://chart.googleapis.com/chart?cht=tx&chl=khttps://chart.googleapis.com/chart?cht=tx&chl=p個最低位數字,而這樣的情況下,除非https://chart.googleapis.com/chart?cht=tx&chl=p個最低位數字他們是均勻分布的,也是以二進位觀點,0和1都是均等出現的,那麼才能保證雜湊表有較好的效率,否則一般設計時,我們都會優先考慮到元素的所有位數。
0010101011001, m=2^6,那麼我們會使用到的數字為

011001=h(k),而在二進位中,1和0的出現通常都具有一定的規律性,這會導致我們產生出的雜湊情況不夠均勻

一般情況下,我們在取https://chart.googleapis.com/chart?cht=tx&chl=m的時候,會選擇一個不接近2的整數幕的質數,而這樣取https://chart.googleapis.com/chart?cht=tx&chl=m的情況下,往往會產生出比較好的結果。像是https://chart.googleapis.com/chart?cht=tx&chl=m%3D701

除法雜湊法很常在程式中見到,因為他的程式碼量不多,且效果不會太差,但相較於其他基於加法和乘法的雜湊函數,除法在電腦中需要花費更多的計算步驟,造成更多時間的消耗。

Multiplication method(乘法雜湊法)

在實際處理資料時,我們常常無法事先得知https://chart.googleapis.com/chart?cht=tx&chl=key的範圍,或是https://chart.googleapis.com/chart?cht=tx&chl=key具有的特性,像是全部都是偶數之類的,這時候,乘法雜湊表就是一個不錯的方法可以使用。

假設https://chart.googleapis.com/chart?cht=tx&chl=m%3D2%5Erhttps://chart.googleapis.com/chart?cht=tx&chl=m表示hash table的槽數,且在一部電腦中,每一個bytes含有https://chart.googleapis.com/chart?cht=tx&chl=w bits,則雜湊函數為

https://chart.googleapis.com/chart?cht=tx&chl=h(k)%3D(A*k%5C%20mod%5C%202%5Ew)%20%3E%3E%20(w-r)

https://chart.googleapis.com/chart?cht=tx&chl=%3E%3E表示向右偏移(right shift)的意思,就是二進制的偏移, A是一個奇數,範圍介於https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7Bw-1%7D%3CA%3C2%5Ew, https://chart.googleapis.com/chart?cht=tx&chl=k表示https://chart.googleapis.com/chart?cht=tx&chl=key

這個方法的關鍵在於https://chart.googleapis.com/chart?cht=tx&chl=A的選取,在選取https://chart.googleapis.com/chart?cht=tx&chl=A時我們必須避免選取一些特定的數值,像是選擇https://chart.googleapis.com/chart?cht=tx&chl=A時要盡量避免以2為底的數字,像是2,4,8,16等數字。

基本上這個方法是一個相當快速的方法,相乘後再取餘數會比起直接除法要來的更快,且二進制的偏移運算本身就十分快速,尤其是在我們進行雜湊運算之前。我們就已經得知需要偏移的位元數的情況下,又來的更加的快速。

  • Example 1. 假設我們有一個hash table,有8個槽,https://chart.googleapis.com/chart?cht=tx&chl=m%3D8%3D2%5E3https://chart.googleapis.com/chart?cht=tx&chl=w%3D7
這個雜湊函數的關鍵就在於A的選取,假設A = 1011001(Bin) = 89(dec),2^w-1 = 64, 2^w = 128。
然後選取一個key來乘上A,k = 1101011,接著計算A * k

        1011001 = A
*       1101011 = k
 __________________
 10010100110011
 
 得到A和k的乘積後,接著對2^7取餘數,也就是取出前7位數字
 
 1001010__(0110011), 接著向右偏移(w-r)位,也就是(7-3) 
 
 0110011 >> (7-3) = 0000011,也就是取出最高位的前3位數字,而這個值就是h(k)了

而為什麼乘法雜湊法是一個很不錯的演算法,我們引用下面圖形進行說明,在說明之前,我們先進行一些假設

       1011001 = A
*      1101011 = k
 __________________
 10010100110011
 
 假設A是一個小於1的數,則我們可以在A的最高位天加上一個小數點,如下面所示
 
       .1011001 = A
 *      1101011 = k
___________________
1001010.0110011

而取餘數的計算就是忽略掉整數部分,保留小數部分,以這個例子來說,A的小數部分以10進制來說大約是5.5左右。
而假設k = 1,2,3,4,5....
 

有了上面的假設,我們可以以一個環來表示一個規律

當k = 1時,A*k取小數部分大約為https://chart.googleapis.com/chart?cht=tx&chl=5.5%2F8

當k = 2時,A*k取小數部分大概是https://chart.googleapis.com/chart?cht=tx&chl=3%2F8

而乘法雜湊法就是運用這樣的想法,讓https://chart.googleapis.com/chart?cht=tx&chl=key平均的分布在hash table中每一個槽裡。而這也就是為什麼這是一個不錯的雜湊方法,既可以保證計算的速度,又可以保證https://chart.googleapis.com/chart?cht=tx&chl=key分布的平均性。

而先前提到的除法雜湊法,與乘法湊法對比在處理二進為資料時,由於取餘數的部分還多出了hash table的槽位,和一個bytes的位元數等因子參與,因此增加了隨機性,從而使乘法雜湊法成為了更好的策略可以使用。

而上面的範例是以7 bit進行示範,如果我們以64 bit表示,然後增加key的範圍,那麼我們可以使最後產生出的雜湊值結果更加的隨機,也就是對應到更多的槽位,使得碰撞的機率下降。

前面提到說,這個方法的好壞取決於我們如何選取https://chart.googleapis.com/chart?cht=tx&chl=A,對於某一些https://chart.googleapis.com/chart?cht=tx&chl=A值,這個方法的效果特別的好,根據Knuth認為,如果https://chart.googleapis.com/chart?cht=tx&chl=A趨近於黃金比例常數的共軛根
https://chart.googleapis.com/chart?cht=tx&chl=A%20%5Capprox%20(%5Csqrt%205%20-%201)%20%2F%202%20%3D%200.618....
產生出的結果會較為理想。

參考資料:Introduction to algorithms 3rd


上一篇
Day-24 Hash Table(雜湊表)
下一篇
Day-26 Hash Table-開放定址(Open Addressing)
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言