Java 集合框架深度解析 (上)：ArrayList 核心原理、擴容機制、迭代器模式與 RandomAccess 接口

ArrayList 核心地位與設計哲學

ArrayList 是 Java 集合框架中使用頻率最高的動態數組實現，底層封裝 Object[] elementData，提供 O(1) 隨機訪問、摊還 O(1) 尾部插入、O(n) 中間插入刪除 的性能特徵。實現 List、RandomAccess、Cloneable、Serializable 接口，是構建高性能業務邏輯的基石。

內部結構與關鍵字段

transient Object[] elementData; // 存儲元素的數組，transient 避免默認序列化
private int size;               // 實際元素個數
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient 配合自定義 writeObject/readObject 實現高效序列化（僅序列化 size 範圍內元素）。

構造器與初始化策略

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

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0 && elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

建議：預估數據量時使用帶容量構造器，避免多次擴容拷貝。

擴容機制深度解析：grow() 與 1.5 倍策略

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

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 倍？

• 2 倍增長 (如 C++ vector) 會導致記憶體碎片，無法復用剛釋放的舊數組空間 (Buddy Allocation 機制)。
• 1.5 倍使得新數組大小約為舊數組 1.5 倍，舊數組釋放後的空間可被後續分配復用，減少 GC 壓力。

插入與刪除：System.arraycopy 批量移動

// 指定位置插入
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 E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // 幫助 GC
    return oldValue;
}

System.arraycopy 為 Native 方法，極快。但中間操作仍需移動後續元素，故 O(n)。

迭代器模式：快速失效與 modCount 機制

Iterator 實現 (內部類 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[] ed = elementData;
        if (i >= ed.length) throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) ed[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();
    }
}

foreach 陷阱與正確刪除姿勢

// ❌ 錯誤：foreach 中直接 list.remove() → CME
for (String s : list) { if (s.equals("x")) list.remove(s); }

// ✅ 正確：使用迭代器 remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) { if (it.next().equals("x")) it.remove(); }

// ✅ Java 8+ Stream 過濾 (生成新列表)
list = list.stream().filter(s -> !s.equals("x")).collect(Collectors.toList());

// ✅ Java 8+ removeIf (內部使用迭代器，線程不安全但單線程安全)
list.removeIf(s -> s.equals("x"));

ListIterator：雙向遍歷與索引操作

public ListIterator<E> listIterator() { return new ListItr(0); }
public ListIterator<E> listIterator(int index) { return new ListItr(index); }

// ListItr 繼承 Itr，新增：
// hasPrevious(), previous(), nextIndex(), previousIndex(), set(E), add(E)
// 支持逆序遍歷：
ListIterator<String> lit = list.listIterator(list.size());
while (lit.hasPrevious()) System.out.println(lit.previous());

RandomAccess 標記接口：算法優化的關鍵

public interface RandomAccess { } // 無方法，純標記

ArrayList 實現該接口，表示支持高效隨機訪問 (基於數組下標)。Collections.binarySearch、Collections.sort 等算法會檢查 list instanceof RandomAccess：

if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
    indexedBinarySearch(list, key); // 下標直接訪問 O(log n)
else
    iteratorBinarySearch(list, key); // 迭代器順序訪問 O(n log n) 退化

LinkedList 未實現 RandomAccess，故二分查找自動降級為迭代器版本。

序列化與 toArray 互轉

// 1. toArray() 返回 Object[]
Object[] arr1 = list.toArray(); // Arrays.copyOf(elementData, size)

// 2. toArray(T[] a) 類型安全
String[] arr2 = list.toArray(new String[0]); // 推薦：JVM 優化零長度數組
String[] arr3 = list.toArray(new String[list.size()]); // 精確預分配

// 3. Arrays.asList 陷阱：返回固定大小列表，不支持 add/remove
List<String> fixed = Arrays.asList("a", "b"); // 實為 Arrays$ArrayList
// fixed.add("c"); // UnsupportedOperationException

// 正確轉換為可變 ArrayList
List<String> mutable = new ArrayList<>(Arrays.asList("a", "b"));

容量控制與性能調優

• ensureCapacity(minCapacity)：預分配，批量添加前調用減少擴容次數。
• trimToSize()：縮容至 size，釋放多餘記憶體，適合長期存活、不再變動的列表。

ArrayList 性能特徵總結表

總結

ArrayList 以動態數組為核心，隨機訪問快、尾部添加快、中間操作慢。掌握 grow() 1.5 倍擴容、modCount 快速失效、RandomAccess 算法優化、toArray 類型安全轉換等細節，能寫出高性能、無 Bug 的集合操作代碼。下一篇將解析 LinkedList 雙向鏈表機制與對比選型指南。