ArrayList 详细解析

ArrayList 本质上就是一个类，内部维护了一个数组，用来装元素；再用一个 size 变量记录“实际放了多少个元素”。

可以把它抽象成这样

Java

        public class ArrayList<E> {
    transient Object[] elementData;
    private int size;
}

这里最关键的是：

elementData：真正存数据的底层数组
size：当前有效元素个数

注意，elementData.length 不等于 size。

比如：

elementData.length = 10，表示底层容量是 10
size = 3，表示实际只用了 3 个位置

也就是说，前 3 个位置有数据，后 7 个位置可能还是空着的。

底层为什么用 Object

源码里不会直接写成 E[]，而是通常写成 Object[]。

原因是 Java 泛型有“类型擦除”，运行时并不知道 E 到底是什么类型，所以很多泛型集合底层都用 Object[] 存，再在取出时做类型转换。

也就是说：

存的时候：本质上放进 Object[]
取的时候：再转成 E

这也是为什么 ArrayList 能装各种类型的对象，但推荐你一定配合泛型使用。

初始化是怎么做的

ArrayList 常见有几种构造方式：

Java

        new ArrayList<>();
new ArrayList<>(20);
new ArrayList<>(collection);

源码层面重点看前两种。

无参构造
无参构造并不是一上来就创建一个长度 10 的数组，而是先给一个“空数组”。
类似这样：
Java
```
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

    
```
这意味着：
- 刚 new ArrayList<>() 时，并没有真正分配默认容量
- 只有第一次 add 的时候，才真正扩成默认容量
这样做的好处是节省内存。因为很多列表创建了，但可能根本没放数据。

指定容量构造
如果你写： new ArrayList<>(20);
那它会直接创建一个长度为 20 的数组。
类似：

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

这个构造方式在已知数据规模时很有价值，因为可以减少扩容次数。

add 到底做了什么

最常见的是： list.add(e);

源码思路大致是：

Java

        public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

你可以把它拆成两步理解：

第一步：确认容量够不够 ensureCapacityInternal(size + 1) 的作用是：
- 现在要插入一个新元素
- 插入后至少要能装下 size + 1 个
- 如果当前数组不够大，就扩容
第二步：把元素放到末尾

Java

        elementData[size] = e;
size++;

或者写成：

Java

        elementData[size++] = e;

这说明尾部追加为什么快：

不需要查位置
不需要搬移已有元素
大多数时候只是在数组尾部放一个值

所以尾插通常是平均 O(1)。

第一次 add 时为什么默认变成 10

这是很多人容易记错的地方。

无参构造时，并没有直接创建长度 10 的数组。第一次添加元素时，才会触发默认容量初始化。

逻辑大致类似：

Java

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

默认容量一般是：private static final int DEFAULT_CAPACITY = 10;

所以：

new ArrayList<>() 时底层还是空数组
第一次 add 时，才变成容量 10

这是一种延迟分配策略。

扩容机制是怎么实现的

这是源码最核心的部分之一。

如果当前容量不够，就会走 grow() 方法。典型思路是：

