ArrayList 扩容:5,000,000 次 add,不预设容量真实多搬运了 1230 多万个元素

真实验证:空 ArrayList 共享同一个哨兵数组

刚 new 出来的 ArrayList,并没有马上分配任何容量。

和 HashMap 类似,ArrayList 底层用一个私有数组 elementData 存元素,反射读出来看看刚创建时是什么样:

ArrayList<Integer> list = new ArrayList<>();
Object[] arr = (Object[]) elementDataF.get(list);

不只是长度为 0,两个完全独立的空 ArrayList 反射出来的 elementData 引用是同一个对象——JDK 内部有一个静态的空数组常量,所有刚创建、还没 add 过的 ArrayList 都先指向这同一份空数组,真正需要空间时才各自分配自己的数组,不会在创建阶段就浪费内存。

真实验证:扫描出扩容公式,不是查文档抄的

从第一次 add 开始,连续扫描 200 次,记录每次容量变化的瞬间。

size=1 触发扩容 -> capacity = 10
size=11 触发扩容 -> capacity = 15  (从 10 扩到 15, 比例 1.500)
size=16 触发扩容 -> capacity = 22  (从 15 扩到 22, 比例 1.467)
size=23 触发扩容 -> capacity = 33  (从 22 扩到 33, 比例 1.500)
size=34 触发扩容 -> capacity = 49  (从 33 扩到 49, 比例 1.485)
size=50 触发扩容 -> capacity = 73  (从 49 扩到 73, 比例 1.490)
size=74 触发扩容 -> capacity = 109  (从 73 扩到 109, 比例 1.493)
size=110 触发扩容 -> capacity = 163  (从 109 扩到 163, 比例 1.495)
size=164 触发扩容 -> capacity = 244  (从 163 扩到 244, 比例 1.497)

第一次 add 直接从 0 跳到 10(默认初始容量),不是先分配 1 再逐步翻倍。之后每次比例都在 1.5 附近浮动,不是精确的 1.5——因为源码里用的是位运算,不是浮点乘法:

java.util.ArrayList · 扩容核心公式 int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 是整数右移一位,等价于除以 2 再向下取整。旧容量是奇数时(比如 15),右移得到 7 而不是 7.5,新容量是 15+7=22,实际比例只有 1.467,不是精确的 1.5——这也是为什么真实扫描出来的比例会在 1.467~1.5 之间跳,而不是每次都严丝合缝的 1.5。

真实验证:500 万次 add,两种写法差多少

不测容易受机器负载干扰的墙钟时间,直接数底层数组真实被重新分配了几次、搬运了多少个元素引用。

每次扩容,JDK 都要用 Arrays.copyOf 把旧数组的全部内容整体搬进新数组——这一步的成本跟旧数组当时有多大成正比。用反射跟踪 elementData 的引用变化,统计真实发生了几次重新分配、累计搬运了多少个元素引用:

不预设容量: 底层数组真实重新分配了 34 次,累计真实搬运了 12306801 个元素引用
预设容量  : 底层数组真实重新分配了 0 次,累计真实搬运了 0 个元素引用

之所以搬运总量会超过元素总数,是因为同一批元素在不同阶段的扩容里被反复搬过:第一批元素在容量还是 10 的时候就存在了,后面每扩容一次,这批元素都要跟着新加入的元素一起被整体拷贝一遍——越早添加的元素,被反复搬运的次数越多。

分步演示:ArrayList 内部数组是怎么真实一步步长大的

每一行都是真实用反射读取内部数组长度得到的结果。