Java集合-ArrayList

前言

ArrayList 是 Java 集合框架中基于数组实现的动态数组，支持自动扩容和快速随机访问。

以下从数据结构、构造方法和核心方法三个角度分析其源码实现（基于JDK 1.8）。

源码分析

数据结构

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 序列化ID
    private static final long serialVersionUID = 8683452581122892189L;
    
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 空数组（用于无参构造初始化）
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    // 默认容量的空数组（无参构造时首次扩容到DEFAULT_CAPACITY）
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    // 存储元素的数组（transient修饰，避免序列化整个数组）
    transient Object[] elementData;
    
    // 当前元素数量
    private int size;
    
    // 快速失败机制计数器
    protected transient int modCount = 0;
}

关键变量说明：

elementData：实际存储元素的数组，使用transient修饰，序列化时仅写入有效元素。
size：记录当前元素数量（不是数组长度）。
modCount：记录结构修改次数（如添加、删除），用于迭代器的快速失败机制。

构造方法

ArrayList 一共有三种构造方法，无参构造、指定初始容量构造、基于集合构造。

// 无参构造
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 指定初始容量构造
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);
    }
}

// 基于集合构造
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;
    }
}

无参构造：

初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组。
首次添加元素时扩容到默认容量10（延迟分配）。

指定初始容量构造：

直接初始化数组大小为initialCapacity，避免后续扩容开销。

基于集合构造：

将集合转换为数组，并处理可能的类型不匹配问题（如Arrays.ArrayList返回的数组类型）。

核心方法

在 ArrayList 中最为核心的是插入、删除、获取、扩容、缩容这几个方法。

插入（add）

插入一共有两种实现方式，一种是尾部插入，另一种是根据指定位置插入。

// 尾部插入
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++;
}

如果使用尾部插入，需要在插入之前调用 ensureCapacityInternal 方法做容量检测，如果容量足够就直接在尾部插入元素，容量不够则扩容后插入。

如果使用指定位置插入，则需要将 index 之后的所有元素后移一位，再在 index 插入元素，在检测容量的基础上，还需要调用 rangeCheckForAdd 方法进行插入范围的检测。

由于 ArrayList 使用动态数组存储元素，插入的平均时间复杂度是 $O(n)$。

删除（remove）

删除一共有两种实现方式，一种是按索引删除，一种是按对象删除。

// 按索引删除
public E remove(int index) {
    rangeCheck(index);           // 检查索引是否越界
    modCount++;                  // 修改计数器加1，用于fail-fast机制
    E oldValue = elementData(index);  // 获取要删除的元素
    int numMoved = size - index - 1;  // 计算需要移动的元素数量
    if (numMoved > 0)            // 如果不是删除最后一个元素
        System.arraycopy(elementData, index+1, elementData, index, numMoved); // 将后面元素前移
    elementData[--size] = null;  // 将最后一个位置置空，帮助GC，且size减1
    return oldValue;            // 返回被删除的元素
}

// 按对象删除
public boolean remove(Object o) {
    if (o == null) {            // 处理要删除的元素为null的情况
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);  // 找到并删除
                return true;
            }
    } else {                    // 处理要删除的元素非null的情况
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);  // 找到并删除
                return true;
            }
    }
    return false;               // 没找到返回false
}

按索引删除：

rangeCheck(index)：检查索引是否合法（0 <= index < size），防止越界。
modCount++：用于迭代器检测并发修改。
使用 System.arraycopy() 高效移动元素。
将最后一个位置置为 null，帮助垃圾回收。

按对象删除：

分开处理 null 和非 null 情况，因为 null 不能调用 equals()。
使用线性搜索查找元素位置。
找到后调用 fastRemove() 执行删除（这是一个私有方法，通常直接操作数组）。
返回 boolean 表示是否成功删除。

按对象删除中调用的 fastRemove(int index) 方法实现如下：

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    modCount++;                  // 修改计数器加1
    int numMoved = size - index - 1;  // 计算需要移动的元素数量
    if (numMoved > 0)            // 如果不是删除最后一个元素
        System.arraycopy(elementData, index+1, elementData, index, numMoved); // 将后面元素前移
    elementData[--size] = null;  // 将最后一个位置置空，帮助GC
}

fastRemove(int index) 是一个高效的内部删除方法，通过跳过不必要的检查和返回值处理，优化了删除操作的性能。它与 remove(int index) 的主要区别在于使用场景和开销，是 ArrayList 实现中性能优化的一个典型示例。

由于 ArrayList 使用动态数组存储元素，删除的平均时间复杂度是 $O(n)$。

获取（get）

获取元素的源码实现很简单，只需要检查索引是否在合法范围中，之后直接通过索引从数组中返回元素。

