ArrayList源码详解-Java21版

ArrayList 可以称得上是集合框架方面最常用的类了，可以和 HashMap 一较高下。从名字就可以看得出来，ArrayList 实现了 List 接口，并且是基于数组实现的。

数组的大小是固定的，一旦创建的时候指定了大小，就不能再调整了。也就是说，如果数组满了，就不能再添加任何元素了。ArrayList 在数组的基础上实现了自动扩容，并且提供了比数组更丰富的预定义方法（各种增删改查），非常灵活。

Java 这门编程语言和别的编程语言，比如说 C语言的不同之处就在这里，如果是 C语言的话，你就必须得动手实现自己的 ArrayList，原生的库函数里面是没有的。所以刷题一般不用C语言。

01、创建ArrayList

这样就可以创建一个ArrayList：

ArrayList<String> alist = new ArrayList<String>();

可以通过上面的语句来创建一个字符串类型的 ArrayList（通过尖括号来限定 ArrayList 中元素的类型，如果尝试添加其他类型的元素，将会产生编译错误），更简化的写法如下：

List<String> alist = new ArrayList<>();

由于 ArrayList 实现了 List 接口，所以 alist 变量的类型可以是 List 类型；new 关键字声明后的尖括号中可以不再指定元素的类型，因为编译器可以通过前面尖括号中的类型进行智能推断。

此时会调用无参构造方法（见下面的代码）创建一个空的数组，常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值为 {}。

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

如果非常确定 ArrayList 中元素的个数，在创建的时候还可以指定初始大小：

List<String> alist = new ArrayList<>(20);

02、向ArrayList中添加元素

可以通过 add() 方法向 ArrayList 中添加一个元素。

alist.add("Hanserwei");

我们来跟一下源码，看看 add 方法到底执行了哪些操作。跟的过程中，我们也可以偷师到 Java 源码的作者（大师级程序员）是如何优雅地写代码的。

private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
}

这里附加一个堆栈过程图：

堆栈过程图示：
add(element)
└── if (size == elementData.length) // 判断是否需要扩容
    ├── grow(minCapacity) // 扩容
    │   └── newCapacity = oldCapacity + (oldCapacity >> 1) // 计算新的数组容量
    │   └── Arrays.copyOf(elementData, newCapacity) // 创建新的数组
    ├── elementData[size++] = element; // 添加新元素
    └── return true; // 添加成功

来具体看一下，先是 add() 方法的源码（已添加好详细地注释）

/**
 * 将指定的元素追加到此列表的末尾。
 *
 * @param e 要附加到此列表的元素
 * @return 成功返回true
 */
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

这里面有个modCount字段，这个是一个计数器，用来记录 ArrayList 被结构性修改的次数。结构性修改指的是那些会改变列表大小，或者以其他方式扰乱列表，导致正在进行的迭代可能产生错误结果的操作。

什么是“结构性修改”？

当您对 ArrayList 进行以下操作时，就会触发结构性修改：

添加元素： 比如 add(E e) 或 add(int index, E element)。

移除元素： 比如 remove(Object o) 或 remove(int index)。

清空列表： 比如 clear()。

modCount 如何实现“快速失败”（Fail-Fast）机制？

这个 modCount 字段主要用于实现 ArrayList 迭代器（通过 iterator() 和 listIterator() 方法返回）的**“快速失败”（fail-fast）机制**。

当您使用迭代器遍历 ArrayList 时，迭代器会在内部记录当前的 modCount 值。在每次执行 next()、remove()、previous()、set() 或 add() 等操作时，迭代器会检查当前的 ArrayList 的 modCount 是否与它最初记录的值一致。

如果 modCount 值发生了变化（意味着在迭代过程中，列表被其他线程或同一个线程的其他操作进行了结构性修改），迭代器会立即抛出 ConcurrentModificationException 异常。

如果 modCount 值没有变化，迭代器会继续正常工作。

这种机制的目的是为了提供一种快速失败的行为，而不是在并发修改时出现不可预测的、非确定性的行为。想象一下，如果在迭代过程中列表被修改了，而迭代器却没有感知，那么您可能会得到错误的结果，或者甚至会崩溃。ConcurrentModificationException 就是为了尽早地发现并报告这种潜在的问题。

当你要添加元素的时候，首先modCount会先加1，记录机构性修改。然后调用add(e, elementData, size)方法。

private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
}

这个这里我是创建完ArrayList第一次添加元素，那么默认的数组大小就是0，所以会触发扩容。

private Object[] grow() {
        return grow(size + 1);
}

该方法用于在添加元素时自动扩容。当 ArrayList 容量不足时，grow() 方法被调用以增加容量，确保能容纳至少 size + 1 个元素。它通过调用另一个 grow(int minCapacity) 方法实现容量增长。

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

该方法用于扩容数组。如果当前容量大于0或数组不为默认空数组，则计算新容量并复制原数组；否则创建一个默认容量或指定最小容量的新数组。这里直接进else分支。这里的DEFAULT_CAPACITY是默认大小，大小为10。我这的minCapacity为1，所以最后返回一个新数组大小为10。

数组扩容完毕，然后添加元素，最后size++就完事了。add方法默认总是返回true。

那么如果满了下一次扩容会扩容成多大呢？

这里会调用ArraysSupport.newLength(int oldLength, int minGrowth, int prefGrowth)方法，该方法接收三个参数，当前容量、最小增长量和推荐增长量（当前容量的一半）。基于这三个来计算新数组的大小。

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // preconditions not checked because of inlining
    // assert oldLength >= 0
    // assert minGrowth > 0

    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        // put code cold in a separate method
        return hugeLength(oldLength, minGrowth);
    }
}

