Hash function

一個好的雜湊函數，可以把均勻的分佈在雜湊表的每一個slot中，也就是盡量滿足簡單均勻雜湊的假設，而且分布的均勻性，不會受到元素的影響，也就是說，一個好的雜湊函數，我們希望它所產生的雜湊值，可以獨立於輸入的元素。

Division method(除法雜湊法)

在雜湊函數中，除法雜湊法是很常見的雜湊函數，令為，雜湊表有個槽，我們通過取對的餘數，將映射到的其中一個槽中，可以用以下的式子表示這個雜湊函數

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

1. 雜湊表可用的槽需要夠多，假設，則產生出的雜湊表分布的將不夠平均，只有兩條鏈結串列，導致效率低落。
2. 如果我們給定的和都恰好為偶數，那麼我們只能使用一半的槽，不僅浪費許多空間，且違反的我們對於雜湊函數的期望，也就是分布的均勻性不受到輸入元素的影響。
3. 如果我們給定，則就是的個最低位數字，而這樣的情況下，除非個最低位數字他們是均勻分布的，也是以二進位觀點，0和1都是均等出現的，那麼才能保證雜湊表有較好的效率，否則一般設計時，我們都會優先考慮到元素的所有位數。

0010101011001, m=2^6，那麼我們會使用到的數字為

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

一般情況下，我們在取的時候，會選擇一個不接近2的整數幕的質數，而這樣取的情況下，往往會產生出比較好的結果。像是

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

Multiplication method(乘法雜湊法)

在實際處理資料時，我們常常無法事先得知的範圍，或是具有的特性，像是全部都是偶數之類的，這時候，乘法雜湊表就是一個不錯的方法可以使用。

假設，表示hash table的槽數，且在一部電腦中，每一個bytes含有 bits，則雜湊函數為

表示向右偏移(right shift)的意思，就是二進制的偏移, A是一個奇數，範圍介於, 表示。

這個方法的關鍵在於的選取，在選取時我們必須避免選取一些特定的數值，像是選擇時要盡量避免以2為底的數字，像是2,4,8,16等數字。

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

• Example 1. 假設我們有一個hash table，有8個槽，，

這個雜湊函數的關鍵就在於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取小數部分大約為

當k = 2時，A*k取小數部分大概是

而乘法雜湊法就是運用這樣的想法，讓平均的分布在hash table中每一個槽裡。而這也就是為什麼這是一個不錯的雜湊方法，既可以保證計算的速度，又可以保證分布的平均性。

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

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

前面提到說，這個方法的好壞取決於我們如何選取，對於某一些值，這個方法的效果特別的好，根據Knuth認為，如果趨近於黃金比例常數的共軛根

產生出的結果會較為理想。

參考資料:Introduction to algorithms 3rd