（本文摘自mic老师面试文档）
常用数据结构基本上是面试必问的问题，比如 HashMap、LinkList、 ConcurrentHashMap 等。
关于 HashMap，有个学员私信了我一个面试题说： “HashMap 是怎么解决哈希冲突
的？”
关于这个问题，我们来模拟一下普通人和高手对于这个问题的回答。
普通人
嗯.... HashMap 我好久之前看过它的源码，我记得好像是通过链表来解决的！
高手
嗯，这个问题我从三个方面来回答。
1. 要了解 Hash 冲突，那首先我们要先了解 Hash 算法和 Hash 表。（如图）
a. Hash 算法，就是把任意长度的输入，通过散列算法，变成固定长度的输出，这个输出结果是散列值。
b. Hash 表又叫做“散列表”，它是通过 key 直接访问在内存存储位置的数据结 构，在具体实现上，我们通过 hash 函数把 key 映射到表中的某个位置，来获 取这个位置的数据，从而加快查找速度。
c. 所谓 hash 冲突，是由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，所以总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。
d. 通常解决 hash 冲突的方法有 4 种。
i. 开放定址法，也称为线性探测法，就是从发生冲突的那个位置开始，按照 一定的次序从 hash 表中找到一个空闲的位置，然后把发生冲突的元素存 入到这个空闲位置中。ThreadLocal 就用到了线性探测法来解决 hash 冲 突的。
向这样一种情况（如图），在 hash 表索引 1 的位置存了一个 key=name，当再次添加 key=hobby 时，hash 计算得到的索引也是 1，这个就是 hash 冲突。而开放定址法， 就是按顺序向前找到一个空闲的位置来存储冲突的 key。
ii. 链式寻址法，这是一种非常常见的方法，简单理解就是把存在 hash 冲突 的 key，以单向链表的方式来存储，比如 HashMap 就是采用链式寻址法 来实现的。
向这样一种情况（如图），存在冲突的 key 直接以单向链表的方式进行存储。
iii. 再 hash 法，就是当通过某个 hash 函数计算的 key 存在冲突时，再用另
外一个 hash 函数对这个 key 做 hash，一直运算直到不再产生冲突。这种
方式会增加计算时间，性能影响较大。
iv. 建立公共溢出区， 就是把 hash 表分为基本表和溢出表两个部分，凡事存
在冲突的元素，一律放入到溢出表中。
e. HashMap 在 JDK1.8 版本中，通过链式寻址法+红黑树的方式来解决 hash 冲
突问题，其中红黑树是为了优化 Hash 表链表过长导致时间复杂度增加的问题。
当链表长度大于 8 并且 hash 表的容量大于 64 的时候，再向链表中添加元素
就会触发转化。
以上就是我对这个问题的理解！
结尾
这道面试题主要考察 Java 基础，面向的范围是工作 1 到 5 年甚至 5 年以上。
因为集合类的对象在项目中使用频率较高，如果对集合理解不够深刻，容易在项目中制
造隐藏的 BUG。
所以，再强调一下，面试的时候，基础是很重要的考核项！！
![[极客大挑战 2019]Http1](https://img-blog.csdnimg.cn/95a8c2c87cbf4afbb042007076f2df9e.png)