注意到if前面的那个对prefLength的重新赋值了吗？这是为了预防溢出！

注意这里的if语句，如果容量允许，默认扩大推荐增长量（当前容量的一半），如果容量不允许，则会调用下面这个函数

private static int hugeLength(int oldLength, int minGrowth) {
    int minLength = oldLength + minGrowth;
    if (minLength < 0) { // overflow
        throw new OutOfMemoryError(
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
    } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
        return SOFT_MAX_ARRAY_LENGTH;
    } else {
        return minLength;
    }
}

这个函数也很好理解，如果实在无法扩容了，那就跟你爆了(抛出异常！)，如果还能塞下，就尽量塞下。

这个时候知道了需要扩容为多少了，用Arrays.copyOf方法返回新数组。然后添加元素，size改变，就完事了。自此ArrayList的add方法就这么多。和Java 8有一定区别，但是差别不大。

03、向ArrayList的指定位置添加元素

除了 add(E e) 方法，还可以通过 add(int index, E element) 方法把元素添加到 ArrayList 的指定位置：

alist.add(0, "Hanserwei");

add(int index ,E element)的源码如下：

/**
 * 在指定位置插入一个元素。
 *
 * @param index   要插入元素的位置
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围，则抛出此异常
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
            elementData, index + 1,
            s - index);
    elementData[index] = element;
    size = s + 1;
}

add(int index, E element)方法会调用到一个非常重要的本地方法 System.arraycopy()，它会对数组进行复制（要插入位置上的元素往后复制）。

来细品一下。

这是 arraycopy() 的语法：

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

在 ArrayList.add(int index, E element) 方法中，具体用法如下：

System.arraycopy(elementData, index,elementData, index + 1,s - index);

elementData：表示要复制的源数组，即 ArrayList 中的元素数组。
index：表示源数组中要复制的起始位置，即需要将 index 及其后面的元素向后移动一位。
elementData：表示要复制到的目标数组，即 ArrayList 中的元素数组。
index + 1：表示目标数组中复制的起始位置，即将 index 及其后面的元素向后移动一位后，应该插入到的位置。
s - index：表示要复制的元素个数，即需要将 index 及其后面的元素向后移动一位，需要移动的元素个数为 s- index。

如图所示：

04、更新ArrayList中的元素

可以使用 set() 方法来更改 ArrayList 中的元素，需要提供下标和新元素。

alist.set(0, "Hanserwu");

假设原来 0 位置上的元素为“Hanserwei”，现在可以将其更新为“Hanserwu”。

来看一下 set() 方法的源码：

/**
 * 用指定元素替换指定位置的元素。
 *
 * @param index   要替换的元素的索引
 * @param element 要存储在指定位置的元素
 * @return 先前在指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围，则抛出此异常
 */
public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

该方法会先对指定的下标进行检查，看是否越界，然后替换新值并返回旧值。

05、删除ArrayList中的元素

remove(int index) 方法用于删除指定下标位置上的元素，remove(Object o) 方法用于删除指定值的元素。

alist.remove(1);
alist.remove("Hanserwei");

先来看 remove(int index) 方法的源码：

/**
 * 删除指定位置的元素。
 *
 * @param index 要删除的元素的索引
 * @return 先前在指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围，则抛出此异常
 */
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

调用fastRemove(Object[] es, int i)方法：

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

需要注意的是，在 ArrayList 中，删除元素时，需要将删除位置后面的元素向前移动一位，以填补删除位置留下的空缺。如果需要移动元素，则需要使用 System.arraycopy 方法将删除位置后面的元素向前移动一位。最后，将数组末尾的元素置为 null，以便让垃圾回收机制回收该元素占用的空间。

再来看 remove(Object o) 方法的源码：

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found:
    {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

这个 found: {} 是一个**标签代码块（labeled block）**的用法：

标签定义：found 是一个标签名，类似于goto语句的目标位置

代码块作用：{} 内的代码可以使用break语句跳出到指定标签位置

使用场景：在这个例子中，当找到匹配元素时，通过 break found; 跳出整个代码块，避免继续执行后续逻辑

这种写法的优点：

提供了类似"goto"的跳转功能

可以从嵌套循环或多层逻辑中直接跳出

增强代码的控制流灵活性

这是一种相对少见但有效的Java语法特性，主要用于复杂的控制流场景。

注意：有相同元素时，只会删除第一个。

找到元素之后也是调用fastRemove()方法进行删除。

06、查找ArrayList中的元素

如果要正序查找一个元素，可以使用 indexOf() 方法；如果要倒序查找一个元素，可以使用 lastIndexOf() 方法。

来看一下 indexOf() 方法的源码：

/**
 * 返回指定元素在列表中第一次出现的位置。
 * 如果列表不包含该元素，则返回 -1。
 *
 * @param o 要查找的元素
 * @return 指定元素在列表中第一次出现的位置；如果列表不包含该元素，则返回 -1
 */
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

这里对外暴露的是indexOf(Object o)方法，但是内部调用的是indexOfRange(Object o, int start, int end)方法。

如果元素为 null 的时候使用“==”操作符，否则使用 equals() 方法。

lastIndexOf() 方法和 indexOf() 方法类似，不过遍历的时候从最后开始。

/**
 * 返回指定元素在列表中最后一次出现的位置。
 * 如果列表不包含该元素，则返回 -1。
 *
 * @param o 要查找的元素
 * @return 指定元素在列表中最后一次出现的位置；如果列表不包含该元素，则返回 -1
 */
public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = end - 1; i >= start; i--) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = end - 1; i >= start; i--) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

contains() 方法可以判断 ArrayList 中是否包含某个元素，其内部就是通过 indexOf() 方法实现的：

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}