ArrayList的扩容机制 - 李清灿的开发笔记

前提：基于1.8的源码进行分析。

在ArrayList中，是使用一个Object[]数组elementData进行数据的存储的，而一个ArrayList的容量就是这个数组elementData的长度length。

观察ArrayList的2个构造函数源码：

折叠复制代码

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);
    }
}

无参的构造函数，elementData直接为一个默认的特殊的空数组（相当于一个特殊标记，后续扩容代码中发现这个标记会直接扩容为默认的容量10）
指定初始容量的构造函数，elementData会直接实例化一个指定容量的数组；如果初始容量为0，则elementData赋值为一个默认的空数组。

当我们往ArrayList中添加数据时，会通过一个ensureCapacityInternal函数来保证容量的可用性，也就是说ArrayList是先扩容（如果需要的话）后插入数据的。

折叠复制代码

/**
 * 确保最小容量，如不够则进行扩容
 * @param minCapacity
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
 * 计算得出需要保证的容量
 * 这里正常情况下都是直接返回入参minCapacity的值，只有当elementData的值为上述提到的无参构造函数中设置的特殊数组时，才会返回默认的容量
 * @param elementData
 * @param minCapacity
 * @return
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
/**
 * 这里会进行一个判断，只有当前elementData数组小于所需的容量时，才会调用grow进行扩容
 * @param minCapacity
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

从上方的源码以及注释来看，扩容的代码主要是在grow这个函数中：

折叠复制代码

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

函数的逻辑其实也不复杂，主要是对elementData的长度进行一个1.5倍的扩容，这里使用了一个位运算来实现，效率比用乘号来的高效。

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

原理是：oldCapacity右移1位，因为是二进制，所以右移1位相当于除以2，再加上原来的oldCapacity，所以得到新的newCapacity相当于是oldCapacity的1.5倍（当然这里面有一个向下取整的精度问题，忽略不计）

grow函数在通过位运算计算出新数组的长度之后，因为oldCapacity可能为0，以及1.5倍向下取整的问题，得到的新容量newCapacity可能还是会比所需容量小，这种情况下新数组容量会直接等于所需容量。额外在考虑一下MAX_ARRAY_SIZE的情况，最终可以得到一个扩容后的新容量。

获取到扩容之后的新容量值，接下来就是直接创建一个新数组并进行一个数据的拷贝，ArrayList的扩容就结束了。