面试官:Hash 碰撞是什么?如何解决?被问懵了……
面试官 如何 解决 什么 HASH 碰撞
2023-09-27 14:22:37 时间
Hash如何存数据
hash表的本质其实就是数组,hash表中通常存放的是键值对Entry。
如下图:
这里的学号是个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最新版)
4.别再写满屏的爆爆爆炸类了,试试装饰器模式,这才是优雅的方式!!
觉得不错,别忘了随手点赞+转发哦!
相关文章
- 跟面试官讲解CountDownLatch源码设计原理
- 面试官问我什么是软件测试?看了这篇博客面试官彻底被我征服了
- 被面试官问懵:TCP 四次挥手收到乱序的 FIN 包会如何处理?
- 美女面试官问我Python如何优雅的创建临时文件,我的回答....
- 面试官问我HTTP,我真的是
- 面试官:数据库日期类型字段,需要兼容不同数据库,应该如何选择?
- 面试官:如果保证数据库和缓存数据的一致性?面试必问……
- 面试官:有一个 List 对象集合,如何优雅地返回给前端?我懵了。。
- 面试官:什么是脚手架?为什么需要脚手架?常用的脚手架有哪些?
- 面试官:MySQL 如何查找删除重复行?我竟然写不出来。。
- 头条面试官:如何设计群聊消息的已读未读功能?懵了。。
- 面试官:@Transactional 注解是如何实现的?
- 面试官:如何防止 Java 源码被反编译?我竟然答不上来。。
- 面试官:new 关键字在 JVM 中是如何执行的?
- 来,看我是如何把面试官问倒的!
- 面试官:如何设计分布式日志系统?
- 面试官:你知道SPI吗?Java、Spring、Dubbo三者SPI机制的原理和区别了解吗?
- 面试官:ThreadLocal了解吗?用过吗?原理是什么?底层数据如何存储的?
- 面试官:用过cookie吗?怎么工作的?使用场景是什么?
- 面试官:Kafka 如何优化内存缓冲机制造成的频繁 GC 问题?
- 字节面试官问粉丝,如何实现准时的setTimeout
- 面试官问我:如何设计一个秒杀场景?
- 面试官问你如何解决web高并发这样回答就好了
- 软件测试简历?面试题?企业面试官想要什么?我不再和offer失之交臂...
- 大数据必知必会系列——面试官一问就懵:你们做过的项目技术是如何选型的?[新星计划]
- 2019-9-6-逗比面试官成长路线-如何让被面试者觉得糟心
- 面试官: 你了解前端路由吗?