Java 1.8 ArrayList 源码分析

我们声明一个初始容量为1的ArrayList。看看在add时候到底发生了什么。

public class Main {
    public static void main(String[] args) {
        final ArrayList<String> objects = new ArrayList<>(1);
        objects.add("A");
        objects.add("B");
        objects.add("C");
    }
}

当声明的容量小于10时的情况

执行第一个语句objects.add("A")，此时size是0，执行ensureCapacityInternal(1)。

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

calculateCapacity(elementData,1)，此时数组为空，所以return 10。调用ensureExplicitCapacity(10)。

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

10 > 0 调用grow(10)

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

newCapacity - minCapacity = -10 < 0 ,所以newCapacity=10。elementData = Arrays.copyOf(elementData,10); elementData容量变为了10。

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);
}

无需扩容的情况

接下来执行objects.add("B")。此时size是1，执行ensureCapacityInternal(2)。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

calculateCapacity(elementData,2)，此时数组不为空，所以return 2。调用ensureExplicitCapacity(2)。

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

2-10 < 0 所以不需要grow，直接执行上面的elementData[size++] = e。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

正常扩容情况

1.5倍扩容，将原来的数组整个拷贝过去。

int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity)

总结

• 当我们new一个ArrayList的时候，初始容量为0，内部表示为一个空数组。在一次add后，容量为扩充为10。
• 我们可以自定义初始容量的大小，值得注意的是，如果定义的容量小于10，在第一次add后，容量会扩充为10。
• 容量不够时，按照1.5倍原容量大小扩容，复制原容量数组的所有元素到新容量的数组去。所以说扩容是一个比较昂贵的操作。我们可以根据需求设置初始容量。