public E get(int index) {
    rangeCheck(index);
    return elementData(index); // 直接通过索引访问数组
}

由于 ArrayList 使用动态数组存储元素，获取的时间复杂度是 $O(1)$。

扩容（grow）

扩容是 ArrayList 的核心方法，当插入的时候容量不足，便会触发扩容，扩容是动态的，主要涉及三个方法：ensureCapacityInternal、ensureExplicitCapacity 和 grow。

ensureCapacityInternal(int minCapacity)：

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

这个方法是确保 ArrayList 内部容量足够的第一步。它接收一个参数 minCapacity，表示需要的最小容量。

解析：

elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA：
- elementData 是 ArrayList 底层用来存储元素的数组。
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个特殊的空数组，表示 ArrayList 刚创建时使用默认容量（还未分配实际空间）。
- 如果当前是默认空数组，说明这是第一次添加元素，需要初始化容量。
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)：
- DEFAULT_CAPACITY 通常是 10（JDK 版本可能不同，但常见默认值是 10）。
- 如果传入的 minCapacity 小于默认容量，就用默认容量（10）代替，确保初始容量不会太小。
ensureExplicitCapacity(minCapacity)：
- 将调整后的 minCapacity 传递给下一步方法，进入具体的容量检查和扩容逻辑。

ensureExplicitCapacity(int minCapacity)：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

这个方法检查当前数组是否需要扩容，并调用 grow方法进行实际扩容。

解析：

modCount++：
- modCount 是 ArrayList 的一个修改计数器，用于跟踪结构修改次数（比如添加、删除元素）。
- 在快速失败（fail-fast）机制中，如果迭代时检测到 modCount 变化，会抛出ConcurrentModificationException。
if (minCapacity - elementData.length > 0)
- 检查当前数组长度 elementData.length 是否小于所需容量 minCapacity。
- 如果小于，说明现有容量不够，需要扩容，调用 grow 方法。
不满足条件时：
- 如果当前容量已经足够（minCapacity <= elementData.length），则无需扩容，直接返回。

grow(int minCapacity)：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); // 拷贝数据
}

这是实际执行扩容的核心方法，计算新容量并将原有数据拷贝到新数组中。

解析：

int oldCapacity = elementData.length：
- oldCapacity 记录当前数组的容量。
int newCapacity = oldCapacity + (oldCapacity >> 1)：
- oldCapacity >> 1 是位运算，相当于除以 2。
- 新容量 = 旧容量 + 旧容量/2 = 旧容量的1.5倍。
- 例如：旧容量是10，新容量就是15；旧容量是16，新容量就是24。
if (newCapacity - minCapacity < 0)：
- 检查1.5倍扩容后的容量是否仍然小于 minCapacity。
- 如果是，直接用 minCapacity 作为新容量，确保至少满足需求。
- 场景：一次性添加大量元素，1.5倍不足以容纳。
if (newCapacity - MAX_ARRAY_SIZE > 0)：
- MAX_ARRAY_SIZE 通常是 Integer.MAX_VALUE - 8（为了留出一些头部空间）。
- 如果新容量超过这个最大限制，调用 hugeCapacity 方法处理超大容量情况。
elementData = Arrays.copyOf(elementData, newCapacity)：
- 使用 Arrays.copyOf 创建一个新数组，大小为 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;
}

/**
如果minCapacity超过MAX_ARRAY_SIZE，返回Integer.MAX_VALUE（约21亿）。
否则返回MAX_ARRAY_SIZE。
**/

整体流程

触发扩容：调用 add 或 ensureCapacity 时，传入所需的最小容量 minCapacity。
初始检查：ensureCapacityInternal 处理默认空数组情况，调整 minCapacity。
容量判断：ensureExplicitCapacity 确认是否需要扩容。
执行扩容：grow 计算新容量（默认1.5倍），并将数据拷贝到新数组。

扩容涉及数组拷贝，时间复杂度 $O(n)$。

缩容（trim）

缩容的作用是将 ArrayList 底层数组的容量缩减到当前实际元素个数（size），以节省内存空间。

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0) ? EMPTY_ELEMENTDATA 
            : Arrays.copyOf(elementData, size);
    }
}

trimToSize() 方法用于“修剪” ArrayList 的底层数组 elementData，使其容量等于当前元素个数 size，从而释放多余的内存空间。通常在确定 ArrayList大小不再变化时调用，以优化内存使用。

后记

对 ArrayList 的特性总结如下：

动态调整大小
基于数组实现
非线程安全
允许重复与 null
有序性
默认自动扩容为原本的1.5倍

总的来说，ArrayList适合需要频繁随机访问和动态调整大小的场景，但不适合高并发或频繁在中间插入/删除元素的操作。