您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java 集合源碼深度解析（二）：ArrayList 核心機制與擴容策略演進

編輯：Java 綜合教學

Java 集合源碼深度解析（二）：ArrayList 核心機制與擴容策略演進

ArrayList 是 Java 集合框架中最常用的動態陣列實現，基於 Object[] 底層儲存，支援隨機存取、自動擴容、序列化與克隆。本文基於 JDK 1.6/1.7/1.8 源碼，系統剖析其構造、擴容、增刪查、序列化與效能優化細節。

一、類別定義與核心欄位

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, Serializable {
    private static final long serialVersionUID = 8683452581122892189L;
    transient Object[] elementData; // transient：序列化時由 writeObject 自行處理
    private int size;               // 實際元素個數
}

transient 避免預設序列化機制複製整個陣列（含尾部空間），由 writeObject 僅序列化 size 與有效元素，節省空間。
實作 RandomAccess 標記介面，告知演算法（如 Collections.sort）支援高效隨機存取。

二、三種構造函數

構造函數	行為	適用場景
`ArrayList(int initialCapacity)`	指定初始容量，`<0` 拋異常	預估資料量大致可知，避免多次擴容
`ArrayList()`	預設容量 10（JDK 1.6/7），JDK 1.8 延遲至首次 `add` 才分配	通用場景
`ArrayList(Collection<? extends E> c)`	複製集合元素，確保底層為 `Object[]`	集合轉換、防禦性複製

三、自動擴容機制：核心 `ensureCapacity` / `grow`

JDK 1.6/1.7 策略

// 1.6
int newCapacity = (oldCapacity * 3) / 2 + 1;
// 1.7 優化：位移運算替代乘除
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
// 並引入 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 防溢位

JDK 1.8 進一步優化

空陣列 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 延遲分配，首次 add 才分配默認 10 容量。
grow(int minCapacity) 統一擴容邏輯，呼叫 Arrays.copyOf。
新增 hugeCapacity 處理超大陣列分配。

效能啟示：位移運算（>> 1）比乘除快；預估資料量時指定 initialCapacity 可避免多次複製。

四、核心操作源碼剖析

1. 新增元素

add(E e)：檢查容量 → elementData[size++] = e，均攤 O(1)。
add(int index, E element)：System.arraycopy 向右位移尾部元素 → 插入，O(n)。
addAll：批次複製，同樣依賴 System.arraycopy。

2. 刪除元素

remove(int index)：System.arraycopy 向左位移後續元素 → elementData[--size] = null 釋放引用助 GC，O(n)。
remove(Object o)：遍歷比對（null 用 ==，非 null 用 equals） → 呼叫 fastRemove。
clear()：將所有元素置 null → size = 0。

3. 查詢與遍歷

get(index)：RangeCheck → 直接陣列下標存取，O(1)。
indexOf/lastIndexOf：線性遍歷比對，O(n)。
contains：委派 indexOf。

五、`System.arraycopy` 與 `Arrays.copyOf` 底層優勢

System.arraycopy 是 native 方法，最終呼叫 C memmove，支援重疊區域複製，效率遠高於 Java 迴圈。
Arrays.copyOf 內部同樣呼叫 System.arraycopy，並針對 Object[] 做快速路徑優化。

六、序列化自定義：`writeObject` / `readObject`

private void writeObject(ObjectOutputStream s) throws IOException {
    int expectedModCount = modCount;
    s.defaultWriteObject();           // 寫入 non-transient 欄位
    s.writeInt(elementData.length);   // 寫入陣列長度（容量）
    for (int i = 0; i < size; i++)    // 僅寫入有效元素
        s.writeObject(elementData[i]);
    if (modCount != expectedModCount) throw new ConcurrentModificationException();
}

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    int arrayLength = s.readInt();
    Object[] a = elementData = new Object[arrayLength];
    for (int i = 0; i < size; i++)
        a[i] = s.readObject();
}

設計精妙：不序列化尾部空槽，反序列化時精確還原容量與元素，兼容跨版本演進。

七、`modCount` 與 Fail-Fast 機制

modCount 記錄結構性修改次數（增、刪、清空）。
迭代器建立時捕獲 expectedModCount，遍歷過程中若不一致拋 ConcurrentModificationException。
非執行緒安全，多執行緒環境請用 Collections.synchronizedList 或 CopyOnWriteArrayList。

八、JDK 版本演進總結表

特性	JDK 1.6	JDK 1.7	JDK 1.8
預設初始容量	10	10	延遲分配（首次 add 才給 10）
擴容公式	`old*3/2+1`	`old + (old>>1)`	同 1.7，含溢位保護
空陣列共享	無	無	`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`
序列化相容	基礎	增強	完善