JDK 1.8 原始碼深度解析：ArrayList 擴容機制、Fast-Fail 迭代器與 SubList 視圖

前言

ArrayList 是 Java 最常用的動態陣列實現。本文基於 **JDK 1.8 (OpenJDK 8u40+)** 原始碼，深度解析其核心機制：擴容策略、快速失效迭代器、SubList 視圖、序列化與執行緒安全。

類別繼承體系

java.lang.Object
  ↓
java.util.AbstractCollection<E>  (實作 toArray, contains, remove 等通用方法)
  ↓
java.util.AbstractList<E>       (實作 List 介面骨架、迭代器、subList、modCount)
  ↓
java.util.ArrayList<E>          (核心：Object[] elementData、動態擴容、隨機存取)

實作介面：`List`、`RandomAccess` (標記支援快速隨機存取)、`Cloneable`、`Serializable`。

核心欄位

transient Object[] elementData;  // 實際儲存陣列，transient 自定序列化
private int size;                // 邏輯大小 (元素個數)
protected transient int modCount = 0; // 修改次數 (繼承自 AbstractList)，用於快速失效

建構子與初始化

// 預設容量 10
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);
    }
}

// 從 Collection 建立
public ArrayList(Collection 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;
    }
}

**延遲初始化**：預設建構子不立即分配陣列，第一次 `add` 時才分配容量 10 (見 `grow`)。

核心擴容機制 (grow / grow / hugeCapacity)

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

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

// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 (保留給 VM header)

擴容關鍵點

• **增長因子 1.5** (舊容量 + 旧容量/2)，平衡記憶體浪費與擴容頻率。
• **最大容量限制** `MAX_ARRAY_SIZE = 0x7fffffff - 8` (約 2GB 元素)，超過拋 `OutOfMemoryError`。
• **Arrays.copyOf** 為 Native 實現，效能極高。
• **ensureCapacityInternal** 在 `add`、`addAll` 前呼叫，確保容量足夠。

快速失效迭代器 (Fail-Fast Iterator)

private class Itr implements Iterator {
    int cursor;       // 下一個要返回的索引
    int lastRet = -1; // 最後返回的索引
    int expectedModCount = modCount; // 快照

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

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size) throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) 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 ex) {
            throw new ConcurrentModificationException();
        }
    }

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

Fail-Fast 原理

1. 建立迭代器時捕獲 `modCount` 快照 (`expectedModCount`)。
2. 每次 `next()`、`remove()` 前比對 `modCount` 是否變更。
3. 若**其他執行緒**或**同執行緒非透過迭代器**修改了 List (如直接 `list.add()`)，`modCount` 遞增，拋出 `ConcurrentModificationException`。
4. 迭代器自身的 `remove()` 會同步更新 `expectedModCount`，合法修改不拋出異常。

**僅為檢測程式錯誤**，不保證多執行緒安全。並發環境請用 `Collections.synchronizedList`、`CopyOnWriteArrayList` 或 `java.util.concurrent` 容器。

SubList 視圖機制

public List subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<>(this, fromIndex, toIndex) :
            new SubList<>(this, fromIndex, toIndex));
}

// 內部類 SubList (非 RandomAccess)
class SubList extends AbstractList {
    private final AbstractList l; // 父列表引用
    private final int offset;        // 起始偏移
    private int size;                // 子列表大小

    SubList(AbstractList list, int fromIndex, int toIndex) {
        this.l = list;
        this.offset = fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = l.modCount; // 共享 modCount
    }

    public E get(int index) {
        rangeCheck(index);
        return l.get(index + offset); // 委派給父列表
    }
    public E set(int index, E element) {
        rangeCheck(index);
        return l.set(index + offset, element);
    }
    // add/remove 同樣委派並同步修改 size、modCount
}

// RandomAccessSubList 僅多實作 RandomAccess 標記介面
class RandomAccessSubList extends SubList implements RandomAccess { ... }

SubList 關鍵特性

• **視圖模式**：不複製資料，持有父列表引用 + 偏移量 + 大小。
• **雙向同步**：對 SubList 的修改 (set/add/remove) 直接反映到父列表，反之亦然。
• **modCount 共享**：父列表修改會導致 SubList 迭代器 Fail-Fast，反之亦然。
• **RandomAccess 保留**：父列表支援隨機存取 → 回傳 `RandomAccessSubList`，保證 `instanceof RandomAccess` 檢查通過 (如 `Collections.sort` 優化)。
• **不可長期持有**：SubList 會強持有父列表，阻礙 GC；用完應立即釋放引用。

序列化實現 (writeObject / readObject)

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    int expectedModCount = modCount;
    s.defaultWriteObject(); // 寫入 size, modCount 等非 transient 欄位
    s.writeInt(size);       // 寫入邏輯大小
    for (int i = 0; i < size; i++) s.writeObject(elementData[i]); // 僅寫入有效元素
    if (modCount != expectedModCount) throw new ConcurrentModificationException();
}

private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    s.readInt(); // 讀取 size (已由 defaultReadObject 讀入，這行實際多餘但保留相容)
    if (size < 0) throw new InvalidObjectException("Invalid size: " + size);
    elementData = (size == 0) ? EMPTY_ELEMENTDATA : new Object[size];
    for (int i = 0; i < size; i++) elementData[i] = s.readObject();
}

**自定序列化** 只儲存有效元素 (size)，忽略陣列尾部空洞，節省空間並確保反序列化後 `elementData.length == size` (緊湊)。

執行緒安全與替代方案

常見效能陷阱與優化

• 頻繁擴容：預估資料量，使用 `new ArrayList<>(estimatedSize)` 或 `ensureCapacity()`。
• 頭部插入/刪除 O(n)：需頻繁頭部操作請改用 `LinkedList` 或 `ArrayDeque`。
• 大量刪除：使用 `removeIf(predicate)` (JDK 8+) 避免手寫迴圈位移錯誤。
• 轉陣列：`toArray(new String[0])` (JDK 11+ 推薦) 或 `toArray(new String[size])` 避免反射開銷。

結語

ArrayList 以 **Object[] + size + modCount** 三大核心欄位實現動態陣列，**1.5 倍擴容**、**Fail-Fast 迭代器**、**SubList 視圖** 是其精華設計。理解原始碼有助於正確選擇容器、避免並發 Bug、優化記憶體與效能。JDK 11+ 引入 `toArray(IntFunction)`、JDK 15+ `trimToSize()` 等細節優化，核心架構穩定可靠，仍是 Java 集合框架基石。

1. 上一篇文章： Spring 整合 ActiveMQ 完整實戰：點對點隊列與發布訂閱模型、監聽器配置、壓力測試
2. 下一篇文章： Java 基礎練習 1：根據輸入奇偶性計算級數和

Java 綜合教學

Eclipse Git 實戰：核心概念差異、常用操作與團隊協作避坑指南

Eclipse Git 實戰：核心概念差異、常用操作與團隊協

JavaWeb 核心：Servlet 開發完整指南（生命週期、映射、配置與最佳實踐）

Servlet 簡介 Sun 定義的動態 Web 資源開發規

Java 面向對象核心（三）：包機制與訪問權限控制實戰

Java 面向對象核心（三）：包機制與訪問權限控制實戰 包是

S2階段易買網項目總結：功能模塊與心路歷程

S2 階段易買網項目總結 指導老師：原玉明 時光飛逝，S2