Java ArrayList 源碼深度解析：擴容、迭代器、線程安全與刪除陷阱

類結構圖譜

實現接口：List、RandomAccess、Cloneable、Serializable。核心字段：

transient Object[] elementData; // 數組緩衝區，transient 避免序列化空槽
private int size;               // 實際元素個數

三種構造函數

public ArrayList() { this(10); }                          // 默認容量 10
public ArrayList(int initialCapacity) { ... }             // 指定初始容量
public ArrayList(Collection<? extends E> c) { ... }       // 集合轉列表

核心方法源碼剖析

1. 擴容機制 grow() (JDK 8)

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

觸發時機：add、addAll 時 size + 1 > capacity。

2. 隨機訪問 get/set - O(1)

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
public E set(int index, E element) {
    rangeCheck(index);
    E old = elementData(index);
    elementData[index] = element;
    return old;
}

3. 尾部添加 add(E e) - 均攤 O(1)

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

4. 指定位置插入 add(index, e) - O(n)

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

System.arraycopy 將 index 及之後元素整體右移一位。

5. 刪除 remove(index) / remove(Object) - O(n)

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

迭代器與 fail-fast 機制

Itr 內部類

private class Itr implements Iterator<E> {
    int cursor;       // 下一個待返回元素索引
    int lastRet = -1; // 上一次返回元素索引
    int expectedModCount = modCount; // 快照

    public boolean hasNext() { return cursor != size; }

    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size) throw new NoSuchElementException();
        cursor = i + 1;
        return elementData(lastRet = i);
    }

    public void remove() {
        if (lastRet < 0) throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount; // 關鍵：同步修改計數
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

為什麼 foreach 刪除會拋 CME？

foreach 編譯為 Iterator，調用 list.remove() 導致 modCount++，但迭代器的 expectedModCount 未更新，下次 next() 觸發檢查拋異常。

正確刪除姿勢

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    it.next(); // 必須先 next()，設置 lastRet
    if (condition) it.remove(); // 迭代器 remove() 會同步 expectedModCount
}

subList 視圖陷阱

List<String> sub = list.subList(1, 3); // 返回 SubList 視圖
sub.set(0, "new"); // 修改視圖 → 原列表同步變化
list.add("x");     // 修改原列表結構 → 視圖失效，後續操作拋 CME

SubList 共享原數組，通過 offset/size 映射區間。結構性修改（增刪）會導致視圖失效。

線程安全性

• 非線程安全：多線程並發增刷會導致數據覆蓋、數組越界、size 不一致。
• 替代方案：Collections.synchronizedList(new ArrayList<>())、CopyOnWriteArrayList（讀多寫少）、手動 synchronized。

總結

ArrayList 以動態數組為核心，隨機訪問極快，增刷需搬移元素。modCount + expectedModCount 實現 fail-fast，保護單線程邏輯正確性。掌握 grow、arraycopy、Itr.remove 三大核心片段，即可應對面試與生產疑難雜癥。