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

解决哈希冲突的方法「建议收藏」在实际的应用中,选取合适的哈希函数可减少冲突,但冲突是不可避免的。所以我就想给大家说几种解决哈希冲突的方法啦~首先就是开放定址法,用这个方法处理冲突的核心思想就是在冲突发生的时候,形成一个地址序列,顺着这个序列挨个去检查探测,一直等到找到一个“空”的开放地址。把我们发生冲突的关键字值存放到这个“空”地址中去。这个地址的算法一般就是:Hi=(H(key)+di)%m  这里面的i=1,2,。

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

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

首先就是开放定址法,用这个方法处理冲突的核心思想就是在冲突发生的时候,形成一个地址序列,顺着这个序列挨个去检查探测,一直等到找到一个“空”的开放地址。把我们发生冲突的关键字值存放到这个“空”地址中去。这个地址的算法一般就是: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

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • npm安装和卸载全局包

    其中install可以缩小为i例如:npmii5ting_toc-g

    2022年4月12日
    45
  • 【MyBatis学习13】MyBatis中的二级缓存[通俗易懂]

    【MyBatis学习13】MyBatis中的二级缓存[通俗易懂]1.二级缓存的原理  前面介绍了,mybatis中的二级缓存是mapper级别的缓存,值得注意的是,不同的mapper都有一个二级缓存,也就是说,不同的mapper之间的二级缓存是互不影响的。为了更加清楚的描述二级缓存,先来看一个示意图:  从图中可以看出:sqlSession1去查询用户id为1的用户信息,查询到用户信息会将查询数据存储到该UserMapper的二级缓存中。

    2022年9月15日
    3
  • batch内负采样

    batch内负采样一般在计算softmax交叉熵时,需要用tf.nn.log_uniform_candidate_sampler多itemid做随机负采样。但是在类似dssm这种双塔模型中,item侧特征除了itemid外,还有其他meta特征,此时负样本对itemid做负采样后,还需要取相应负样本的meta特征。可是在tf训练数据中并不方便建立itemid与各类meta特征的映射表。为了解决dssm类模型的负采样问题,可以取一个batch内其他用户的正样本做为本用户的负样本,以解决负采样meta特征问题。好了,废话少说,

    2022年6月23日
    65
  • mysql tinyint长度_mysql设置取值范围0到100

    mysql tinyint长度_mysql设置取值范围0到100Tinyint占用1字节的存储空间,即8位(bit)。那么Tinyint的取值范围怎么来的呢?我们先看无符号的情况。无符号的最小值即全部8位(bit)都为0,换算成十进制就是0,所以无符号的Tinyint的最小值为0.无符号的最大值即全部8bit都为1,11111111,换算成十进制就是255.这很好理解。有符号的Tinyint的取值范围是怎么来的呢?在计算机中,用最高位表示符号。0表示正,1表示…

    2022年9月16日
    1
  • java静态变量,静态方法的理解

    java静态变量,静态方法的理解

    2021年7月16日
    70

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号