奇怪,为什么 ArrayList 初始化容量大小为 10?HashMap 的初始化容量为 16?
背景
看 ArrayList 源码时,无意中看到 ArrayList 的初始化容量大小为 10,这就奇怪了!我们都知道 ArrayList 和 HashMap 底层都是基于数组的,但为什么 ArrayList 不像用 HashMap 那样用 16 作为初始容量大小,而是采用 10 呢?
于是各方查找资料,求证了这个问题,这篇文章就给大家讲讲。
为什么 HashMap 的初始化容量为 16?
在聊 ArrayList 的初始化容量时,要先来回顾一下 HashMap 的初始化容量。这里以 Java 8 源码为例,HashMap 中的相关因素有两个:初始化容量及装载因子:
在 HashMap 当中,数组的默认初始化容量为 16,当数据填充到默认容量的 0.75 时,就会进行 2 倍扩容。当然,使用者也可以在初始化时传入指定大小。但需要注意的是,最好是 2 的 n 次方的数值,如果未设置为 2 的 n 次方,HashMap 也会将其转化,反而多了一步操作。
关于 HashMap 的实现原理的内容,这里就不再赘述,网络上已经有太多文章讲这个了。有一点我们需要知道的是 HashMap 计算 Key 值坐标的算法,也就是通过对 Key 值进行 Hash,进而映射到数组中的坐标。
此时,保证 HashMap 的容量是 2 的 n 次方,那么在 hash 运算时就可以采用位运行直接对内存进行操作,无需转换成十进制,效率会更高。
通常,可以认为,HashMap 之所以采用 2 的 n 次方,同时默认值为 16,有以下方面的考量:
减少 hash 碰撞;
提高 Map 查询效率;
分配过小防止频繁扩容;
分配过大浪费资源;
总之,HashMap 之所以采用 16 作为默认值,是为了减少 hash 碰撞,同时提升效率。
ArrayList 的初始化容量是 10 吗?
下面,先来确认一下 ArrayList 的初始化容量是不是 10,然后在讨论为什么是这个值。
先来看看 Java 8 中,ArrayList 初始化容量的源码:
很明显,默认的容器初始化值为 10。而且从 JDK1.2 到 JDK1.6,这个值也始终都为 10。
从 JDK1.7 开始,在初始化 ArrayList 的时候,默认值初始化为空数组:
此处肯定有朋友说,Java 8 中 ArrayList 默认初始化大小为 0,不是 10。而且还会发现构造方法上的注释有一些奇怪:构造一个初始容量 10 的空列表。什么鬼?明明是空的啊!
保留疑问,先来看一下 ArrayList 的 add 方法:
在 add 方法中调用了 ensureCapacityInternal 方法,进入该方法一开始是一个空容器所以 size=0 传入的 minCapacity=1:
上述方法中先通过 calculateCapacity 来计算容量:
会发现 minCapacity 被重新赋值为 10 (DEFAULT_CAPACITY=10),传入 ensureExplicitCapacity(minCapacity);这 minCapacity=10,下面是方法体:
上述代码中 grow 方法是用来处理扩容的,将容量扩容为原来的 1.5 倍。
了解上面的处理流程,我们会发现,本质上 ArrayList 的初始化容量还是 10,只不过使用懒加载而已,这是 Java 8 为了节省内存而进行的优化而已。所以,自始至终,ArrayList 的初始化容量都是 10。
这里再多提一下懒加载的好处,当有成千上万的 ArrayList 存在程序当中,10 个对象的默认大小意味着在创建时为底层数组分配 10 个指针(40 或 80 字节)并用空值填充它们,一个空数组(用空值填充)占用大量内存。如果能够延迟初始化数组,那么就能够节省大量的内存空间。Java 8 的改动就是出于上述目的。
为什么 ArrayList 的初始化容量为 10?
最后,我们来探讨一下为什么 ArrayList 的初始化容量为 10。其实,可以说没有为什么,就是“感觉”10 挺好的,不大不小,刚刚好,眼缘!
首先,在讨论 HashMap 的时候,我们说到 HashMap 之所以选择 2 的 n 次方,更多的是考虑到 hash 算法的性能与碰撞等问题。这个问题对于 ArrayList 的来说并不存在。ArrayList 只是一个简单的增长阵列,不用考虑算法层面的优化。只要超过一定的值,进行增长即可。所以,理论上来讲 ArrayList 的容量是任何正值即可。
ArrayList 的文档中并没有说明为什么选择 10,但很大的可能是出于性能损失与空间损失之间的最佳匹配考量。10,不是很大,也不是很小,不会浪费太多的内存空间,也不会折损太多性能。
如果非要问当初到底为什么选择 10,可能只有问问这段代码的作者“Josh Bloch”了吧。
如果你仔细观察,还会发现一些其他有意思的初始化容量数字:
ArrayList 与 Vector 初始化容量一样,为 10;HashSet、HashMap 初始化容量一样,为 16;而 HashTable 独独使用 11,又是一个很有意思的问题。
小结
有很多问题是没有明确原因、明确的答案的。就好像一个女孩儿对你没感觉,可能是因为你不够好,也可能是她已经爱上别人了,但也有很大可能你是不会知道答案。但在寻找原因和答案的过程中,还是能够学到很多,成长很多的。没有对比就没有伤害,比如 HashMap 与 ArrayList 的对比,没有对比就不知道是否适合,还比如 HashMap 与 ArrayList。当然,你还可以试试特立独行的 HashTable,或许适合你呢。
评论