HashMap啥时候扩容以及扩容原因

╰+攻爆jí腚メ 2023-10-12 23:11 4阅读 0赞

#### HashMap啥时候扩容以及扩容原因 ####

*  存储容器的设计
 *  容器的大小
 *  长度不够怎么办
 *  HashMap是如何扩容的
 *  为什么扩容因子是0.75
 *  面试中遇到该如何回答

## 存储容器的设计 ##

在任何语言里面，我们希望在内存里面去临时存放一段数据，那么可以使用官方封装好的一些集合框架，比如说像List、HashMap、Set等等。  
![在这里插入图片描述][f2b15ccc527b4df8a9ef9b6d90c32b2c.png]  
作为数据存储的一个容器。

## 容器的大小 ##

当我们创建一个集合对象的时候，实际上就是在内存里面一次性的申请了一块内存空间。

而这个内存空间的大小是在创建集合对象的时候去指定的，比如List的默认大小是10，HashMap默认大小是16。

## 长度不够怎么办 ##

在实际开发过程中，我们需要去存储的数据量往往是大于存储容器的大小。

那么针对这个情况，通常做法就是扩容。当集合存储容量达到某个阈值的时候，集合就会进行一个动态扩容，从而去更好的满足更多的数据存储的一个需求。

而List和HashMap本质上是一个数组的结构，所以基本上只需要去新建一个更长的数组，然后把原来数组里面的数据拷贝到新数组里面就可以了。

以HashMap为例，它是什么时候触发扩容以及扩容的原理是什么呢？

## HashMap是如何扩容的 ##

当HashMap里面的元素个数超过临界值的时候会自动触发扩容。这个临界值有一个计算公式：  
![在这里插入图片描述][4bed6263784a4e249d7ee83d4a357878.png]  
负载因子的默认值是0.75，而容量大小默认是16，也就是说元素个数达到12的时候触发扩容。扩容的大小是原来的两倍。

由于动态扩容这个机制的存在，所以我们在实际应用里面需要注意集合初始化的时候，明确去指定集合的大小。

避免频繁扩容带来性能上的影响。假设我们向HashMap里面存1024个元素，如果按照默认的值是16的情况下，随着元素的不断增加，会造成至少7次扩容。

而这7次扩容需要重新去创建新Hash表，并且进行数据的一个迁移，对性能的影响是非常大的。

## 为什么扩容因子是0.75 ##

扩容因子表示Hash表中的元素的填充程度。扩容因子的值越大，那么意味着触发扩容的元素个数会更多。

虽然它的整体空间利用率比较高，但是Hash冲突的概率也会增加。反过来说，扩容因子的值越小，那么触发扩容元素的个数也就越小，那么意味着Hash冲突的概率也会减少。

但是对于内存空间的浪费就比较多了。而且还会增加扩容的一个频率，因此扩容因子的值的设置本质上就是一个冲突的概率以及空间利用率之间的一个平衡。

0.75这个值的来源和统计学里面的泊松分布有关系，我们知道HashMap里面采用的是链式寻址的方式来去解决Hash冲突的问题，而为了避免链表过长带来的一个实践复杂度增加的一个情况，所以链表长度大于等于7的时候，就会转化为红黑树，从而去提升解锁的效率。

当扩容因子在0.75的时候，链表长度达到8的可能性几乎为0，也就是说比较好的达到了一个空间成本和时间成本的一个平衡。

## 面试中遇到该如何回答 ##

当HashMap的元素个数达到扩容阈值，默认是12的情况下，会自动触发扩容，默认扩容大小是原来数组长度的两倍。

HashMap的最大容量是Integer.MAX\_VALUE，也就是2的31次方减1。

**参考资料**：[【Java面试】全网讲的最透彻的HashMap！HashMap啥时候扩容][Java_HashMap_HashMap]

[f2b15ccc527b4df8a9ef9b6d90c32b2c.png]: https://img-blog.csdnimg.cn/f2b15ccc527b4df8a9ef9b6d90c32b2c.png
[4bed6263784a4e249d7ee83d4a357878.png]: https://img-blog.csdnimg.cn/4bed6263784a4e249d7ee83d4a357878.png
[Java_HashMap_HashMap]: https://www.bilibili.com/video/BV15N4y1T7Mn/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb