Java ArrayList 源碼深度解析：動態擴容、System.arraycopy 核心機制與實現細節

Java ArrayList 源碼深度解析：動態擴容、System.arraycopy 核心機制與實現細節

ArrayList 底層是 Object[] 動態數組，本文基於 JDK 8 源碼，剖析構造器、擴容策略、核心增刪查遞、System.arraycopy 與 Arrays.copyOf 內部原理、modCount 快速失效機制。

核心字段

transient Object[] elementData; // 非 private，ArrayListSpliterator 直接訪問
private int size;               // 邏輯大小
// private int modCount;        // 結構性修改次數，迭代器快速失效用

三種構造器

// 默認容量 10
public ArrayList() { this(10); }

// 指定初始容量
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) elementData = new Object[initialCapacity];
    else if (initialCapacity == 0) elementData = EMPTY_ELEMENTDATA;
    else throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}

// 集合轉換
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else elementData = EMPTY_ELEMENTDATA;
}

擴容核心：grow() / ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0) grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
    if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 增長因子 1.5（old + old>>1），平衡空間與拷貝開銷。
• Arrays.copyOf 內部調用 System.arraycopy，原生 C 實現，極快。
• MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，防止 VM 分配超大數組 OOM。

關鍵操作源碼精讀

添加元素

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

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

批量添加

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

刪除元素

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E old = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // 釋放引用助 GC
    return old;
}

public boolean remove(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i] == null) { fastRemove(i); return true; }
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i])) { fastRemove(i); return true; }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;
}

範圍刪除 / 修剪容量

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
    int newSize = size - (toIndex - fromIndex);
    while (size != newSize) elementData[--size] = null;
}

public void trimToSize() {
    modCount++;
    if (size < elementData.length)
        elementData = Arrays.copyOf(elementData, size);
}

轉數組

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

public <T> T[] toArray(T[] a) {
    if (a.length < size)
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        for (int i = size; i < a.length; i++) a[i] = null;
    return a;
}

System.arraycopy vs Arrays.copyOf 核心差異

modCount 快速失效機制

所有結構性修改（add、remove、clear）均 modCount++。迭代器構建時記錄 expectedModCount = modCount，遍歷前檢查不一致即拋 ConcurrentModificationException，防止非併發下的邏輯錯誤。

總結

ArrayList 以「動態數組 + 1.5 倍擴容 + System.arraycopy 批量移動」實現高性能隨機訪問與尾部插入，頭部/中間插刪為 O(n)。理解其擴容與拷貝細節，有助於預估容量（new ArrayList(n)）避免頻繁擴容，選擇合適集合類型（頻繁頭尾操作改 ArrayDeque）。