大家好呀，我是你们的小米，一个积极活泼的程序员小伙伴！今天我们聊聊Java面试中的常见问题——“HashMap是怎么解决哈希冲突的？”。相信不少人都对这个问题既熟悉又陌生，知道它很重要，但要讲清楚，可能还得捋一捋思路。别急，今天我们就通过一个小故事，轻松搞懂这个知识点！ HashMap的世界：存储的艺术 想象一个图书管理员阿牛，他需要管理一间藏书丰富的图书馆。为了快速找到书，阿牛决定设计一个存书系统： 书本编号（Key）： 每本书都有独特的编号，类似HashMap的key。 书柜号（哈希函数）： 阿牛通过某种算法，把书的编号转化为一个书柜号，这相当于HashMap的hashCode()。 书的位置（存储）： 阿牛把书放进对应的书柜。 问题来了：哈希冲突 一天，阿牛发现编号 123 和 789 的两本书，居然被分配到同一个书柜里！这就是哈希冲突——不同的Key，经过哈希函数计算，得到了相同的Hash值。 这种情况在HashMap里并不罕见，因为HashMap的底层结构决定了哈希值会映射到一个固定大小的数组中，必然存在冲突的可能。那么阿牛该怎么办呢？ HashMap的解决方案 为了应对哈希冲突，阿牛想出了两种办法，分别对应HashMap在不同版本中的处理方式： 1. 链地址法（JDK 1.8之前的实现） 阿牛决定用链表解决问题。如果书柜里已经有书，他就直接在书柜旁边放一个篮子，把新书放进篮子里。 每次存书时，阿牛会先检查书柜里是否已经有书。如果有，就把新书添加到链表的尾部。 每次取书时，阿牛会按照链表依次查找，直到找到目标书。 在代码中，链地址法就是用链表存储同一个桶（bucket）中的所有Key-Value对：
虽然这种方法简单易行，但当链表长度过长时，性能会急剧下降。因为查找需要遍历整个链表，时间复杂度从理想情况下的O(1)退化为O(n)。 2. 红黑树（JDK 1.8之后的新方案） 阿牛觉得链表太慢了，于是升级了他的存书策略——如果书柜旁边的篮子（链表）里的书超过一定数量（8本），他就用红黑树来替代链表。 红黑树是一种自平衡二叉搜索树，能够显著提升查找效率： 存储时： 如果篮子里的书数量超过了阈值，就将链表转换为红黑树。 查找时： 红黑树的时间复杂度是O(log n)，比链表的O(n)高效得多。 在代码中，红黑树的实现逻辑看起来大致如下：
这里有一个小细节：如果HashMap的容量较小，链表不会直接转换为红黑树，而是优先扩容。这是因为红黑树相对复杂，适用于大规模数据。 总结：HashMap的两种处理方式 为了方便大家记忆，我们用一个表格总结一下：
面试中的延伸问题 如果你在面试中被问到这个问题，面试官可能还会进一步追问： 1、哈希冲突的概率高吗？ 答：HashMap的哈希函数经过优化，尽量均匀分布Key，但冲突无法完全避免。 2、为什么选用红黑树？ 答：红黑树具有自平衡特性，插入、删除和查找的效率较高，且最坏情况的时间复杂度是O(log n)。 3、什么时候会退化为链表？ 答：如果HashMap的容量不足，冲突严重，链表长度可能增加。 彩蛋：如何手写一个简易HashMap？ 如果你有时间，不妨自己尝试实现一个简易版的HashMap，帮助加深理解：
END 写到这里，小米想问问大家：你在用HashMap时有没有遇到过什么坑？欢迎留言一起讨论呀！下次我们再聊聊“HashMap在多线程环境中的坑”！记得关注和点赞哦，啾咪~ 我是小米，一个喜欢分享技术的29岁程序员。如果你喜欢我的文章，欢迎关注我的微信公众号“软件求生”，获取更多技术干货！
