開放地址法

開放地址法是一個計算機術語。

基本介紹

• 中文名：開放地址法
• 實質：衝突處理方法
• 包括：線性探測再散列
• 注意：不能簡單地直接刪除

簡介

1.衝突處理方法一---開放地址法

當發生地址衝突後，求解下一個地址用：

ND =( D+di）%m　 i=1,2,…,k(k<= m-1)

不同取法

其中: m為哈希表長度,di為增量序列。增量序列的不同取法，又構成不同的開放地址法。

(1)線性探測再散列

D = H(key);

ND = (D+di)%m;　di取1,2,3,……,m-1

線性探測再散列處理衝突的基本思想:若數據元素在存儲地址D發生衝突，則放到存儲地址（D+1）%m；若又發生衝突則放到存儲地址（D+2）%m；若再發生衝突則放到存儲地址（D+3）%m；……；直到碰到第一個為空的存儲地址（D+i）%m，則將數據元素存放在該存儲空間。

(2)二次探測再散列

D = H(key);

ND = (D+di)%m;　di取1*1,-1*1,2*2,-2*2,……,K*K,-K*K 　(K≤m/2)

(3)雙散列法

首先使用第一個散列函式H1(key)及逆行那個散列，一旦發生衝突，則使用第二個函式H2(key)計算改項到達下一個存儲地址的增量，其取值p和key有關，範圍在1和m之間，並且與m互質的正整數。

D = H1(key);

p = H2(key);

ND = (D+p)%m;

值得提醒的是，對利用開放地址法查了衝突所產生的哈希表中刪除一個元素，不能簡單地直接刪除，因為這樣將截斷其它具有相同哈希地址的元素的查找地址，所以應設定一個特殊的標誌以表明該元素已被刪除。