HashMap如何解决哈希冲突

逃离我推掉我的手 2023-09-26 22:39 41阅读 0赞

### HashMap如何解决哈希冲突 ###

*  Hash算法和Hash表
 *  Hash冲突
 *  解决哈希冲突的方法
 *   *  开放地址法
     *  链式寻址法
     *  再hash法
     *  建立公共溢出区

# Hash算法和Hash表 #

Hash算法就是把任意长度的输入通过**散列算法**编程固定长度的输出。这个输出结果就是一个**散列值**。  
![在这里插入图片描述][a4c5bd26ef4d410394983649de24eeb0.png]  
Hash表又称为“**散列表**”，它是通过key直接访问到内存存储位置的数据结构。在具体的实现上，我们通过Hash函数把key映射到表中的某个位置，来获取这个位置的数据，从而去加快数据的查找。

# Hash冲突 #

所谓的Hash冲突是由于哈希算法被计算的数据是无限的。而计算后的结果的范围是有限的。

所以总会存在不同的数据经过计算之后得到的值是一样的。那么这种情况下就会出现所谓的哈希冲突。

# 解决哈希冲突的方法 #

通常解决哈希冲突的方法有**四种**。

## 开放地址法 ##

也称**线性探测法**，就是从发生冲突的那个位置开始，按照一定次序，从Hash表中去找到一个空闲的位置，然后把发生冲突的元素存入到这个位置。

而在Java中，**ThreadLocal就用到了线性探测法来解决Hash冲突**。

![在这里插入图片描述][5e569a37b5a84c9bbfa2c7de8e5e7304.png]  
像这种情况，在Hash表索引1的位置存了一个key=name，再向它添加key=hobby的时候，假设Hash计算得到的索引也是1。那么这个时候，我们称为Hash冲突。而开放地址法就是按照顺序向前去找到一个空闲的位置来存储这个冲突的key。

## 链式寻址法 ##

把存在Hash冲突的key以**单向链表**的方式来进行存储。比如HashMap就用到了链式寻址法来实现。  
![在这里插入图片描述][bc02e62c1be24687b4e463dc38729abd.png]  
存在冲突的key直接以单向链表的方式去进行存储。

## 再hash法 ##

某个Hash函数计算的Key存在冲突的时候，**再用另外一个Hash函数**对这个Key进行Hash，一直运算直到不再产生冲突为止。

这种方式会增加计算的时间。性能上会有一些影响。

## 建立公共溢出区 ##

把Hash表分为**基本表**和**溢出表**这两个部分。凡是存在冲突的元素一律放到溢出表中。

HashMap在JDK 1.8版本中是通过链式寻址法以及红黑树的方式来解决Hash冲突问题的。

其中红黑树是为了优化Hash表的链表过长导致时间复杂度增加的一个问题。当**链表长度大于8**并且给**Hash表的容量大于64**的时候，再向链表中添加元素，就会触发链表向红黑树的一个转换。

**参考资料**：[【Java面试】数据结构面试必问题，HashMap如何解决哈希冲突？][Java_HashMap]

[a4c5bd26ef4d410394983649de24eeb0.png]: https://img-blog.csdnimg.cn/a4c5bd26ef4d410394983649de24eeb0.png
[5e569a37b5a84c9bbfa2c7de8e5e7304.png]: https://img-blog.csdnimg.cn/5e569a37b5a84c9bbfa2c7de8e5e7304.png
[bc02e62c1be24687b4e463dc38729abd.png]: https://img-blog.csdnimg.cn/bc02e62c1be24687b4e463dc38729abd.png
[Java_HashMap]: https://www.bilibili.com/video/BV1Au411z77B/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb