解决散列冲突的方法有哪些

A. 散列查找的处理冲突的方法

思路：从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元的一类处理冲突的方法。
在使用该方法处理冲突的散列表中，查找一个元素的过程是：先根据给定关键字K，利用与插入时使用的同一散列函数h(K)计算出散列地址(设下标为d),然后用K同d单元的关键字比较，若相等则查找成功，否则按插入时处理冲突的相同次序，依次用K同所查单元的关键字比较，直到查找成功或查找到一空单元(表明查找失败)为止。
有三种常见的开放寻址法
（1）线性探查法
是用开放寻址法处理冲突的一种最简单的探查方法。
从发生冲突的d单元起,依次探查下一个单元,直到碰到一个空闲单元或探查完所有单元为止探查时,当达到下标为m-1的表尾单元时,下一个探查的单元是下标为0的表首单元。
探查序列为d,d+1,d+2……，表示为(d+i)%m (0≤i≤m-1)。
例如：构取m=13,线性表为A=(18,75,60,43,54,90,46)，构造的散列表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 46 60 75 90 现向表中再插入关键字为31和58的两个元素,用线性探查法解决冲突。
先插入31，h(31)=31%13=5,因H[5]被占用，探查下一个即下标为6的单元，空闲，插入31。 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 31 46 60 75 90 再插入58，h(58)=58%13=6,因H[6]被占用，探查下一个即下标为7的单元，因H[7]仍不空闲，再接着向下探查，当探查到下标为9的单元时，空闲，插入58。 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 31 46 60 58 75 90 利用线性探查法处理冲突易造成元素的“堆积”(聚集) 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 46 60 75 90 向散列表中插入一个元素：
int Insert (hashlist1 HT,int m,ElemType item)
{
//向长度为m的散列表HT中插入一个元素
int d=H(item.key,m); //可选一种合适的构造散列函数的方法，计算散列地址
int temp=d;
while(HT[d].key != NullTag)
{
//当d单元不空时继续向后查找空位置
d=(d+1)%m;
if(d==temp) return 0;
}
HT[d]=item; //将新元素插入到下标为d的位置
return 1;
}
从散列表中查找一个元素：
int Search (hashlist1 HT,int m, ElemType item)
{
//从长度为m的散列表HT中查找
int d=H(item.key, m);
int temp=d;
while(HT[d].key!=NullTag)
{
//当散列地址中的关键字域不为空则循环
if(HT[d].key==item.key) return d;
else d=(d+1)%m;
if(d==temp) return -1;
}
return -1;
}
（2）平方探查法
探查序列为d,d+1,d+2……,表示为(d+i2)%m(0≤i≤m-1)。递推公式为：
优点：它是一种较好的处理冲突的方法，可以较好避免堆积现象
缺点：不能探查到散列表上所有单元。
例：当d0=5,m=17时，只能探查到下标依次为5、6、9、14、4、13、7、3、1的单元。
d0=5;
d1=(5 +2*1-1)%17=6; d2=(6 +2*2-1)%17=9;
d3=(9 +2*3-1)%17=14; d4=(14 +2*4-1)%17=4;
d5=(4 +2*5-1)%17=13; d6=(13 +2*6-1)%17=7;
d7=(7 +2*7-1)%17=3; d8=(3 +2*8-1)%17=1; d9=(1 +2*9-1)%17=1;
（3）双散列函数探查法
思路：
该方法使用两个散列函数h1和h2，其中h1和前面的h(K)一样，以关键字为自变量，产生一个0～m-1之间的数作散列地址;h2也以关键字为自变量，产生一个1～m-1之间的、并和m互素的数作散列地址。它的探查序列为：
利用双散列法，按一定的距离，跳跃式地寻找“下一个”桶，减少了“堆积”的机会，最多经过m-1次探查，它会遍历表中所有位置，回到H0 位置。
例：给出一组表项关键码{22,41,53,46,30,13,01,67}。散列表为HT[0..10]，m = 11。
散列函数为：
Hash(x)=(3x) % 11
再散列函数为：
ReHash(x) = (7x) % 10 +1
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2,
H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6
H0(30) = 2 冲突H1 = (2+1) = 3 ,H0(13) = 6 冲突H1 = (6+2) = 8
H0(01) = 3 冲突H1 = (3+8) = 0 ,H2 = (0+8) = 8 H3 = (8+8) = 5
H4 =(5+8)=2 H5 =(2+8)=10,H0(67)=3 冲突, H1 = (3+10) = 2 H2 = (2+10) = 1
搜索成功的平均搜索长度：
链接法
思路：就是把发生冲突的同义词元素(结点)用单链表链接起来的方法。
例：假定一个线性表B为：B=(18,75,60,43,54,90,46,31,58,73,15,34)。
设采用的散列函数为h(K)=K%13,采用链接法处理：
在该例中，查找成功时平均查找长度为：
ASL=(8×1+3×2+1×3)/12≈1.42
若线性探查法处理冲突进行散列存储，得到：
查找成功时平均查找长度为：
ASL=(7×1+1×2+1×4+1×4+1×2+1×6)/12≈2.1
多种方法分析
在散列表的插入和查找算法中，平均查找长度与表的大小m无关，只与选取的散列函数、α值和处理冲突的方法有关,若假定所选取的散列函数能够使任一关键字等概率地映射到散列空间的任一地址上，理论上证明：
当采用线性探查法处理冲突时，ASL=
当采用链地址法处理冲突时，ASL=
当采用平方探查法、双散列函数法处理冲突时，ASL=
散列存储优缺点
插入与查找的速度相当快根据关键字计算散列地址需要开销一定计算时间占用存储空间较多在散列表中只能按关键字查找元素线性表中元素的逻辑关系无法在散列表中体现。 链表地址法为散列表的每个表象建立一个单链表，用于链接同义词表，为此需要给每个表项增加一个指针域。
关于同义词表的建立，有两种方法。一种方法是在散列表的基本存储区域外开辟一个新的区域用于存储同义词表，这种方法称为“分离的同义词子表法”，或称“独立链表地址法”，这个分离的同义词子表所在的区域称为“溢出区”。另一种方法是不建立溢出区，而是将同义词子表存储在散列表所在的基本存储区域里，例如，可以再基本存储区域里从后向前探测空闲表项，找到后就将其链接到同义词子表中，这个方法称为“结合的同义词子表法”，或称为“公共链表地址法”。
独立链表地址法是查找效率最好的解决冲突的方法，速度要快于开放地址法，因为独立链表地址法在进行散列查找时仅需搜索同义词表。开放地址法要求表长时固定的，而地理链表法中的表项则是动态分配的，其表长仅受内存空间的限制。链表法的主要缺点是需要为每个表项（包括分离的同义子表的每个节点）设立一个指针域。
总之，独立链表地址法的动态结构使它成为散列法中解决冲突的首选方法。

