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

浅浅的花香味﹌ 2023-09-28 20:44 47阅读 0赞

> 欢迎关注`Java`面试系列，不定期更新面试小短文。欢迎一键三连！

#### 文章目录 ####

*  什么是Hash算法？
 *  什么是Hash表？
 *  HashMap是如何解决Hash冲突的？

## 什么是Hash算法？ ##

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

## 什么是Hash表？ ##

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

![c07eb869dfa44282b717196a42faadfe.png][]

## 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` 直接以单向链表的方式进行存储。

![fe3f02c9883540eeb87fc8219ec906df.png][]

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

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

![79624193facd43c2bfa28c18673d14cc.png][]

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

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

欢迎一键三连~  
  
有问题请留言，大家一起探讨学习  
  
\----------------------Talk is cheap, show me the code-----------------------

[c07eb869dfa44282b717196a42faadfe.png]: https://img-blog.csdnimg.cn/c07eb869dfa44282b717196a42faadfe.png
[fe3f02c9883540eeb87fc8219ec906df.png]: https://img-blog.csdnimg.cn/fe3f02c9883540eeb87fc8219ec906df.png
[79624193facd43c2bfa28c18673d14cc.png]: https://img-blog.csdnimg.cn/79624193facd43c2bfa28c18673d14cc.png