查找算法【哈希表】 - 处理冲突的方法：开放地址法-二次探测法 & 随机探测法 & 再散列法

查找算法【哈希表】 - 处理冲突的方法：开放地址法-二次探测法 & 随机探测法 & 再散列法

【二次探测法】

二次探测法指采用前后跳跃式探测的方法，发生冲突时，向后1位探测，向前1位探测，向后2^2 位探测，向前2^2 位探测……以跳跃式探测，避免堆积。

二次探测的增量序列为di =1^2 , -1^2 , 2^2 , -2^2 , …, k^2 , -k^2（k ≤m /2）。

【举个栗子】

例如，有一组关键字（14,36,42,38,40,15,19,12,51,65,34,25），若表长为15，散列函数为hash(key)=key%13，则可采用二次探测法处理冲突，构造该散列表。

【构造流程】

按照关键字的顺序，根据散列函数计算散列地址，如果该地址空间为空，则直接放入；如果该地址空间已存储数据，则采用线性探测法处理冲突。

① hash(14)=14%13=1，将14放入1号空间（下标为1）hash(36)=36%13=10，将36放入10号空间；hash(42)=42%13=3，将42放入3号空间；hash(38)=38%13=12，将38放入12号空间。

② hash(40)=40%13=1，1号空间已存储数据，采用二次探测法处理冲突。

hash′(40)=(hash(40)+di )%m ，di =1^2 , -1^2 , 2^2 , -2^2 , …, k^2 ,-k^2 （k ≤m /2）

d 1 =1^2 ：hash′(40)=(1+1^2 )%15=2，2号空间为空，将40放入2号空间。

即hash(40)=40%13=1→2。

③ hash(15)=15%13=2，2号空间已存储数据，发生冲突，采用二次探测法处理冲突。

hash′(15)=(hash(15)+di )%m ，di =1^2 , -1^2 , 2^2 , -2^2 , …, k^2 ,-k^2 （k ≤m /2）

• d1 =1^2 ：hash′(15)=(2+1^2 )%15=3，3号空间已存储数据，继续进行二次探测。
• d2 =-1^2 ：hash′(15)=(2-1^2 )%15=1，1号空间已存储数据，继续进行二次探测。
• d3 =2^2 ：hash′(15)=(2+2^2 )%15=6，6号空间为空，将15放入6号空间。
• 即hash(15)=15%13=2→3→1→6。

④ hash(19)=19%13=6，6号空间已存储数据，采用二次探测法处理冲突。

d1 =1^2 ：hash′(19)=(6+1^2 )%15=7，7号空间为空，将19放入7号空间。

即hash(19)=19%13=6→7。

hash(12)=12%13=12，12号空间已存储数据，采用二次探测处理冲突。

d1 =1^2 ：hash′(12)=(1²⁺¹2 )%15=13，13号空间为空，将12放入13号空间。

即hash(12)=12%13=12→13。

⑤ hash(51)=51%13=12，12号空间已存储数据，采用二次探测处理冲突。

• d1 =1^2 ：hash′(51)=(1²⁺¹2 )%15=13，13号空间已存储数据，继续进行二次探测。
• d2 =-1^2 ：hash′(51)=(1^2-12 )%15=11，11号空间为空，将51放入11号空间。

即hash(51)=51%13=12→13→11。

⑥ hash(65)=65%13=0，将65放入0号空间；hash(34)=34%13=8，将34放入8号空间。

⑦ hash(25)=25%13=12，12号空间已存储数据，采用二次探测法处理冲突。

注意：在二次探测过程中如果二次探测地址为负值，则加上表长即可。

• d1 =1^2 ：hash′(25)=(1²⁺¹2 )%15=13，已存储数据，继续进行二次探测。
• d2 =-1^2 ：hash′(25)=(1^2-12 )%15=11，已存储数据，继续进行二次探测。
• d3 =2^2 ：hash′(25)=(1²⁺²2 )%15=1，已存储数据，继续进行二次探测。
• d4 =-2^2 ：hash′(25)=(1^2-22 )%15=8，已存储数据，继续进行二次探测。
• d5 =3^2 ：hash′(25)=(1²⁺³2 )%15=6，已存储数据，继续进行二次探测。
• d6 =-4^2 ：hash′(25)=(1^2-32 )%15=3，已存储数据，继续进行二次探测。
• d7 =4^2 ：hash′(25)=(1²⁺⁴2 )%15=13，已存储数据，继续进行二次探测。
• d8 =-4^2 ：hash′(25)=(1^2-42 )%15=-4，-4+15=11，已存储数据，继续进行二次探测。
• d9 =5^2 ：hash′(25)=(1²⁺⁵2 )%15=7，已存储数据，继续进行二次探测。
• d10 =-5^2 ：hash′(25)=(1^2-52 )%15=-13，-13+15=2，已存储数据，继续进行二次探测。
• d11 =6^2 ：hash′(25)=(1²⁺⁶2 )%15=3，已存储数据，继续进行二次探测。
• d12 =-6^2 ：hash′(25)=(1^2-62 )%15=-9，-9+15=6，已存储数据，继续进行二次探测。
• d13 =7^2 ：hash′(25)=(1²⁺⁷2 )%15=1，已存储数据，继续进行二次探测。
• d14 =-7^2 ：hash′(25)=(1^2-72 )%15=-7，-7+15=8，已存储数据，继续进行二次探测。

即12→13→11→1→8→6→3→13→11→7→2→3→6→1→8。

已探测到(m /2)^2 ，还没找到位置，探测结束，存储失败，此时仍有4个空间，却探测失败。

注意： 二次探测法是跳跃式探测方法，效率较高，但是会出现有空间却探测不到的情况，因而存储失败。而线性探测法只要有空间就一定能够探测成功。

【算法实现】

int Seconddetect(int HT[] , int H0 , int key , int &cnt){
	int Hi;
	for(int i = 1 ; i <= m / 2 ; ++i){
		int i1 = i * i;
		int i2 = -i1;
		cnt ++;
		Hi = (H0 + i1) % m; //采用线性探测法计算下一个哈希地址Hi
		if(HT[Hi] == NULLKEY){ //若单元Hi 中元素的关键字为key
			return Hi;
		}
		cnt ++;
		Hi = (H0 + i2) % m; //采用探测法计算下一个哈希地址Hi
		if(Hi < 0 ){
			Hi += m;
		}
		if(HT[Hi] == NULLKEY){ //若单元Hi为空，则所查元素不存在
			return Hi;
		}
		else if(HT[Hi] == key){ //若单元Hi 中元素的关键字为key
			return Hi;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

【随机探测法】

随机探测法采用伪随机数进行探测，利用随机化避免堆积。随机探测的增量序列为di =伪随机序列。

【再散列法】

再散列法指在通过散列函数得到的地址发生冲突时，再利用第2个散列函数处理，称之为双散列法。再散列法的增量序列为di =hash2(key)。

注意： 采用开放地址法处理冲突时，不能随便删除表中的元素，若删除元素，则会截断其他后续元素的探测，若要删除一个元素，则可以做一个删除标记，标记其已被删除。