HashMap 是怎么解决哈希冲突的？

2023-09-11 微信公众号程序员的故事

加入收藏

前言

今天来分享一道比较好的面试题，“HashMap 是怎么解决哈希冲突的？”对于这个问题，我们一起看看考察点和比较好的回答吧！

考察点

现在的企业级开发中HashMap几乎是最常用到的容器，了解HashMap 是怎么解决哈希冲突的，有助于我们开发出更加优秀的代码。那么这个问题就是面试官想考察我们是不是平日里善于积累，仔细思考这方面的知识！

回答

关于这个问题，我从三个方面来回答：

1.hash冲突的基础就是hash算法和hash表这种数据结构。先讲讲hash算法和hash表。

①Hash 算法，就是通过散列算法，把任意长度的输入变成固定长度的输出。这个输出就是散列值。

hashValue1  = hash(inputStr1);
hashValue2  = hash(inputStr2);
hashValue1和hashValue2的长度一样

②Hash 表又叫做“散列表”，其本质是通过key，可以直接访问在内存存储位置的数据结构。因此在表现上，我们可以通过hash函数把key映射到散列表中的某个位置，进而获取这个位置的数据，这样能够加快查找速度。

③那么我们所说的hash 冲突，因为哈希算法计算的数据是无穷的，而计算的结果范围是有限的，这样就会造成不同的输入得到的结果确实一样的情况。也就是说发生了冲突。如图所示：

2.如何结果hash冲突呢？这里讲一下常用的4中方法。

①开放定址法，也被称为线性探测法，其原理是这样的，从发生冲突的那个位置开始，通过一定的次序从hash表里面找一个空闲的位置。之后将发生冲突的元素存入到这个空闲位置中。在应用上面，我们常见的ThreadLocal就是用到了线性探测法来解决hash冲突。如图，在 hash 表索引 1 的位置存了一个 key=name，当再次添加key=hobby 时hash 计算得到的索引也是 1，这个就是 hash 冲突。而开放定址法，就是按顺序向前找到一个空闲的位置来存储冲突的 key。

②链式寻址法，这是一种非常常见的方法，简单理解就是把存在 hash 冲突的 key，以单向链表的方式来存储，比如 HashMap 就是采用链式寻址法来实现的。向这样一种情况（如图），存在冲突的 key 直接以单向链表的方式进行存储。

③再 hash 法，就是当通过某个 hash 函数计算的 key 存在冲突时，再用另外一个 hash 函数对这个 key 做 hash，一直运算直到不再产生冲突。这种方式会增加计算时间，性能影响较大。

④. 建立公共溢出区，就是把 hash 表分为基本表和溢出表两个部分，凡是存在冲突的元素，一律放入到溢出表中。

3.HashMap 在 JDK1.8 版本中，通过链式寻址法+红黑树的方式来解决 hash 冲突问题，其中红黑树是为了优化 Hash 表链表过长导致时间复杂度增加的问题。当链表长度大于 8 并且 hash 表的容量大于 64 的时候，再向链表中添加元素就会触发转化。

以上就是我对于这个问题的理解。