Java

        // JDK 8
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// JDK 17
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(
                oldCapacity,
                minCapacity - oldCapacity, // 最小需要增量
                oldCapacity >> 1             // 期望增量：还是1.5倍
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 首次扩容：直接到 10
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

这里最关键的一句是： int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 就是除以 2，所以新容量约等于旧容量的 1.5 倍。

例如：

10 扩到 15
15 扩到 22
22 扩到 33

为什么是 1.5 倍，不是 2 倍或 +1 这是空间和时间的折中。

如果每次只加 1：

扩容太频繁
每次都要复制数组
性能会很差

如果每次乘 2：

扩容次数更少
但可能浪费较多内存
1.5 倍是一个比较平衡的策略。

扩容真正贵在 Arrays.copyOf(elementData, newCapacity);

它会：

创建一个更大的新数组
把旧数组元素复制进去
把引用指向新数组

所以扩容本质不是“把旧数组拉长”，而是“新建+拷贝”。

这就是 ArrayList 扩容的成本来源。

按下标插入为什么慢

如果你调用：list.add(index, element); 就不是简单尾插了。源码思路大概是：

Java

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

这里的关键是：System.arraycopy(...)

它会把 index 后面的元素整体向后挪一位。

比如原来：[A, B, C, D]

在位置 1 插入 X：

B、C、D 全部后移
再把 X 放到位置 1

变成：[A, X, B, C, D]

所以中间插入慢，不是因为“找不到位置”，而是因为“要搬家”。

时间复杂度是 O(n)。

remove 为什么也慢

删除和插入是反过来的过程。

例如：list.remove(index);

源码思路大概是：

Java

        public E remove(int index) {
    rangeCheck(index);
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;
    return oldValue;
}

这个过程分三步：

取出旧值
把后面的元素整体前移
把最后一个位置置为 null

为什么最后要置 null, 这一个很重要：elementData[--size] = null;

目的不是为了“好看”，而是为了让对象不再被数组引用，方便 GC 回收。

如果不置空，虽然 size 变小了，但数组里可能还留着旧对象引用，会造成对象无法及时释放。

这也是源码里很典型的内存管理细节。

get 为什么这么快

看 get(index) 的思路：

Java

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

实际就是数组下标访问。

因为底层是连续数组，所以通过下标可以直接定位，不需要遍历，这就是 O(1)。

这也是 ArrayList 最大的性能优势

set 为什么也快

set(index, element) 只是覆盖指定位置：

Java

        public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

它不会搬移元素，只是替换，所以也很快，通常是 O(1)。

为什么允许 null 和重复元素

因为 ArrayList 本身不做去重，也不限制 null。

它更像一个“顺序容器”，而不是“唯一集合”。

比如你可以存：

Java

        list.add(null);
list.add("A");
list.add("A");

这些都合法。

这和 Set 的设计目标不同。List 关注的是顺序和位置，不是唯一性。

遍历时为什么会出现并发修改异常

这个点和源码里的 modCount 有关。

ArrayList 继承体系里有一个字段：protected transient int modCount = 0;

每当发生“结构性修改”时，比如：

add
remove
clear
扩容引发的结构变化

通常都会增加 modCount。而迭代器创建时，会记录一个当前版本号：int expectedModCount = modCount;

之后每次迭代时，都会检查：

当前 modCount 是否还等于 expectedModCount 如果不等，说明遍历过程中集合被外部改了，就抛出 ConcurrentModificationException。

这就是 fail-fast 机制它不是为了线程安全，而是为了“尽快发现错误使用”。

例如：

Java

        for (String s : list) {
    if (s.equals("A")) {
        list.remove(s);
    }
}

这里增强 for 底层用的是迭代器。你一边遍历，一边直接操作集合本体，版本号就变了，迭代器会立刻报错。

为什么 Iterator.remove 可以因为如果你用的是迭代器自己的删除方法，它会同步更新自己的状态和 expectedModCount，所以不会冲突。

这个机制是面试里很常问的源码点。

为什么说 ArrayList 不是线程安全的

因为它的大部分操作都没有加锁。

举个简单例子，两个线程同时执行：

Java

        list.add("A");
list.add("B");

add 里面会涉及：

读 size
检查容量
写入数组
size++

这些步骤不是原子操作。多个线程同时改，就可能导致：

写覆盖
size 错乱
数组越界
数据丢失

所以 ArrayList 在多线程并发写场景下是不安全的。

toArray 为什么有意义

ArrayList 虽然底层就是数组，但它不会直接把内部数组裸露给你，因为：

内部数组可能容量大于实际元素个数
直接暴露会破坏封装

所以才需要 toArray()：

给你一个“只包含有效元素”的新数组副本
避免外部直接操作内部存储结构

这体现了源码设计中的封装思想。

一个简化版 ArrayList 帮你彻底理解

Java

        class MyArrayList<E> {
    private Object[] data = new Object[10];
    private int size = 0;

    public void add(E e) {
        if (size == data.length) {
            grow();
        }
        data[size++] = e;
    }

    public E get(int index) {
        checkIndex(index);
        return (E) data[index];
    }

    public E remove(int index) {
        checkIndex(index);
        E oldValue = (E) data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null;
        return oldValue;
    }

    private void grow() {
        int newCapacity = data.length + (data.length >> 1);
        Object[] newData = new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }
}

收起

时间复杂度

这是理解 ArrayList 的重点。

按下标访问：O(1) 原因：底层是数组，可以直接定位到某个位置。
尾部添加：平均 O(1) 大多数时候直接放到末尾即可。但如果刚好触发扩容，会退化成 O(n)，因为要复制旧数组。
中间插入：O(n) 因为插入位置后面的元素都要整体后移。
中间删除：O(n) 因为删除后，后面的元素要整体前移。
查找某个元素：O(n) 因为通常要从前往后一个个比对。

所以 ArrayList 的

优势是：查得快，尾插也不错。

劣势是：中间插入删除慢。

Fonnpo

Spring 核心详解

HashMap 详细解析

LinkedList 详细解析