浅谈 ArrayList 的扩容机制

相信大家对 ArrayList 这个类都不陌生吧，ArrayList 底层是基于数组实现的，作为可变长度的数组用于存储任意类型的对象，那么是否有了解过 ArrayList 是如何实现可变长的呢，它的扩容机制是什么呢？

这篇文章将从源码的角度来讲讲 ArrayList 的扩容机制，有兴趣的读者们可以接着往下了解。

ArrayList 的构造函数

在了解 ArrayList 的扩容机制之前，让我们先看看它的构造函数有哪些？

ArrayList 的字段

// 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储数据的数组
transient Object[] elementData;
// 元素个数
private int size;
// 最大数组长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

相信大家对这里的 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为何需要有两个空数组感到疑惑，这两个空数组之间的区别在什么地方呢？对于这个问题等看完后面的源码后就会有答案了。

ArrayList 的构造函数

// 有参构造函数（initialCapacity：指定的初始化集合大小）
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 创建长度为initialCapacity的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 使用空数组（长度为0）
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 无参构造器
public ArrayList() {
    // 使用默认空数组（一开始长度为0，等集合被使用后初始化为10）
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 有参构造器（根据指定的集合构造列表）
public ArrayList(Collection<? extends E> c) {
    // 通过toArray()方法转换为数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 数组长度不为0且数组不是Object类型数据则更换类型为Object的新数组
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 数组长度为0则使用空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

通过上面源码中的三种 ArrayList 的构造函数可以看到根据不同的参数构造列表，同时根据不同的参数导致的列表的数组 elementData 被赋予的值也是不同的。

到这里应该可以看出 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别：

EMPTY_ELEMENTDATA：当构造函数使用指定 initialCapacity 为 0 或指定集合且集合元素为 0 时，会使得 elementData 被赋值为 EMPTY_ELEMENTDATA。这里的空数组表示初始化后的数组长度就是 0 。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：当构造函数使用无参构造函数时，elementData 被赋值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。这里的空数组表示开始长度为 0，当列表被使用时，初始化后的数组长度为 10（DEFAULT_CAPACITY），也就是默认数组大小。（通过后面的 add() 源码能够更好理解）

到这里就可以理解为什么 ArrayList 有两个空数组字段，主要是为了设置默认的数组长度，也就是为了区分当前数组是默认数组（也就是还不确定大小，先设置为空数组，等使用后在设置为默认长度），还是已经确认长度为 0 的空数组。

ArrayList 的扩容机制

ArrayList 的扩容机制核心方法是 grow() 方法，这里从 add() 方法进入详细看看 ArrayList 的扩容过程。

扩容过程源码分析

添加元素方法：add()

public boolean add(E e) {
    // size + 1 确保添加后长度足够，进入方法判断是否需要扩容
    ensureCapacityInternal(size + 1);
    // 添加元素
    elementData[size++] = e;
    return true;
}

判断是否是默认长度方法：ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {
    // 数组为默认数组时，minCapacity只会在10之上。
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 进入方法判断是否需要扩容
    ensureExplicitCapacity(minCapacity);
}

判断是否需要扩容方法：ensureExplicitCapacity()

private void ensureExplicitCapacity(int minCapacity) {
    // 用于记录修改次数的计数器，保证多线程下抛出ConcurrentModificationException异常
    modCount++;
    // minCapacity最小需求容量小于当前数组长度时则需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

扩容方法：grow()

private void grow(int minCapacity) {
    // 旧容量等于数组长度
    int oldCapacity = elementData.length;
    // 新容量等于数组长度 + 0.5 * 数组长度 也就是 1.5 数组长度
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 新容量还是小于最小需求容量时，直接将新容量赋值为最小需求容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
        
    // 新容量大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）调用hugeCapacity()扩容到Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
        
    // 数组拷贝，将数据迁移到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容过程梳理

下面以使用无参构造函数的列表为例，分别讲讲第1个元素插入和第11个元素插入的扩容过程：

添加第1个元素的过程：

ArrayList扩容过程.png

调用 add(e) 方法添加元素，此时的 size=0。
调用 ensureCapacityInternal(1) 方法判断是否是默认长度数组，此时该方法的传参是 size + 1 代表目前列表需要的最小容量。进入该方法后，因为使用的是无参构造器，故这里的数组是默认长度数组，所以 minCapacity 最小容量被置为 10，也就是列表默认长度 DEFAULT_CAPACITY。
调用 ensureExplicitCapacity(10) 方法判断是否需要扩容，此时由于 minCapacity=10 大于数组长度 elementData.length=0 所以需要扩容。
调用 grow(10) 方法进行扩容，此时旧数组容量为 oldCapacity=0，新数组容量为 newCapacity=0，而最小容量 minCapacity=10，因为新数组容量小于最小容量，故将新数组容量重新赋值为 newCapacity=minCapacity=10，然后进行数组拷贝，到此完成扩容操作。

添加第11个元素的过程：

ArrayList扩容过程2.png

调用 add(e10) 方法添加元素，此时的 size=10。
调用 ensureCapacityInternal(11) 方法判断是否是默认长度数组，此时该方法的传参是 size + 1 代表目前列表需要的最小容量。进入该方法后，由于已经超出了默认长度 10，所以这里 minCapacity 设置为 11。
调用 ensureExplicitCapacity(11) 方法判断是否需要扩容，此时由于 minCapacity=11 大于数组长度 elementData.length=10 所以需要扩容。
调用 grow(11) 方法进行扩容，此时旧数组容量为 oldCapacity=10，新数组容量为 newCapacity=15，而最小容量 minCapacity=11，因为新数组容量大于最小容量，故将新数组容量依旧为15，然后进行数组拷贝，到此完成扩容操作，新数组的长度扩容到了 15，并将旧数组的元素迁移到新数组中。

以上就是扩容的全过程，扩容公式为 $n e wC a p a c i t y = o l d C a p a c i t y + (o l d C a p a c i t y >> 1)$ ，也就是新容量取值为旧容量的 1.5 倍。

补充：数组拷贝 System.arraycopy() 方法

扩容后的数据迁移调用的是 Arrays.copyOf() 方法底层调用的是 System.arraycopy()，这里简单介绍一下这个常用的方法。

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

该方法的参数如下：

src：源数组
srcPos：源数组拷贝的起始位置
dest：目标数组
destPos：目标数组拷贝的起始位置
length：需要拷贝的数组元素的数量

这里作为补充知识简单了解一下即可。

总要有总结

以上就是 ArrayList 的扩容机制的内容了，主要总结如下：

ArrayList 是基于动态数组实现的，可以扩容或缩短（缩短可以手动调用 trimToSize() 方法，ArrayList在元素小于一半长度时会自动缩短长度，这里不作过多说明）数组的大小从而实现可变长的数组。
ArrayList 中声明了 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 两个字段，虽然都是空数组，但是两者之间有着不同的作用。
ArrayList 的扩容机制采用的是新数组容量扩容为旧数组容量的 1.5 倍。

补充： ArrayList 提供了 ensureCapacity(int minCapacity) 用于实现手动扩容到指定的容量，这样在需要添加大量数据时可以不必重复进行扩容操作，提高性能。

到这里就是本篇的所有内容了，ArrayList 类中还有许多有意思的方法，有兴趣的读者们可以自行去查看它们的源码。

感谢观看！！！