ArrayList详解

ArrayList 源码深度解析（基于 JDK 8）

ArrayList 是 Java 集合框架中最常用的 List 实现类，基于动态数组实现，支持自动扩容，适用于频繁查询、少量增删的场景。本文将从继承关系、核心源码、扩容机制、迭代器实现等方面，全面解析 ArrayList 的工作原理。

ArrayList 核心特性与继承关系

核心特性

有序性：元素按插入顺序存储，支持通过索引访问（0 基索引）。
可重复性：允许存储重复元素，也允许存储 null 值。
动态扩容：底层数组容量不足时自动扩容，无需手动管理大小。
非线程安全：多线程环境下并发修改可能导致数据不一致（需手动同步或使用 CopyOnWriteArrayList）。

继承关系

1 2	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承 AbstractList：复用了 List 接口的部分默认实现（如 addAll、indexOf 等）。
实现 List：遵循 List 接口规范，支持列表的基本操作。
实现 RandomAccess：标记接口，表明支持快速随机访问（通过索引直接访问，时间复杂度 O(1)），遍历此类集合时，普通 for 循环效率高于迭代器。
实现 Cloneable：支持克隆（浅拷贝）。
实现 Serializable：支持序列化，可通过流传输。

核心变量解析

ArrayList 的核心功能依赖于以下变量，决定了其存储方式和扩容行为：

// 1. 默认初始容量（无参构造器第一次添加元素时的初始容量）
private static final int DEFAULT_CAPACITY = 10;

// 2. 空数组（用户指定初始容量为 0 时使用）
private static final Object[] EMPTY_ELEMENTDATA = {};

// 3. 无参构造器专用空数组（第一次添加元素时会扩容至 DEFAULT_CAPACITY）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 4. 底层存储元素的数组（transient 表示不参与默认序列化，需自定义序列化逻辑）
transient Object[] elementData;

// 5. 集合实际元素数量（区别于数组容量 capacity）
private int size;

// 6. 数组最大容量（避免某些 VM 因数组头部信息导致 OOM）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

关键区别：

EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是空数组，但前者用于用户指定容量为 0 的场景（如 new ArrayList(0)），第一次添加元素时直接按需求扩容；后者用于无参构造器，第一次添加元素时会扩容至 DEFAULT_CAPACITY（10）。

构造函数解析

ArrayList 提供三种构造函数，用于初始化底层数组：

自定义初始容量

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity]; // 直接创建指定容量的数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA; // 关联空数组（后续扩容按实际需求）
    } else {
        throw new IllegalArgumentException("非法容量: " + initialCapacity);
    }
}

无参构造器（最常用）

1
2
3

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 延迟初始化，初始为空数组
}

延迟初始化：无参构造器不会立即分配容量为 10 的数组，而是在第一次添加元素时才扩容，减少内存浪费。

通过集合初始化

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a; // 若为 ArrayList，直接复用其数组（浅拷贝）
        } else {
            // 非 ArrayList 集合，复制元素到新数组
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        elementData = EMPTY_ELEMENTDATA; // 空集合则关联空数组
    }
}

核心方法解析

1. 添加元素：`add(E e)`

添加元素的核心是确保数组容量充足，不足则触发扩容。

public boolean add(E e) {
    // 确保容量：size + 1 是当前所需最小容量
    ensureCapacityInternal(size + 1); 
    // 元素放入数组，size 自增
    elementData[size++] = e;
    return true;
}

扩容流程详解：

计算所需最小容量：

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 若为无参构造的初始状态（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），则最小容量为 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity; // 否则直接返回所需容量
}

检查是否需要扩容：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 记录结构修改次数（用于迭代器的 fail-fast 机制）
    // 若所需容量 > 当前数组长度，触发扩容
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

执行扩容：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 扩容 1.5 倍（oldCapacity + oldCapacity/2，位运算更高效）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 若扩容后仍小于所需容量（如初始为空数组时），直接用所需容量
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    // 若超过最大容量，使用 Integer.MAX_VALUE 或 MAX_ARRAY_SIZE
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? 
            Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
    // 复制原数组元素到新数组（扩容核心：创建新数组 + 复制元素）
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容逻辑总结：

