在雜湊法中，當識別字要放入某bucket時，若該bucket已滿，則發生溢位(overflow)情況，那當雜湊法的理想狀況是所有的資料經過雜湊函數後都得到不同的值，但現實情況是即使所有的關鍵欄位的值都不相同，還是可能得到相同的位址，這就發生了碰撞(collision)。因此在碰撞後處理溢位的問題就是相當的重要，介紹常見的處理方法。

線性探測法

線性探測法是發生碰撞時，若該索引已有資料，則以線性的方式往後尋找空的儲存位置，一找到位置就把資料放進去。線性探測法通常把雜湊的位置視為環狀結構，這樣後面的位置已被填滿而前面還有位置時，可以將資料放到前面。

平方探測法

主要是用平方探測法改善Clustering Problem，在平方探測中，當溢位時，下一次搜尋的位址是(f(x)+i^2)%B和(f(x)-i^2)%B，即讓資料值加或減i的平方。

例如:資料值key，雜湊函數f

第一次:f(key)
第二次:f(f(key)+1^2)%B
第三次:f(f(key)-1^2)%B
第四次:f(f(key)+2^2)%B
第五次:f(f(key)-2^2)%B
.
.
.
第n次:f(f(key)+-((B-1)/2)^2)%B，其中B必須為4j+3的質數，且1<=i<=(B-1)/2

再雜湊法

再雜湊法是一開始先設置一系列的雜湊函數，當使用第一種雜湊函數出現溢位時就改用第二種，如果第二種也溢位則改用第三種，直到沒有溢位為止。

例如:h1為key%8,h2為key * key,h3為key * key%8....。

利用雜湊處理碰撞的問題:

[681,467,633,511,100,164,472,438,445,366,118]

其中雜湊函數為(此處的m=13)

h0(x) = (h(x) + 0 * h'(x))modM
h1(x) = (h(x) + 1 * h'(x))modM
h2(x) = (h(x) + 2 * h'(x))modM
h3(x) = (h(x) + 3 * h'(x))modM

1.利用第一種雜湊函數h，所得的雜湊位址如

681 -> 5
467 -> 12
633 -> 9
511 -> 4
100 -> 9
164 -> 8
472 -> 4
438 -> 9
445 -> 3
366 -> 2
118 -> 1

2.其中100,472,438發生碰撞，再利用第二種雜湊函數進行資料的位址安排

100 -> h(100 + 2) = 102 mod 13=11
472 -> h(472 + 2) = 474 mod 13=6
438 -> h(438 + 2) = 440 mod 13=11

3.439仍發生碰撞問題，接著利用第三種雜湊函數重新進行438位址安排

經過三次安排後，資料的位址安排如

使用這些方法時要先知道你的資料的需求，有這些條件再用方法來處理，最被常用來加密存放資料庫中的密碼字串，由於雜湊演算法所計算出來的雜湊值具有不可逆的性質，因此可有效地保護密碼。

目前應該不會太難吧🐮🐮！！

要是哪裡理解上還是邏輯上有錯請各位大大指正，感謝 🧙🧙🧙。

資料來源 :
https://zh.wikipedia.org/zh-tw/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8