開放定址法中常用的方法

『壹』 線性探測再散列法是什麼

當di值可能為1,2,3,...m-1，稱線性探測再散列。

具體如下:

開放地址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）。

其中，m為哈希表的表長。di是產生沖突的時候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測再散列。

如果di取1，則每次沖突之後，向後移動1個位置。如果di取值可能為1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2），稱二次探測再散列，如果di取值可能為偽隨機數列。稱偽隨機探測再散列。

處理沖突的方法：

開放定址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)為散列函數，m為散列表長，di為增量序列，可有下列三種取法：

1、di=1,2,3,…, m-1，稱線性探測再散列；

2、di=1^2, -1^2, 2^2,-2^2, 3^2, …, ±(k)^2,(k<=m/2)稱二次探測再散列。

3、di=偽隨機數序列，稱偽隨機探測再散列。

再散列法：Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函數，即在同義詞產生地址沖突時計算另一個散列函數地址，直到沖突不再發生，這種方法不易產生「聚集」，但增加了計算時間。

鏈地址法（拉鏈法）：將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中。

用二次探測再散列法解決沖突：

1、(key+1^2)%11=(49+1)%11=6,仍然發生沖突。

2、(key-1^2)%11=(49-1)%11=4,仍然發生沖突。

3、(key+2^2)%11=(49+4)%11=9,不再發生沖突。

以上內容參考網路-哈希表