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

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/149888.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 用户案例怎么写_用户运营案例

    用户案例怎么写_用户运营案例用户案例 – 3Cs

  • Java——教师类

    Java——教师类Description设计一个教师类Teacher,要求:属性有编号(intno)、姓名(Stringname)、年龄(intage)、所属学院(Stringseminary),为这些属性设置相应的get和set方法。为Teacher类重写equals方法,要求:当两个教师对象的no相同时返回true。重写Teacher类的toString方法,通过该方法可以返回“no:**…

  • CSS面试题

    CSS面试题1.有哪些方式(CSS)可以隐藏页面元素?1.opacity:0本质是将元素的透明度降为0,看起来是隐藏了,但是依然占据空间2.visibility:hidden占据空间3.display:none彻底隐藏元素,元素从文档流中消失,不占据空间4.z-index:-9999原理是将层级放到底部,看起来是隐藏了5.overflow:hidden这个只是隐藏元素溢出的部分6.transform:scale(0,0)将元素缩放为0,但是依然占据空间2.em\px\rem区别?Px:绝对

  • Android 使用动态载入框架DL进行插件化开发

    Android 使用动态载入框架DL进行插件化开发

  • IDEA设置背景为自定义照片「建议收藏」

    IDEA设置背景为自定义照片「建议收藏」一分钟教你把女朋友的照片设置成IDEA的背景图片【建议收藏】1.为什么写这篇文章?2.操作方法2.1.步骤12.2.步骤22.3.快捷操作一2.4.快捷操作二1.为什么写这篇文章?事情是这样的,在2021年6月10日早上我在CSDN上发布了文章《你真的懂Java怎么输出HelloWorld吗?》。这篇文章就如同标题一样,讲的是Java输出HelloWorld时源码的实现原理,本身再正常不过的一篇文章,但没想到的是。。十几天过去了,我却收到如下的评论??!!大家居然对我的IDEA背

  • 推荐5款好用的Java软件,初学者必看「建议收藏」

    推荐5款好用的Java软件,初学者必看「建议收藏」“工欲善其事必先利其器”,想要学好Java,除了要有好的学习资源之外,还要有一套适合自己的Java软件,好的软件能极大提高你的学习和工作效率。那么,学Java用什么软件好呢?下面小千为大家推荐5款好用的Java软件。

发表回复

您的电子邮箱地址不会被公开。

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