## 深入分析 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)`：根据索引修改元素，首先检查索引的有效性，然后将指定位置的元素替换为新元素，并返回旧元素。