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

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


相关推荐

  • pycharm常用快捷键总结

    pycharm常用快捷键总结工欲善其事,必先利其器。Python开发利器Pycharm常用快捷键以及配置如下,相信有了这些快捷键,你的开发会事半功倍!一常用快捷键编辑类:Ctrl+D复制选定的区域或行Ctrl+Y删除选定的行Ctrl+Alt+L代码格式化Ctrl+Alt+O优化导入(去掉用不到的包导入)Ctrl+鼠标简介/进入代码定义Ctrl+/行注释、取消注释C…

  • datagrip 2022 激活码 mac(JetBrains全家桶)「建议收藏」

    (datagrip 2022 激活码 mac)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~9AAG1RZ8NI-eyJsaWNlb…

  • VUE父子组件之间的传值,以及兄弟组件之间的传值;

    VUE父子组件之间的传值,以及兄弟组件之间的传值;一、Vue父子组件之间传值vue使用中,经常会用到组件,好处是:1、如果有一个功能很多地方都会用到,写成一个组件就不用重复写这个功能了;2、页面内容会简洁一些;方便管控;子组件的传值是通过props来传递数据,$emit来触发事件;下面是一个简单的子组件props传值:父组件的部分:首先引入组件,在组件上绑定你要传给组件的值;然后,在组件里通过props来接收你从父页面传…

  • 项目管理知识体系五大过程组(项目管理10大知识领域)

    信息系统项目管理师属于计算机技术与软件专业技术资格(水平)考试五大高级资格考试中的一项,是信息系统建设领域的高级项目经理资质申报的直接性前提条件。通过本考试的合格人员能够掌握信息系统项目管理的知识体系,具有高级工程师的实际工作能力和业务水平。通过本考试的基本用途有以下2个:1、评职称:此证书在国企和事业单位可以评职称。2、申报项目经理:此证书可在自己所在企业申报系统集成项目经理,如果…

  • 什么是泛型,怎么使用泛型分析

    什么是泛型,怎么使用泛型分析1、泛型1:什么是泛型?泛型就是广泛的类型,也是一种数据类型,而这种数据类型可以是任意类型,编写过程中当中不能确定类型,创建对象时必须指定具体类型,不指定也可以,但是会出现一些错误。泛型是编译器行为,只能在编译期有效,如果能够跨过编译器,那么泛型就没有任何意义了。2、泛型类怎么定义泛型类?在类后面加<&g…

  • laravel5.4 前后台未登陆,跳转到各自的页面

    laravel5.4 前后台未登陆,跳转到各自的页面

    2021年10月25日

发表回复

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

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