查找算法【哈希表】 – 处理冲突的方法
无论如何设计散列函数，都无法避免发生冲突。
如果发生冲突，就需要处理冲突。
处理冲突的方法分为3种：
- 开放地址法
- 链地址法
- 建立公共溢出区。
【开放地址法】
开放地址法是线性存储空间上的解决方案，也被称为闭散列。
当发生冲突时，采用冲突处理方法在线性存储空间上探测其他位置。hash′(key)=(hash(key)+di )%m ，其中，hash(key)为原散列函数，hash′(key)为探测函数，di 为增量序列，m 为表长。
根据增量序列的不同，开放地址法又分为线性探测法、二次探测法、随机探测法、再散列法。
① 线性探测法
线性探测法是最简单的开放地址法，线性探测的增量序列为di =1,…,m -1。
例如，有一组关键字(14,36,42,38,40,15,19,12,51,65,34,25)，若表长为15，散列函数为hash(key)=key%13，则可采用线性探测法处理冲突，构造该散列表。
按照关键字顺序，根据散列函数计算散列地址，如果该地址空间为空，则直接放入；如果该地址空间已存储数据，则采用线性探测法处理冲突。
[1] 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号空间。
[2] hash(40)=40%13=1，1号空间已存储数据，采用线性探测法处理冲突。
hash′(40)=(hash(40)+di )%m ，di =1,…,m -1
d1 =1：hash′(40)=(1+1)%15=2，2号空间为空，将40放入2号空间，即hash(40)=40%13=1→2。
[3] hash(15)=15%13=2，2号空间已存储数据，发生冲突，采用线性探测法处理冲突。
hash′(15)=(hash(15)+di )%m ，di =1,…,m -1
- d1 =1：hash′(15)=(2+1)%15=3，3号空间已存储数据，继续进行线性探测。
- d2 =2：hash′(15)=(2+2)%15=4，4号空间为空，将15放入4号空间。
即hash(15)=15%13=2→3→4。
[4] hash(19)=19%13=6，将19放入6号空间；hash(12)=12%13=12，12号空间已存储数据，采用线性探测法处理冲突。
hash′(12)=(hash(12)+di )%m ，di =1,…,m -1
d 1 =1：hash′(12)=(12+1)%15=13，12号空间为空，将12放入13号空间，即hash(12)=12%13=12→13。
[5] hash(51)=51%13=12，12号空间已存储数据，采用线性探测法处理冲突。
hash′(51)=(hash(51)+di )%m，di =1,…,m -1
- d1 =1：hash′(51)=(12+1)%15=13，13号空间已存储数据，继续进行线性探测。
- d2 =2：hash′(51)=(12+2)%15=14，14号空间为空，将51放入14号空间。
即hash(51)=51%13=12→13→14。
[6] hash(65)=65%13=0，将65放入0号空间；hash(34)=34%13=8，将34放入8号空间；
hash(25)=12%13=12，12号空间已存储数据，采用线性探测法处理冲突。
hash′(25)=(hash(25)+di )%m ，di =1,…,m -1
- d1 =1：hash′(25)=(12+1)%15=13，13号空间已存储数据，继续进行线性探测。
- d2 =2：hash′(25)=(12+2)%15=14，14号空间已存储数据，继续进行线性探测。
- d3 =3：hash′(25)=(12+3)%15=0，0号空间已存储数据，继续进行线性探测。
- d4 =4：hash′(25)=(12+4)%15=1，1号空间已存储数据，继续进行线性探测。
- d5 =5：hash′(25)=(12+5)%15=2，2号空间已存储数据，继续进行线性探测。
- d6 =6：hash′(25)=(12+6)%15=3，3号空间已存储数据，继续进行线性探测。
- d7 =7：hash′(25)=(12+7)%15=4，4号空间已存储数据，继续进行线性探测。
- d8 =8：hash′(25)=(12+8)%15=5，5号空间为空，将25放入5号空间
即hash(25)=25%13=12→13→14→0→1→2→3→4→5。
注意： 线性探测法很简单，只要有空间，就一定能够探测到位置。但是，在处理冲突的过程中，会出现非同义词之间对同一个散列地址发生争夺的现象，称之为“堆积”。例如，上图中25和38是同义词，25和12、51、65、14、40、42、15均非同义词，却探测了9次才找到合适的位置，大大降低了查找效率。
性能分析：
1 查找成功的平均查找长度。假设查找的概率均等（12个关键字，每个关键字查找的概率均为1/12），查找成功的平均查找长度等于所有关键字查找成功的比较次数ci 乘以查找概率 之和，即
。可以看出，1次比较成功的有7个，2次比较成功的有2个，3次比较成功的有2个，9次比较成功的有1个，乘以查找概率求和，因为查找概率均为1/12，也可以理解为比较次数求和后除以关键字个数12。其查找成功的平均查找长度为ASLsucc =(1×7+2×2+3×2+9)/12=4/3。
2 查找失败的平均查找长度。本题中的散列函数为hash(key)=key%13，计算得到的散列地址为0,1,…,12，一共有13种情况，那么有13种查找失败的情况，查找失败的平均查找长度等于所有关键字查找失败的比较次数 乘以查找概率 之和，即
。当hash(key)=0时，如果该空间为空，则比较1次即可确定查找失败；如果该空间非空，关键字又不相等，则继续采用线性探测法向后查找，直到遇到空，才确定查找失败，计算比较次数。类似地，在hash(key)= 1,…,12时也如此计算。
本题的散列表如下表所示。
- hash(key)=0：从该位置向后一直比较到7时为空，查找失败，比较8次。
- hash(key)=1：从该位置向后一直比较到7时为空，查找失败，比较7次。
- hash(key)=2：从该位置向后一直比较到7时为空，查找失败，比较6次。
- hash(key)=3：从该位置向后一直比较到7时为空，查找失败，比较5次。
- hash(key)=4：从该位置向后一直比较到7时为空，查找失败，比较4次。
- hash(key)=5：从该位置向后一直比较到7时为空，查找失败，比较3次。
- hash(key)=6：从该位置向后一直比较到7时为空，查找失败，比较2次。
- hash(key)=7：该位置为空，查找失败，比较1次。
- hash(key)=8：从该位置向后一直比较到9时为空，查找失败，比较2次。
- hash(key)=9：该位置为空，查找失败，比较1次。
- hash(key)=10：从该位置向后一直比较到11时为空，查找失败，比较2次。
- hash(key)=11：该位置为空，查找失败，比较1次。
hash(key)=12：从该位置向后比较到表尾，再从表头开始向后比较（像循环队列一样），一直比较到7时为空，查找失败，比较11次。
假设查找失败的概率均等（13种失败情况，每种情况发生的概率都为1/13），查找失败的平均查找长度等于所有关键字查找失败的比较次数乘以概率之和。查找失败的平均查找长度为ASLunsucc =(1×3+2×3+3+4+5+6+7+8+11)/13=53/13。
算法实现：
int H(int key){ //哈希函数
return key % 13;
}
int Linedetect(int HT[] , int H0 , int key , int &cnt){
int Hi;
for(int i = 1 ; i < m ; i++){
cnt ++;
Hi = (H0 + i) % m; //按照线性探测法计算下一个哈希地址Hi
if(HT[Hi] == NULLKEY){
return Hi; //若单元Hi为空，则所查元素不存在
}
else if(HT[Hi] == key){
return Hi; //若单元Hi 中元素的关键字为key
}
}
return -1;
}
int SearchHash(int HT[] , int key){
//在哈希表HT中查找key，若查找成功，则返回下标，否则返回-1
int H0 = H(key); //根据哈希函数计算哈希地址
int Hi , cnt = 1;
if(HT[H0] == NULLKEY){ //若单元H0为空，则所查元素不存在
return -1;
}
else if(HT[H0] == key){ //若单元H0 中元素的关键字为key，则查找成功
cout << "查找成功，比较次数：" << cnt << endl;
return H0;
}
else{
Hi = Linedetect(HT , H0 , key , cnt);
if(HT[Hi] == key){ //若单元Hi 中元素的关键字为key，则查找成功
cout << "查找成功，比较次数：" << cnt << endl;
return Hi;
}
else{
return -1; //若单元Hi为空，则所查元素不存在
}
}
}
bool InsertHash(int HT[] , int key){
int H0 = H(key); //根据哈希函数H(key) 计算哈希地址
int Hi = -1 , cnt = 1;
if(HT[H0] == NULLKEY){
HC[H0] = 1; //统计提交次数
HT[H0] = key; //若单元H0 为空，则放入
return 1;
}
else{
Hi=Linedetect(HT , H0 ,key , cnt); //线性探测
if((Hi != -1) && (HT[Hi] == NULLKEY) ){
HC[Hi] = cnt;
HT[Hi] = key; //若单元Hi为空，则放入
return 1;
}
}
return 0;
}
文章出处登录后可见！