默认扩容 1.5 倍（平衡内存与性能）；
特殊情况（如初始为空数组）直接按所需容量扩容；
最大容量限制为 Integer.MAX_VALUE（避免 OOM）。

2. 删除元素：`remove(int index)`

删除指定索引元素，核心是数组元素移位和帮助 GC。

public E remove(int index) {
    rangeCheck(index); // 检查索引是否越界（index >= size 则抛异常）
    modCount++; // 记录结构修改
    E oldValue = elementData(index); // 获取待删除元素
    // 计算需要移动的元素数量（删除位置后的元素都需左移一位）
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 数组复制：将 index+1 及以后的元素左移一位
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    elementData[--size] = null; // 最后一位设为 null，帮助 GC 回收
    return oldValue; // 返回被删除的元素
}

性能特点：

中间位置删除需移动大量元素，时间复杂度 O(n)，效率较低；
尾部删除无需移动元素，效率高（O(1)）。

3. 获取元素：`get(int index)`

随机访问元素，体现 ArrayList 快速查询的优势。

public E get(int index) {
    rangeCheck(index); // 检查索引越界
    return elementData(index); // 直接返回数组元素（O(1) 时间复杂度）
}

// 内部方法：获取数组元素（强转类型）
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

迭代器与 Fail-Fast 机制

ArrayList 的迭代器（Itr）是快速失败（Fail-Fast） 迭代器，用于检测并发修改，避免数据不一致。

迭代器核心实现

private class Itr implements Iterator<E> {
    int cursor; // 下一个要返回的元素索引
    int lastRet = -1; // 最后返回的元素索引（-1 表示未返回）
    int expectedModCount = modCount; // 迭代器创建时的结构修改次数

    public boolean hasNext() {
        return cursor != size; // 游标未到末尾则有元素
    }

    public E next() {
        checkForComodification(); // 检查并发修改
        int i = cursor;
        if (i >= size) throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) throw new ConcurrentModificationException();
        cursor = i + 1; // 游标后移
        return (E) elementData[lastRet = i]; // 返回当前元素，更新 lastRet
    }

    public void remove() {
        if (lastRet < 0) throw new IllegalStateException();
        checkForComodification(); // 检查并发修改
        try {
            ArrayList.this.remove(lastRet); // 调用 ArrayList 的 remove 方法
            cursor = lastRet; // 游标回退（删除后元素左移，游标无需 +1）
            lastRet = -1; // 重置 lastRet
            expectedModCount = modCount; // 同步修改次数（避免后续 check 失败）
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // 核心：检查并发修改
    final void checkForComodification() {
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
}

Fail-Fast 机制原理

触发条件：迭代过程中，若其他线程（或当前线程）通过非迭代器方法（如 list.remove(index)）修改集合结构（modCount 变化），则 modCount != expectedModCount，迭代器立即抛出 ConcurrentModificationException。
目的：及时发现并发修改，避免迭代器返回不一致的数据（快速失败而非默默出错）。
局限性：仅为调试辅助机制，不能保证 100% 检测到并发修改（如修改后又改回原值）。

使用注意事项

1. 初始化时指定容量

无参构造器默认第一次扩容至 10，若已知元素数量（如 1000 个），建议初始化时指定容量：

1	List<String> list = new ArrayList<>(1000); // 避免多次扩容，提升性能

2. 遍历方式选择

随机访问场景：用普通 for 循环（效率高于迭代器）：

1
2
3

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

需删除元素：必须用迭代器的remove()方法（避免ConcurrentModificationException）：

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("a")) {
        it.remove(); // 安全删除
    }
}

3. 线程安全问题

ArrayList 非线程安全，多线程并发修改可能导致：

数据丢失（如同时 add 元素）；
数组越界（扩容时未加锁，导致一个线程访问到无效索引）。

解决方案：

手动同步（synchronized 或 Collections.synchronizedList）；
使用并发容器（如 CopyOnWriteArrayList，适合读多写少场景）