解决哈希冲突的方法「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

在实际的应用中，选取合适的哈希函数可减少冲突，但冲突是不可避免的。所以我就想给大家说几种解决哈希冲突的方法啦~

首先就是开放定址法，用这个方法处理冲突的核心思想就是在冲突发生的时候，形成一个地址序列，顺着这个序列挨个去检查探测，一直等到找到一个“空”的开放地址。把我们发生冲突的关键字值存放到这个“空”地址中去。这个地址的算法一般就是：Hi=(H(key)+di)%m 这里面的i=1，2，。。。k。k要<=m-1；i是探测次数。不难理解，H(key)是关键字是key的哈希函数，加上di（每次再探测时的地址增量）对这个哈希表的长度做取余数的运算。根据di的取法不同，就可以得到不同的开放地址处理冲突探测的方法~

形成探测序列的方法很多，比如线性探测法、二次探测法、双哈希函数探测法。

二次探测法的地址增量序列为di=1^2,-1^2,2^2,-2^2,….q^2,-q^2,(q小于等于m/2，i为d的下标),这是一种较好的处理冲突的方法，它能够避免“聚集”现象。它的缺点就是不能探测到哈希表上的所有存储单元，但至少能探测到一半的存储单元。

双哈希函数探测法：Hi=(H(key)+i*RH(key))%m (i=1,2,…,m-1).其中，H(key)，RH(key)是两个哈希函数，m为哈希长度。这个方法使用两个哈希函数，先用第一个函数H(key)对关键字计算哈希地址，一旦产生地址冲突，在用第二个函数RH(key)确定移动的步长因子，最后，通过步长因子序列由探测函数寻找空余的哈希地址。

那我就只说线性探测咯，比较基础易懂。

线性探测法：当哈希函数产生的数据元素的哈希地址中已有数据元素存在时，就是发生了冲突，从下一地址序列中寻找可以用的存储空间来存储数据元素。

关于线性探测法，我们举个例子吧！

假设有一个关键字集合，S={16，76，63，57，40}，使用哈希法存储该集合，选取的哈希函数为：h（K）=K%m，即用数据元素的关键字K去整除哈希表的长度m，取余数作为存储该数据元素的哈希地址，其中，K和m均为正整数，并m要大于等于集合长度n。此时，n=5，m=11，所以每个元素的哈希地址以此为5，10，8，2，7.吧这几个数就放到0~10中相应数字的位置。这个时候，向刚刚构造的哈希表中插入27，50两个元素。若发生冲突就用线性探测发处理。27的哈希地址为5，已经被占用，接着探查下一个，即下标为6的存储单元，该单元空，所以把27放在6里，这个时候再看50的哈希地址为6，6已经被27占用，就接着探查下一个，发现7被40占用，就继续探测，一直到9，发现空闲，就把50放在9里。

用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：

① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。

② 按上述算法建立起来的哈希表，删除工作非常困难。如果将此元素删除，查找的时会发现空槽，则会认为要找的元素不存在。只能标上已被删除的标记，否则，将会影响以后的查找。

③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。

线性再散列法是形式最简单的处理冲突的方法。插入元素时，如果发生冲突，算法会简单的从该槽位置向后循环遍历hash表，直到找到表中的下一个空槽，并将该元素放入该槽中（会导致相同hash值的元素挨在一起和其他hash值对应的槽被占用）。查找元素时，首先散列值所指向的槽，如果没有找到匹配，则继续从该槽遍历hash表，直到：（1）找到相应的元素；（2）找到一个空槽，指示查找的元素不存在，（所以不能随便删除元素）；（3）整个hash表遍历完毕（指示该元素不存在并且hash表是满的）

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/149888.html原文链接：https://javaforall.net