image

编辑人: 流年絮语

2024-11-20

0

690

hash冲突如何解决

分析&回答

方法1:链地址法

对于相同的哈希值,使用链表进行连接。(HashMap使用此法)

image-1691395134463

优点:处理冲突简单,无堆积现象。即非同义词决不会发生冲突,因此平均查找长度较短;
适合总数经常变化的情况。(因为拉链法中各链表上的结点空间是动态申请的)
占空间小。装填因子可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计
删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点:查询时效率较低。(存储是动态的,查询时跳转需要更多的时间)
在key-value可以预知,以及没有后续增改操作时候,开放定址法性能优于链地址法。
不容易序列化

法2:再哈希法

提供多个哈希函数,如果第一个哈希函数计算出来的key的哈希值冲突了,则使用第二个哈希函数计算key的哈希值。

优点:不易产生聚集
缺点:增加了计算时间

法3:建立公共溢出区

将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

法4:开放定址法

所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。当关键字key的哈希地址p =H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,若p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。

即:Hi=(H(key)+di)% m (i=1,2,…,n)

用开放定址法解决冲突的做法是:当冲突发生时,使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字,即查找失败。

反思&扩展


喵呜面试助手: 一站式解决面试问题,你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享!

创作类型:
原创

本文链接:hash冲突如何解决

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。
分享文章