视频加载中...

一位2年工作经验的小伙伴面试时被问到，说，HashMap什么时候扩容，为什么要扩容？这个问题本身不是很难，但是这位小伙伴对底层实现原理没有太多关注，所以，被这个问题难住了。

下面我给大家分析一下这个问题的底层逻辑。

另外，6/7/8月份资料文档已整理，包含如下↓（还在持续更新中！）：

①100道最新大厂经典面试题解析资料文档！

②15万+字Java面试题解析和配套答案！

③从应届生到高级开发都适用的简历模板！

④从入门到精通的架构师学习路线图！

想获取的小伙伴可以S信我【666】免费领取！

1 数据存储容器

在任何编程语言中，我们经常需要在内存中去临时存放一段数据，我们可以使用官方封装好的一些集合框架。

比如说用List、HashMap、Set等等作为临时数据存储的容器。

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

比如HashMap的默认大小是16。

2 动态扩容

在实际开发过程中，我们需要去存储的数据量往往是大于存储容器的默认大小的。所以，出现容量默认大小不能满足需求时，就需要扩容。而这个扩容的动作是由集合自动完成的，每种集合的扩容规则都有差异。但总的扩容原则是，当集合存储容量达到某个阈值的时候，集合就会进行动态扩容，而更好地满足更多数据存储的需求。

而HashMap中，用来存储数据的容器，本质上是一个数组结构。基本的扩容逻辑就是新建一个更长的数据，然后把原来数组里面的数据Copy到新的数组里面就可以了。

那HashMap是在什么触发扩容呢？它的扩容原理是什么呢？

3 扩容原理

当HashMap里面的元素个数超过临界值的时候会自动触发扩容。这个临界值的计算公式如图所示：

它等于负载因子 乘以 容量大小，负载因子的默认值是0.75，而容量大小默认是16,。也就是说，第1次扩容的动作会在元素个数达到12的时候触发，扩容的大小是原来的2倍。HashMap的最大容量是Integer.MAX_VALUE也就是2的31次方减1。

由于动态扩容机制的存在，所以我们在实际应用的时候，最好在集合初始化的时候明确去指定集合的大小，从而避免频繁扩容带来性能上的消耗。

假设，我们向HashMap中插入1024个元素，如果按照默认容量大小是16的情况下，随着元素的不断增加，会造成至少7次扩容。而这7次扩容过程中，需要重新去创建新的Hash表，并且进行数据的迁移，对性能的影响是非常大的。

那为什么负载因子是0.75，而不是其他的值呢？

3 负载因子

负载因子表示Hash表中的元素填充程度。负载因子的值越大，也就意味着触发扩容的元素个数就越多。虽然，它的整体空间利用率会比较高，但是Hash冲突的概率也会增加。那么，反之，负载因子的值越小，那么触发扩容元素的个数也就越少，也就意味着Hash冲突的概率也会减少。但是，对于内存空间的浪费自然就比较多了，而且还会增加扩容的频率。

因此，扩容因子的值的设置，本质上就是一个冲突的概率以及空间利用率之间的一个平衡。关于0.75这个值的来源，和统计学里面的泊松分布有关系。

我们知道，HashMap采用的是链式寻址的方式来解决Hash冲突的问题。而为了避免链表过长，导致时间复杂度增加的情况，所以，HashMap判断链表长度大于等于8的时候，就会转换为红黑树，从而提升检索的效率。

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

好了，以上就是我对HashMap扩容的理解。

我是被编程耽误的文艺Tom，如果我的分享对你有帮助，请动动手指分享给更多的人。关注我，面试不再难！