1 開放定址法

1.1 定義

開放定址法就是一旦發生了沖突，就去尋找下一個空的散列地址

1.2 要求

只要散列表足夠大

空的散列地址總能找到，并將記錄存入

1.3 線性探測法

使用該公式用于解決沖突的開放定址法稱為線性探測法

對于線性探測法，在出現沖突時，它只能晚后一步一步檢測看是否有空位置

假設此時該沖突位置后續沒有可用位置，但前面有一個空位置

盡管可以不斷地求余數后得到結果，但效率很差

1.4 二次探測法

因此可以改進該算法，增加雙向尋找可能的空位置，這種新算法稱為二次探測法：

1.5 隨機探測法

此外還有一種方法是，在沖突時，對于位移量di采用隨機函數計算得到，我們稱為隨機探測法：

注意：

這里的隨機其實是偽隨機數

即設置相同的隨機種子，則不斷調用隨機函數的過程中就可以生成不會重復的數列

同時，在查找時，用同樣的隨機種子，它每次得到的數列也是相同的

因此相同的di就可以得到相同的散列地址

2 再散列函數法

2.1 散列函數

即提供多個散列函數：

2.2 解釋

這里的RHi就是不同的散列函數然后每當發生散列地址沖突時

就換一個散列函數計算

相信總會有一個可以把沖突解決掉（todo:: how to search??）

2.3 優點弊端

2.3.1 優點

這種方法能夠使得關鍵字不產生聚集

2.3.2 弊端

當然，相應地也增加了計算的時間

3 鏈地址法

3.1 定義

將所有關鍵字為同義詞（即哈希地址相同）的記錄存儲在一個單鏈表中,我們稱這種表為同義詞子表

在散列表中只存儲所有同義詞子表的頭指針

3.2 優點弊端

3.2.1 優點

鏈地址法對于可能會造成很多沖突的散列函數來說

提供了絕不會出現找不到地址的保障

3.2.2 弊端

當然，這也就帶來了查找時需要遍歷單鏈表的性能損耗

4 公共溢出區法

即為所有沖突的關鍵字建立一個公共的溢出區來存放

在查找時，對給定值通過散列函數計算出散列地址后先與基本表的相應位置進行比對如果相等，則查找成功如果不相等，則到溢出表去進行順序查找如果對于基本表而言，有沖突的數據很少的情況下

公共溢出區的結構對查找性能來說還是非常高的