大家好呀，我是你们的小米，一个积极活泼的程序员小伙伴！今天我们聊聊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岁程序员。如果你喜欢我的文章，欢迎关注我的微信公众号“软件求生”，获取更多技术干货！