HashMap夺命3连问

女爷i 2024-03-17 00:32 173阅读 0赞

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

*   *   *  1.HashMap什么时候扩容，如何扩容？
         *  2.那HashMap是在什么时候触发扩容呢？它的扩容原理是什么呢？
         *  3.那为什么负载因子是0.75，而不是其他的值呢？

#### 1.HashMap什么时候扩容，如何扩容？ ####

在任何编程语言中，我们经常需要在内存中临时去存放一段数据，我们可以使用官方封装好的一些集合框架，比如List、HashMap、Set等等作为临时数据存储的容器。

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

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

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

#### 2.那HashMap是在什么时候触发扩容呢？它的扩容原理是什么呢？ ####

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

threadshold = loadFactory * capacity
    
    临界值 = 负载因子 * 容量大小

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

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

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

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

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

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

我们知道，HashMap采用的是链式寻址的方式来解决Hash冲突的问题。而为了避免链表过长，导致时间复杂度增加的情况，所以，HashMap判断链表长度大于等于8的时候，就会转换成红黑树，从而提升检索的效率。当负载因子为0.75的时候，链表的长度达到8的可能性几乎为0，也就是说，比较好的做到了空间成本和时间成本的平衡。

**如果您认为这篇文章对您有所帮助，希望能给我点一个免费的赞或收藏，这将是我创作的动力和鼓励！**