本篇文章为你整理了面试官:Hash 碰撞是什么?如何解决?被问懵了……(hash碰撞的解决方法)的详细内容,包含有hash碰撞的解决办法 hash碰撞的解决方法 hash碰撞的表现 hash碰撞和hash冲突 面试官:Hash 碰撞是什么?如何解决?被问懵了……,希望能帮助你了解 面试官:Hash 碰撞是什么?如何解决?被问懵了……。
分享Java技术,高并发编程,分布式技术,架构设计,Java面试题,算法,行业动态,程序人生等。
如下图:
这里的学号是个key,哈希表就是根据key值来通过哈希函数计算得到一个值,这个值就是下标值,用来确定这个Entry要存放在哈希表中哪个位置。
Hash碰撞
hash碰撞指的是,两个不同的值(比如张三、李四的学号)经过hash计算后,得到的hash值相同,后来的李四要放到原来的张三的位置,但是数组的位置已经被张三占了,导致冲突。
hash碰撞的解决方式是开放寻址法和拉链法。
开放寻址法指的是,当前数组位置1被占用了,就放到下一个位置2上去,如果2也被占用了,就继续往下找,直到找到空位置。
拉链法采用的是链表的方式,这个时候位置1就不单单存放的是Entry了,此时的Entry还要额外保存一个next指针,指向数组外的另一个位置,将李四安排在这里,张三那个Entry中的next指针就指向李四的这个位置,也就是保存的这个位置的内存地址。如果还有冲突,就把又冲突的那个Entry放到一个新位置上,然后李四的Entry指向它,这样就形成一个链表。
总结起来:开放寻址法和拉链法都是想办法找到下一个空位置来存发生冲突的值。
更多 Java 教程:https://www.javastack.cn/java/
来源:blog.csdn.net/zsyoung/article/details/114505480
近期热文推荐:
1.1,000+ 道 Java面试题及答案整理(2022最新版)
2.劲爆!Java 协程要来了。。。
3.Spring Boot 2.x 教程,太全了!
4.别再写满屏的爆爆爆炸类了,试试装饰器模式,这才是优雅的方式!!
5.《Java开发手册(嵩山版)》最新发布,速速下载!
觉得不错,别忘了随手点赞+转发哦!
以上就是面试官:Hash 碰撞是什么?如何解决?被问懵了……(hash碰撞的解决方法)的详细内容,想要了解更多 面试官:Hash 碰撞是什么?如何解决?被问懵了……的内容,请持续关注盛行IT软件开发工作室。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。