## 深入分析 Java 中的 `ArrayList` 源碼

`ArrayList` 是 Java 集合框架中的一個重要類，它基于數組實現，提供了動態數組的功能。`ArrayList` 是一個非常常用的集合類，因為它在隨機訪問和遍歷方面性能優越。本文將詳細分析 `ArrayList` 的源碼，包括其數據結構、構造方法、核心操作、自動擴容機制等。

### 1. `ArrayList` 的基本數據結構

`ArrayList` 是一個動態數組，它的底層是一個 `Object` 類型的數組。在 `ArrayList` 的實現中，主要使用以下幾個關鍵字段：

```java
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
? ? private static final long serialVersionUID = 8683452581122892189L;

? ? // 默認初始容量
? ? private static final int DEFAULT_CAPACITY = 10;

? ? // 空數組實例，當初始容量為0時使用
? ? private static final Object[] EMPTY_ELEMENTDATA = {};

? ? // 默認空數組實例，當使用默認構造函數時使用
? ? private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

? ? // 存儲元素的數組
? ? transient Object[] elementData;

? ? // 元素數量
? ? private int size;
}
```

- `elementData`：這是實際存儲元素的數組。
- `size`：這是當前 `ArrayList` 中包含的元素數量。
- `DEFAULT_CAPACITY`：這是默認的初始容量。
- `EMPTY_ELEMENTDATA` 和 `DEFAULTCAPACITY_EMPTY_ELEMENTDATA`：分別是用于初始化時的空數組。

### 2. 構造方法

`ArrayList` 提供了多個構造方法：

#### 2.1 默認構造方法

```java
public ArrayList() {
? ? this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```

默認構造方法將 `elementData` 初始化為 `DEFAULTCAPACITY_EMPTY_ELEMENTDATA`，即一個空數組。當第一次添加元素時，數組將擴展到默認初始容量。

#### 2.2 指定初始容量的構造方法

```java
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);
? ? }
}
```

此構造方法允許用戶指定 `ArrayList` 的初始容量。如果初始容量大于 0，則創建一個相應大小的數組；如果初始容量為 0，則使用空數組；如果初始容量為負數，則拋出 `IllegalArgumentException`。

#### 2.3 從另一個集合創建 `ArrayList`

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

此構造方法從另一個集合創建 `ArrayList`，并將集合中的所有元素添加到 `ArrayList` 中。

### 3. 核心操作方法

#### 3.1 添加元素

添加元素的方法主要有 `add(E e)` 和 `add(int index, E element)`：

```java
public boolean add(E e) {
? ? ensureCapacityInternal(size + 1); ?// 擴容檢查
? ? elementData[size++] = e;
? ? return true;
}

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

- `add(E e)`：在數組末尾添加元素，需要先檢查容量是否足夠，如果不足，則進行擴容。
- `add(int index, E element)`：在指定位置插入元素，需要先檢查索引的有效性，然后將指定位置后的元素向后移動，再插入新元素。

#### 3.2 確保容量

`ensureCapacityInternal(int minCapacity)` 方法用于確保數組有足夠的容量，如果不足則進行擴容：

```java
private void ensureCapacityInternal(int minCapacity) {
? ? ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
? ? modCount++;

? ? // overflow-conscious code
? ? if (minCapacity - elementData.length > 0)
? ? ? ? grow(minCapacity);
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
? ? ? ? return Math.max(DEFAULT_CAPACITY, minCapacity);
? ? }
? ? return minCapacity;
}
```

### 4. 自動擴容機制

當 `ArrayList` 中的元素超過當前數組的容量時，需要進行擴容。`grow(int minCapacity)` 方法用于擴容：

```java
private void grow(int minCapacity) {
? ? int oldCapacity = elementData.length;
? ? int newCapacity = oldCapacity + (oldCapacity >> 1);
? ? if (newCapacity - minCapacity < 0)
? ? ? ? newCapacity = minCapacity;
? ? if (newCapacity - MAX_ARRAY_SIZE > 0)
? ? ? ? newCapacity = hugeCapacity(minCapacity);
? ? elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
? ? if (minCapacity < 0) // overflow
? ? ? ? throw new OutOfMemoryError();
? ? return (minCapacity > MAX_ARRAY_SIZE) ?
? ? ? ? Integer.MAX_VALUE :
? ? ? ? MAX_ARRAY_SIZE;
}
```

- `oldCapacity`：舊容量，即擴容前數組的長度。
- `newCapacity`：新容量，為舊容量的 1.5 倍。
- 如果 `newCapacity` 仍小于所需的最小容量，則將其設為 `minCapacity`。
- 如果 `newCapacity` 超過了 `MAX_ARRAY_SIZE`，則調用 `hugeCapacity(int minCapacity)` 方法進行處理。
- 最后通過 `Arrays.copyOf` 方法將舊數組復制到新數組中。

### 5. 刪除元素

`ArrayList` 提供了刪除元素的方法 `remove(int index)` 和 `remove(Object o)`：

```java
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; // clear to let GC do its work

? ? return oldValue;
}

public boolean remove(Object o) {
? ? if (o == null) {
? ? ? ? for (int index = 0; index < size; index++)
? ? ? ? ? ? if (elementData[index] == null) {
? ? ? ? ? ? ? ? fastRemove(index);
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? } else {
? ? ? ? for (int index = 0; index < size; index++)
? ? ? ? ? ? if (o.equals(elementData[index])) {
? ? ? ? ? ? ? ? fastRemove(index);
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? }
? ? return false;
}

private void fastRemove(int index) {
? ? modCount++;
? ? int numMoved = size - index - 1;
? ? if (numMoved > 0)
? ? ? ? System.arraycopy(elementData, index+1, elementData, index, numMoved);
? ? elementData[--size] = null; // clear to let GC do its work
}
```

- `remove(int index)`：根據索引刪除元素，首先檢查索引的有效性，然后通過 `System.arraycopy` 方法將索引后的元素向前移動，覆蓋要刪除的元素。
- `remove(Object o)`：根據對象刪除元素，通過遍歷找到目標元素并調用 `fastRemove(int index)` 方法進行刪除。

### 6. 獲取元素和修改元素

`ArrayList` 提供了獲取元素的方法 `get(int index)` 和修改元素的方法 `set(int index, E element)`：

```java
public E get(int index) {
? ? rangeCheck(index);
? ? return elementData(index);
}

public E set(int index, E element) {
? ? rangeCheck(index);

? ? E oldValue = elementData(index);
? ? elementData[index] = element;
? ? return oldValue;
}
```

- `get(int index)`：根據索引獲取元素，首先檢查索引的有效性，然后返回數組中的對應元素。
- `set(int index, E element)`：根據索引修改元素，首先檢查索引的有效性，然后將指定位置的元素替換為新元素，并返回舊元素。