【390期】面试官:Hash碰撞是什么?如何解决?

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

【390期】面试官:Hash碰撞是什么?如何解决?

点击加入:
后端技术内卷群,一起学习!

Hash如何存数据

hash表的本质其实就是数组,hash表中通常存放的是键值对Entry。

如下图:

【390期】面试官:Hash碰撞是什么?如何解决?

这里的学号是个key,哈希表就是根据key值来通过哈希函数计算得到一个值,这个值就是下标值,用来确定这个Entry要存放在哈希表中哪个位置。

Hash碰撞

hash碰撞指的是,两个不同的值(比如张三、李四的学号)经过hash计算后,得到的hash值相同,后来的李四要放到原来的张三的位置,但是数组的位置已经被张三占了,导致冲突。

解决方法

hash碰撞的解决方式是开放寻址法和拉链法。

开放寻址法指的是,当前数组位置1被占用了,就放到下一个位置2上去,如果2也被占用了,就继续往下找,直到找到空位置。

【390期】面试官:Hash碰撞是什么?如何解决?

拉链法采用的是链表的方式,这个时候位置1就不单单存放的是Entry了,此时的Entry还要额外保存一个next指针,指向数组外的另一个位置,将李四安排在这里,张三那个Entry中的next指针就指向李四的这个位置,也就是保存的这个位置的内存地址。如果还有冲突,就把又冲突的那个Entry放到一个新位置上,然后李四的Entry指向它,这样就形成一个链表。

【390期】面试官:Hash碰撞是什么?如何解决?

总结起来:开放寻址法和拉链法都是想办法找到下一个空位置来存发生冲突的值。

来源:blog.csdn.net/zsyoung/article/details/114505480
【390期】面试官:Hash碰撞是什么?如何解决?
主流Java进阶技术(学习资料分享)

与其在网上拼命找题? 不如马上关注我们~

【390期】面试官:Hash碰撞是什么?如何解决?

PS:因为公众号平台更改了推送规则,如果不想错过内容,记得读完点一下“在看”,加个“星标”,这样每次新文章推送才会第一时间出现在你的订阅列表里。“在看”支持我们吧!

原文始发于微信公众号(Java面试题精选):【390期】面试官:Hash碰撞是什么?如何解决?