Java 集合框架深度解析：Iterator 迭代器模式與 ArrayList 實現原理

Java 集合框架深度解析：Iterator 迭代器模式與 ArrayList 實現原理

迭代器模式是遍歷集合的標準化方式，將遍歷邏輯從集合內部結構中抽離，避免客戶端代碼與集合實現緊耦合。本文從使用方式切入，深入分析 ArrayList 的 Iterator 實現原理與快速失效機制。

一、為什麼需要 Iterator？

無迭代器時，遍歷方式強依賴內部結構：

• 陣列：for (int i=0; i<arr.length; i++) 使用下標
• ArrayList：for (int i=0; i<list.size(); i++) list.get(i)

問題：客戶端必須知道具體集合類型，無法復用遍歷邏輯，整合不同集合極其麻煩。

二、Iterator 介面定義

public interface Iterator<E> {
    boolean hasNext();  // 是否有下一個元素
    E next();           // 返回下一個元素並移動游標
    void remove();      // 移除剛遍歷的元素（可選操作）
}

相比舊 Enumeration：方法命名更清晰、支援遍歷時安全移除元素。

三、標準使用模式

// 推薦：for 迴圈形式，變數作用域最小
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    String s = it.next();
    // 處理 s
}

// 等價 while 寫法
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
}

四、ArrayList Iterator 實現原理 (JDK 8 參考)

內部類 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();
        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();
    }
}

關鍵機制解析

1. 游標設計：cursor 指向下一個元素，lastRet 記錄上一個返回位置，初始 -1
2. 快速失效：modCount 記錄結構性修改次數（add/remove），Iterator 建立時快照 expectedModCount。遍歷中若 modCount != expectedModCount 拋出 ConcurrentModificationException
3. 安全移除：Iterator.remove() 內部呼叫 ArrayList.remove() 並同步更新 expectedModCount，這是遍歷中唯一合法的修改方式

五、最佳實踐

• 遍歷過程中絕不直接呼叫 list.add()/list.remove()，必須用 it.remove()
• 捕獲 ConcurrentModificationException 後不要空 catch，應檢查程式邏輯錯誤
• 多執行緒環境下，ArrayList 非執行緒安全，考慮 CopyOnWriteArrayList 或同步包裝
• 僅需讀取時，優先使用增強 for 迴圈（for (E e : list)），編譯器自動轉為 Iterator