Java ArrayList 源碼深度解析 (一)：核心欄位、建構子與擴容機制

ArrayList 核心特徵

• 底層：**動態陣列** (`Object[] elementData`)
• 非線程安全 (非同步)
• 實作 `List`、`RandomAccess`、`Cloneable`、`Serializable`
• 預設初始容量：10

核心欄位

transient Object[] elementData; // transient: 不序列化陣列本身，由 writeObject 手動處理
int size;                         // 實際元素數量
int modCount;                     // 修改次數 (fail-fast 機制用)

三種建構子

1. 無參建構子 (最常用)

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 共享空陣列實例
}

**延遲初始化**：真正添加第一個元素時才分配大小 10 的陣列。

2. 指定初始容量

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

**最佳實務**：預估資料量，指定初始容量避免多次擴容複製。

3. 集合建構子

public ArrayList(Collection c) {
    elementData = c.toArray();
    size = elementData.length;
    // 防護性複製：確保底層陣列為 Object[]
    if (elementData.getClass() != Object[].class) {
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
}

擴容機制核心：grow() / ensureCapacity()

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

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 至少 10
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity > elementData.length) {
        grow(minCapacity); // 觸發擴容
    }
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍擴容
    if (newCapacity < minCapacity) newCapacity = minCapacity;
    if (newCapacity > MAX_ARRAY_SIZE) newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

擴容關鍵點總結

核心操作源碼解析

get(int index) - O(1) 隨機存取

public E get(int index) {
    rangeCheck(index);              // 邊界檢查
    return elementData(index);      // 直接陣列存取
}

private void rangeCheck(int index) {
    if (index >= size) throw new IndexOutOfBoundsException(...);
}

add(int index, E element) - 插入需位移

public void add(int index, E element) {
    rangeCheckForAdd(index);                    // 允許 index == size (尾部插入)
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index,        // 來源陣列、來源起始
                       elementData, index + 1,  // 目標陣列、目標起始
                       size - index);           // 複製長度
    elementData[index] = element;
    size++;
}

remove(int index) - 刪除需位移

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

效能特徵總結

• 查詢：O(1) 極快 (隨機存取)
• 尾部新增：均攤 O(1)
• 中間插入/刪除：O(n) 需大量位移
• 記憶體：較 LinkedList 緊湊 (無節點物件開銷)

線程安全替代方案

// 同步包裝器 (效能較差)
List syncList = Collections.synchronizedList(new ArrayList<>());

// 並發專用 (JDK 5+ 推薦)
List concurrentList = new CopyOnWriteArrayList<>(); // 讀多寫少
// 或
List concurrentList = Collections.synchronizedList(new ArrayList<>()); // 一般同步

下一章預告

下篇將深入解析：`iterator()` 實作與 fail-fast 機制、`subList` 視圖陷阱、`toArray` 陷阱、`removeIf`、`replaceAll` 等 JDK 8+ 新方法源碼。