ArrayList 扩容机制分析

注意：文章内容基于 JDK 8，其他版本的 JDK 可能会存在差异。

构造函数

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

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;

默认无参构造函数，初始化容量为 10，初始化为空数组，当添加第一个元素时，数组的容量才变成 10。

带容量参数的构造函数，用户可以在初始化 ArrayList 对象时，指定初始化容量大小，如果传入的参数大于0，则创建指定大小的数组，如果传入的参数等于 0，则初始化为空数组，如果传入的参数小于 0，则抛出异常。

add 函数

public boolean add(E e) {
    // 确保数组容量符合要求
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是默认容量，则返回默认容量和最小容量的较大者
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 判断是否需要对数组进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow 函数

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
// 扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

新的容量为原来容量的 1.5 倍左右，如果新的容量小于最小需要的容量，则新的容量为最小需要的容量，如果新的容量大于MAX_ARRAY_SIZE，则调用hugeCapacity函数。

hugeCapacity 函数

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

总结

ArrayList 的底层是数组，相当于动态数组，和 Java 中的数组相比，它的容量可以动态增长，每次扩容时新的容量为原来容量的 1.5 倍左右。