B. 线性探测再散列技术是如何解决冲突的

线性探测再散列也称杂凑技术。是一种较快的查找技术。

线性探测再散列是哈希表解决冲突的一种计算方法，Hi=(H(key)+di)%m，i=1,2,……k(k<=m-1)，H(key)哈希函数，m哈希表长，di增量序列当，di值可能为1,2,3,...m-1，称线性探测再散列，用该方法处理冲突的方法：开放寻址法、再散列法和链地址法（拉链法）。

解决冲突的方法一般有线性探测再散列法、随机探测法、再哈希法、链地址法等，其中线性再散列法较简单，其计算公式为：Hi＝（H（K）+di）MOD p式中di＝1，2，…

常用的哈希函数

1.直接寻址法。仅适合于：地址集合的大小 == 关键字集合的大小。

2.数字分析法。对关键字进行分析，取关键字的若干位或其组合作哈希地址。仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

3.平方取中法。以关键字的平方值的中间几位作为存储地址。

4.折叠法。将关键字分割成位数相同的几部分，然后取这几部分的叠加和(舍去进位)做哈希地址。移位叠加/间界叠加。适合于: 关键字的数字位数特别多，且每一位上数字分布大致均匀情况。

5.除留余数法。取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key%p，p<=m。

6.随机数法。取关键字的伪随机函数值作哈希地址，即H(key)=random(key)，适于关键字长度不等的情况。

以上内容参考：线性探测再散列-学术网络-知网空间