散列表的删除与冲突处理 - 平方探测
接下来我们看冲突处理中的平方探测法（终于写出来了- -、），平方探测顾名思义就是探测增量是1²、-1²、2²、-2²…（线性探测是1、2、3、4……），平方探测与线性探测有点不同，线性探测是查找位置发生冲突后，就往后探测，后一个位置又有冲突的话，继续往后探测，直到找到空位置为止，所以说只要散列表上有空的单元格，线性探测就一定可以找到空位置。但是平方探测不一定，平方探测的做法是：查找某个位置，如果发现冲突了，先往后探测，就是往1²探测，如果1²位置也有冲突，就往前探测，探测-1²的位置，如果-1²位置为空就插入，不为空也就是有冲突就向2²位置探测，接着是-2²、3²、-3²……这样的平方探测法，是不是散列表中有空位就一定能够探测出来呢？我们看一个例子：
散列表的最大长度为5，表中已存在元素3个，假如此时插入了一个元素21，会出现什么样的情况？21对5求余得1，散列表上1这个位置已经有元素了，那么按照平方探测法就会去探测原来位置+1²这个位置（也就是散列地址为2），2这个位置有12这个元素了，接着往-1²位置，也就是下标为0的位置上，发现还有元素，再往2²位置探测，这时我们看，初始的散列位置1+2²等于散列地址为0这个位置，发现回到之前探测过的位置了，这个位置不行，就到-2²探测，等于又回到2这个位置。。。。你可以亲自验证一下，3²也是这样，4²也是这样，就是出现一种什么样的情况呢，散列表中是有空位置的，但就是一直查找不出来，这就很尴尬了。平方探测法的存在一定是有它的理由的，它的优点在于减轻线性探测的“聚集”现象（就是很多元素在相邻的散列地址上“堆积”了起来，这样会大大降低查找效率）。
怎么办？看书上说：“有证明表示，如果散列表长度是某个4K+3(K是正整数)形式的素数时，平方探测法就可以探测到整个散列表的空间。这一点很重要，是我们能够放心使用平方探测法的理论保证。”
好啦，既然我们可以放心使用平方探测法，那么就来看看代码要怎么实现吧：
/*平方探测法*/
Position SquareFind(HashTable H, ElemType Data)
{
/*前者指示初始插入位置,后置指示实际插入位置*/
Position currentPos, newPos;
int collisionNum=0; /*记录发生冲突的次数*/
int numCount=0;
if (Data!=-1) {
/*首先根据散列函数计算出插入位置*/
newPos=currentPos=Hash(Data, H->TableSize);
/*得到初始插入位置后,判断该位置是否为空或者是否发生冲突*/
while (H->Cells[newPos].Info!=Empty && H->Cells[newPos].Data!=Data) {
collisionNum++;
/*如果是奇数次操作,也就是正数的平方探测*/
if (++numCount%2) {
/*12 -12 22 -22 32 -32 42 -42*/
/*1 2 3 4 5 6 7 8*/
newPos=currentPos+(numCount+1)*(numCount+1)/4;
/*判断插入位置是否有越界,有就调整*/
if (newPos>=H->TableSize) {
newPos=newPos%H->TableSize;
}
} else {
/*如果是偶数次操作,也就是负数的平方探测*/
newPos=currentPos-numCount*numCount/4;
/*下标越界判断*/
while (newPos<0) {
newPos+=H->TableSize;
}
}
}
printf("元素%d插入操作:\t散列地址=%d\t实际地址=%d\t冲突次数=%d\n", Data,currentPos, newPos, collisionNum);
}
return newPos;
}对比线性探测，我们多要一个变量numCount，这个变量用来干什么，边看代码边说。第171行根据散列函数获得元素的散列地址后，查找这个初始地址上有没有位置插入，如果位置不空或且这个元素不是我们要找的元素，第176行就先++numCount之后再对2求余，为什么是先++numCount呢，因为第一次平方探测是1²，第一次探测numCount等于1是奇数，对2求余不为0，所以就会做奇数次探测该做的，也就是增量为正数的探测（这里表述的不好- -、）。
我再详细表述一遍，numCount是用来标识当前是奇数还是偶数次探测的变量。例如第一次探测（奇数次探测）增量是1²，numCount从0开始++等于1，由于奇数所以执行179行，探测的散列地址等于currentPos（初始散列地址）+ （numCount+1）²/4，也就是等于1，增量为1。第二次探测增量是-1²，我们来看，第二次是偶数次探测，++numCount等于2，偶数所以进入186行，探测的散列地址等于currentPos-numCount²/4，等于减了1。
我们继续看下去，第三次探测增量应为2²，numCount等于3，（3+1）²/4=4，所以就是增量为2²了，第四次探测增量应为-2²，所以（4*4）/4=4前面有个“-”号所以增量就是-2²。就是这样完成平方探测。
对于字符串散列表，也是一样的：
/*平方探测查找*/
Position SquareFind(HashTable H, ElemType Data[])
{
/*前者指示初始插入位置,后置指示实际插入位置*/
Position currentPos, newPos;
int collisionNum=0; /*记录发生冲突的次数*/
int numCount=0;
if (strcmp(Data, "-1")!=0) {
/*根据散列函数找到该元素应该放的初始位置*/
newPos=currentPos=Hash(Data, H->TableSize);
/*如果该位置的单元格非空,并且不是要找的元素时,即发生了冲突*/
while (H->Cells[newPos].Info!=Empty && strcmp(H->Cells[newPos].Data, Data)!=0) {
/*冲突次数+1*/
collisionNum++;
if (++numCount%2) {
/*12 -12 22 -22 32 -32 42 -42*/
/*1 2 3 4 5 6 7 8*/
newPos=currentPos+(numCount+1)*(numCount+1)/4;
/*判断插入位置是否有越界,有就调整*/
if (newPos>=H->TableSize) {
newPos=newPos%H->TableSize;
}
} else {
/*如果是偶数次操作,也就是负数的平方探测*/
newPos=currentPos-numCount*numCount/4;
/*下标越界判断*/
while (newPos<0) {
newPos+=H->TableSize;
}
}
}
//puts(Data);
printf("元素插入操作:\t散列地址=%d\t实际地址=%d\t冲突次数=%d,\n", currentPos, newPos, collisionNum);
}
return newPos; /*此时的newPos位置是Data的位置,或者是一个空单元格的位置*/
}
运行结果：
最后再来看看散列表的删除操作吧！其实对于散列表的删除，通常是指“懒惰删除”法，也就是我们想要删除某个元素，只把它所在的单元格状态设置为“Deleted”,标识这个单元格里有被删除的元素，这样做是为了下一次查找操作时防止出现“断链情况”，因为我们看上面的代码，无论线性探测还是平方探测，我们根据散列函数找到元素的初始散列地址后，都是判断这个地址单元格状态是否为空，且单元格上的元素是不是等于我们要查找的元素，如果这个单元格为空但是里面没有元素，那么这段代码就出问题了，当我们做插入操作时都是要用到查找函数，如果要插入的元素在单元格里存在了，我们就要返回，但是如果我们插入操作中的查找过程发现某个单元格没有元素，查找操作就没法做比较，所以说代码执行到这里就会出问题，就是上面说的“断链“问题。为了解决这种情况，我们对散列表的删除就采用”懒惰删除“，这样虽然单元格里有元素但是状态为”Deleted“，遇到这种单元格我们仍然可以对它做插入操作。下面是删除操作的代码：
/*散列表的删除操作*/
bool Delete(HashTable H)
{
ElemType Data;
printf("\n请输入要删除的元素：");
scanf("%d", &Data);
/*删除前查找元素是否存在*/
Position Pos=UserSquareFind(H, Data);
if (Data!=-1 && H->Cells[Pos].Info!=Empty && H->Cells[Pos].Data==Data) {
/*如果这个单元格元素不空且等于要删除的元素*/
/*修改这个单元格的状态为"删除"*/
H->Cells[Pos].Info=Deleted;
return true;
} else {
return false;
}
}字符串散列表的删除操作：
/*散列表的删除操作*/
bool Delete(HashTable H)
{
char i[15];
printf("\n请输入要删除的元素：");
gets(i);
/*删除前查找元素是否存在*/
Position Pos=UserSquareFind(H, i);
if (strcmp(i, "finish")!=0 && H->Cells[Pos].Info!=Empty && strcmp(H->Cells[Pos].Data, i)==0) {
/*如果这个单元格元素不空且等于要删除的元素*/
/*修改这个单元格的状态为"删除"*/
H->Cells[Pos].Info=Deleted;
return true;
} else {
return false;
}
}
以上的所有完整代码都在我的GitHub上：
https://github.com/justinzengtm/Hashing/blob/master/integer_hashtable_square%20probing.c
https://github.com/justinzengtm/Hashing/blob/master/string_hashtable_square%20probing.c