漫谈Java集合扩容——从阿里Java编码规约说开来

分类:
JAVA
标签:
集合
编码规约
作者:
何鑫
创作时间:
2019/11/29 12:02:55

摘要:Java集合扩容奥秘尽在其中!

从一条规约说开来

【推荐】在集合初始化时,指定集合初始值大小。

上面是阿里Java编码规约所推荐的一条约定。约定指出,如果未指定大小,集合会按默认容量初始化,以HashMap为例,它的默认容量为16,如果我们需要存储1024个元素,那么集合将需要扩容七次,需要重建七次哈希表,非常消耗性能,所以我们应该根据我们实际需要存储元素的多少来去确定容量,这个公式是:(需要存储的元素个数/负载因子)+ 1。

从源码看端倪

一般我们需要初始化一个集合,以HashMap为例,我们可以这样:

Map<String, String> map = new HashMap<>();

很明显这个是使用无参构造来初始化的,我们可以来看一下源码:

注释告诉我们空构造将使用默认容量16,负载因子使用默认的0.75,那么它在不扩容的情况下能存储的元素个数为16*0.75=12个,超过这个值就会进行扩容,我们用源码来验证。

我们再来看一下HashMap的put方法:

table是HashMap的一个字段,默认为空:

由put方法和table上的注释来看,table是在第一次使用才会被初始化,初始化时调用resize方法:


注意图中的框出来的代码:

在初始化的时候,会依次走上图中框出的代码,重点在第三段,这里会直接把newThr设置为12,然后把字段threshold设置为该值。

我们再往下看put方法:

在这个方法即将结束时,size进行了加一,这个size是键值对的数量:

判断到加1后的size如果大于threshold(此时为12),会进行扩容,继续调resize方法。

如图,扩容会使容量和threshold翻一倍。

现在我们可以下一个结论了,对于HashMap,每当元素达到容量的0.75倍时就会使其扩容,扩容长度为1倍。

如果存1024个元素,使用默认容量,那容量依次为16 32 64 128 256 512 1024 2048,除第一次初始化外,还需扩容七次,对于HashMap来说,每次扩容都需要重建Hash表,还是非常耗费性能的。所以我们在编码时应尽可能的指定容量,如果不确定,可以使用默认值16。

常见集合的默认容量,负载因子及扩容增量

HashMap 默认容量16 负载因子0.75 扩容增量1倍

ArrayList  默认容量10 负载因子1 扩容增量0.5倍+1

Vector     默认容量10 负载因子1 扩容增量1倍

HashSet  默认容量16 负载因子0.75 扩容增量1倍

发表评论

温馨提示: 评论先审核后发布, 请勿发表不良言论

所有评论