Java ArrayList 源碼深度解析：動態數組核心實現與性能優化

ArrayList 概述

ArrayList 是 Java 集合框架中最常用的 List 實現，底層基於動態數組，支持自動擴容。它不是線程安全的，僅適用於單線程環境；多線程場景可使用 Collections.synchronizedList 或 CopyOnWriteArrayList。ArrayList 實現了 Serializable、RandomAccess、Cloneable 接口，支持序列化、快速隨機訪問和克隆。

核心字段與構造函數

關鍵字段

private transient Object[] elementData; // 存儲數據的數組
private int size;                       // 實際元素數量
private static final int DEFAULT_CAPACITY = 10; // 默認容量

三種構造函數

• ArrayList()：無參構造，初始容量 10（實際延遲到首次 add 時分配）
• ArrayList(int initialCapacity)：指定初始容量
• ArrayList(Collection c)：從集合創建，調用 toArray()

核心方法深度解析

擴容機制：ensureCapacity 與 grow

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3) / 2 + 1; // 1.5倍 + 1
        if (newCapacity < minCapacity) newCapacity = minCapacity;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

關鍵點：

1. 增長因子 1.5（舊版本），JDK 8+ 為 oldCapacity + (oldCapacity >> 1)
2. 使用 Arrays.copyOf 實現數組複製，底層調用 System.arraycopy
3. 每次擴容都涉及數組創建與元素複製，頻繁擴容性能損耗大

添加元素：add 方法

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

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

• 尾部添加：攤還 O(1)
• 指定位置插入：需移動後續元素，O(n)

數組複製工具：Arrays.copyOf 與 System.arraycopy

// Arrays.copyOf 核心邏輯
public static  T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static  T[] copyOf(U[] original, int newLength, Class newType) {
    T[] copy = ((Object)newType == (Object)Object[].class) 
        ? (T[]) new Object[newLength] 
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

System.arraycopy 是 native 方法，最終調用 C 的 memmove，效率極高，支持同一數組內重疊複製。

toArray 方法詳解

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

public  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) a[size] = null;
    return a;
}

最佳實踐：list.toArray(new String[0]) 效率最高，避免反射創建數組開銷。

查找與空值處理

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i] == null) return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i])) return i;
    }
    return -1;
}

分離 null 與非 null 比較，避免 NPE，允許存儲 null 元素。

性能特徵總結

最佳實踐建議

1. 預估大小：構造時指定 initialCapacity，避免頻繁擴容
2. 批量操作：優先用 addAll、removeAll 而非循環單個操作
3. 轉數組：使用 toArray(new T[0]) 零長度數組模式
4. 多線程：改用 CopyOnWriteArrayList（讀多寫少）或 Collections.synchronizedList
5. 頻繁插刪：考慮 LinkedList，但注意其隨機訪問 O(n) 的劣勢

總結

ArrayList 以動態數組為基礎，提供高效隨機訪問，擴容機制靈活，是單線程環境下 List 的首選。理解其擴容策略、數組複製原理、toArray 最佳實踐，對編寫高性能 Java 代碼至關重要。