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

前言今天来分享一道比较好的面试题， “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 的时候，再向链表中添加元素就会触发转化。
以上就是我对于这个问题的理解。

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