查找算法【哈希表】 - 处理冲突的方法：开放地址法-二次探测法 & 随机探测法 & 再散列法
【二次探测法】
二次探测法指采用前后跳跃式探测的方法，发生冲突时，向后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)=(12+12 )%15=13，13号空间为空，将12放入13号空间。
即hash(12)=12%13=12→13。
⑤ hash(51)=51%13=12，12号空间已存储数据，采用二次探测处理冲突。
- d1 =1^2 ：hash′(51)=(12+12 )%15=13，13号空间已存储数据，继续进行二次探测。
- d2 =-1^2 ：hash′(51)=(12-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)=(12+12 )%15=13，已存储数据，继续进行二次探测。
- d2 =-1^2 ：hash′(25)=(12-12 )%15=11，已存储数据，继续进行二次探测。
- d3 =2^2 ：hash′(25)=(12+22 )%15=1，已存储数据，继续进行二次探测。
- d4 =-2^2 ：hash′(25)=(12-22 )%15=8，已存储数据，继续进行二次探测。
- d5 =3^2 ：hash′(25)=(12+32 )%15=6，已存储数据，继续进行二次探测。
- d6 =-4^2 ：hash′(25)=(12-32 )%15=3，已存储数据，继续进行二次探测。
- d7 =4^2 ：hash′(25)=(12+42 )%15=13，已存储数据，继续进行二次探测。
- d8 =-4^2 ：hash′(25)=(12-42 )%15=-4，-4+15=11，已存储数据，继续进行二次探测。
- d9 =5^2 ：hash′(25)=(12+52 )%15=7，已存储数据，继续进行二次探测。
- d10 =-5^2 ：hash′(25)=(12-52 )%15=-13，-13+15=2，已存储数据，继续进行二次探测。
- d11 =6^2 ：hash′(25)=(12+62 )%15=3，已存储数据，继续进行二次探测。
- d12 =-6^2 ：hash′(25)=(12-62 )%15=-9，-9+15=6，已存储数据，继续进行二次探测。
- d13 =7^2 ：hash′(25)=(12+72 )%15=1，已存储数据，继续进行二次探测。
- d14 =-7^2 ：hash′(25)=(12-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;
}
【随机探测法】
随机探测法采用伪随机数进行探测，利用随机化避免堆积。随机探测的增量序列为di =伪随机序列。
【再散列法】
再散列法指在通过散列函数得到的地址发生冲突时，再利用第2个散列函数处理，称之为双散列法。再散列法的增量序列为di =hash2(key)。文章来源：https://www.toymoban.com/news/detail-498968.html
注意： 采用开放地址法处理冲突时，不能随便删除表中的元素，若删除元素，则会截断其他后续元素的探测，若要删除一个元素，则可以做一个删除标记，标记其已被删除。文章来源地址https://www.toymoban.com/news/detail-498968.html
到了这里，关于查找算法【哈希表】 - 处理冲突的方法：开放地址法-二次探测法 & 随机探测法 & 再散列法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
