ArrayList 扩容规则-码谱记录

Java 中，ArrayList 是 List 最经典的实现，由于 ArrayList 底层是数组，掌握其扩容机制十分必要。

下面的讨论，基于 JAVA8，不同的JDK版本，某些规则会有差异。

构造器容量

我们一般在一定一个 ArrayList 时，常常采用其无参构造函数：

List<String> list = new ArrayList<>();

对于无参构器，ArrayList 默认初始容量为 0 。

如何证明这个想法？

下面是截取自 ArrayList 的部分源码，默认 elementData 给的是个空的数组，没有长度。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

源码里注释我也复制过来了，可以看到这个注释和实际情况不太相符。在之前的版本，JAVA 给的初始容量为 10，当前版本的实现已经修改了，但是注释忘记改了。如果只看注释就认定初始容量为 10，就掉坑里了。

首次添加元素

为什么一般我们都认为，ArrayList 初始容量为 10 ？

在第一次调用 add() 方法以后，有下面的一段代码：

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
}

也就是在第一次添加元素时，会将数组容量扩容为 10.

可以简单地理解，没有元素时，ArrayList 容量为 0，有一个元素时，ArrayList 容量为 10.

首次扩容

当第一个元素被添加进 ArrayList 后，数组长度为 10。当添加第 11 个元素时，就会发生扩容。

扩容为原来的 1.5 倍。因此，第一次扩容后容量就变成了 15.

这个 1.5 倍并不是整数，按照数学计算，某个数的1.5倍可能是小数，那改怎么处理？

假设到第三次扩容，原容量为 15 * 1.5 = 22.5 ，看起来有点奇怪。

实际上，程序内部并不是这样计算的。

在二分查找解决溢出问题的思路中，曾经提到过位运算。

对于正整数，除以二相当于无符号右移一位。

在 JDK 中，1.5 倍实际上是原始容量 + 原始容量右移一位。

int newCapacity = oldCapacity + (oldCapacity >> 1);

这样，在第三次扩容时，扩容后容量为 15 + (15 >> 1) = 22 。

这就不存在小数问题了，并且位操作对计算机来说比其他运算要更快。

基础扩容规律

对于通过无参构造函数初始化的 ArrayList，并且元素一个一个添加时，前 20 次扩容规律如下：

批量添加元素

ArrayList 除了一个一个添加元素的 add() 方法，还有一个 addAll() ，可以批量添加元素。

当我批量添加多个元素时：

List<String> list = new ArrayList<>();
list.addAll(Arrays.asList("a", "b", "c"));

如果还没有到初始扩容点，其容量就是 10.

List<String> list = new ArrayList<>();
list.addAll(Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k"));

如果已经超过了 10，那此时的容量就是添加集合的长度。

为什么需要这样设计？

当添加很多元素时，如果按照原扩容机制来处理，就可能出现需要多次扩容。比如添加一个包含30个元素的集合到 ArrayList 中，可能先扩容为 10，再扩容为 15，再扩容为 22，而扩容也是有资源消耗的。

因此，一次性扩容到所添加集合的长度，就只需要扩容一次，从 0 到集合长度。而之后，每次扩容都是该长度的 1.5 倍。

下面这个场景A，混合了先一个一个添加元素，再批量加元素：

List<String> list = new ArrayList<>();
for(int i = 0; i< 10; i++){
    list.add("a");
}
list.addAll(Arrays.asList("a", "b", "c"));

首先，一个一个添加10个元素，容量为 10 ，然后批量添加了3 个元素，有点麻烦，到底应该是 13 还是 15？

再来一个场景B，一个一个添加10个元素，容量为 10 ，然后批量添加了 7 个元素，容量肯定不能是15了，那应该是 17 ？

List<String> list = new ArrayList<>();
for(int i = 0; i< 10; i++){
    list.add("a");
}
list.addAll(Arrays.asList("a", "b", "c", "d", "e", "f", "g"));

为了解决这个问题，JDK 采用了下面的方案：

容量 = Math.max(原容量扩容，原容量+批量数组容量)

对于场景A：容量 = Math.max(101.5, 10 + 3)，结果为 15.
对于场景B：容量 = Math.max(101.5, 10 + 7)，结果为 17.

有参构造

ArrayList() 还有几个有参数的构造函数，它们的扩容机制比较简单。

ArrayList(int initialCapacity)

如果传入了容量，初始容量就设置为了传入的容量值。

ArrayList(Collection<? extends E> c)

如果给的是集合，容量就是传入的集合的元素数量。

总结

ArrayList() 使用的数组长度为 0
add() 首次调用会扩容为 10，之后为上一次的 1.5 倍
ArrayList(int initialCapacity) 容量为传入的 initialCapacity
ArrayList(Collection<? extends E> c) 容量为传入集合的元素个数
addAll() 比较复杂，无元素时，扩容为 Math.max(10, 添加的元素个数)，有元素时，Math.max(原容量 * 1.5，原容量 + 添加的元素个数)

Java List

ArrayList 扩容规则