【Java面试小短文】HashMap是如何解决Hash冲突的？

什么是Hash算法？

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

什么是Hash表？

Hash 表又叫做“散列表”，它是通过 key 直接访问在内存存储位置的数据结构， 在具体实现上，我们通过 hash 函数把 key 映射到表中的某个位置，来获取这个位置的数据，从而加快查找速度。如图：

HashMap是如何解决Hash冲突的？

HashMap底层是采用数组结构来存储数据元素，数组的默认长度是16，当我们通过put方法去添加数据的时候，HashMap会根据key的hash值进行取模运算，最终把这样一个值保存到数组的指定位置。

  但是这样的设计方式会存在hash冲突的问题，也就是两个不同的hash值的key，取模后会落到同一个数组下标，所以HashMap引入了一个链式寻址法来解决hash冲突的问题。也就是说对于存在冲突的key，HashMap把这些key组成一个单向链表，然后采用尾插法把这样一个key保存到链表的一个尾部，另外，为了避免链表过长导致查询效率下降，所以当链表长度大于8并且数组长度大于等于64的时候，HashMap会把当前链表转换为红黑树，从而去减少链表数据查询的时间复杂度来提升查询效率。

解决hash冲突的方法有很多，比如

1. 链式寻址法。是一种非常常见的方法，简单理解就是把存在 hash 冲突的 key， 以单向链表的方式来存储，比如 HashMap 就是采用链式寻址法来实现的。

如图，像这样一种情况，存在冲突的 key 直接以单向链表的方式进行存储。

1. 开放寻址法，也称为线性探测法。就是直接从冲突的数组位置向下去寻找一个空的数组下标，进行数据的存储，在ThredLocal里面有使用到这个线性探测法。

  如图：像这样一种情况，在 hash 表索引 1 的位置存了一个 key=name，当再次添加 key=hobby 时，hash 计算得到的索引也是 1，这个就是 hash 冲突。而线性探测法就是按顺序向前找到一个空闲的位置来存储冲突的 key。

1. 再哈希法。如果某个hash函数产生了冲突，那么再用另外一个hash函数进行计算，一直计算直到不再产生冲突。这种方式会增加计算时间，性能影响较大。比如像布隆过滤器就采用了这种方法。
2. 建立公共溢出区。把 hash 表分为基本表和溢出表两个部分，把存在冲突的key统一放在一个公共溢出区里面进行存储。

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