hashMap 源码详解

ゝ一世哀愁。 2024-03-16 14:11 21阅读 0赞

## 1、 HashMap 底层源码解读(源码分析+知识问答) ##

![在这里插入图片描述][5ed1467e93a14754b64f038cfe3186d2.png]

## 2、 什么是哈希碰撞？或者什么是哈希冲突？为什么会发生哈希冲突？ ##

> 不同的关键字通过相同的哈希函数算出了一个相同的 哈希地址，这就叫做哈希冲突。  
> 哈希冲突主要因为 哈希表底层的数组容量是小于实际存储的关键字的数量，所以发生冲突是必然的，我们只能够尽量避免，不能完全消除。

## 3、 如何设计哈希函数？你了解哈希函数怎么设计吗？ ##

> 引起哈希冲突的一个方面就是哈希函数设计的不够合理。哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突  
> 设计哈希函数我们的原则是  
> 1).降低碰撞和溢出的产生  
> 2).哈希函数设计简单  
> 3).函数计算的地址尽量均与分布在整个空间提高空间利用率。

## 4、 常见的哈希函数 ##

> 常见的哈希函数，可以说出来两三个，随便解释一下

> 除留余数法  
> 设置散列表中允许的地址数为m，取一个不大于m，但是接近于m或者等于m 的质数p作为除数，按照哈希函数：  
> Hash(key) = key%p ，将关键字转换成哈希地址

> 直接定址法  
> 计算关键字的某个线性函数得到哈希地址  
> Hash(key) = A\*key+B  
> 优点： 设计简单、均匀分布  
> 缺点：需要事先知道关键字的分布情况  
> 适用的场景：查找比较小且连续的情况

## 5、 如何避免哈希冲突？ ##

> 设计更合理的哈希函数  
> 哈希函数设计的越精妙，产生冲突的概率就越低。

> 调节负载因子  
> 什么是负载因子，负载因子就是 填入表中的元素数量/散列表的长度

![在这里插入图片描述][409345c4ed054c9fa0bfff0fc229073d.png]

> 负载因子和冲突率的关系是成正比的，因为填入表中的元素不能够改变，所以我们只能调节数组的长度。  
> 所以降低冲突率，就是降低负载因子的大小，因此我们只能够把增大散列表的长度（到达阈值扩容）来降低冲突率。

[5ed1467e93a14754b64f038cfe3186d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/cd67f2de65824f779fd010c4b2ea1fb7.png
[409345c4ed054c9fa0bfff0fc229073d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/1b38c897c2274660b7df95c5624e7a47.png