大家好，我是栗筝i，这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 013 篇文章，在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验，并希望进一步完善自己对整个 Java 技术体系来充实自己的技术栈的同学。与此同时，本专栏的所有文章，也都会准备充足的代码示例和完善的知识点梳理，因此也十分适合零基础的小白和要准备工作面试的同学学习。当然，我也会在必要的时候进行相关技术深度的技术解读，相信即使是拥有多年 Java 开发经验的从业者和大佬们也会有所收获并找到乐趣。
–
本文将从介绍 ArrayList 开始，详细探讨其使用方法、工作原理以及背后的源码实现，帮助读者深入理解并灵活运用 ArrayList，以提升编程效率和代码质量。
在接下来的部分中，我们将首先概述 ArrayList 的基本特性及其在 Java 集合框架中的地位。随后，通过实际代码示例展示如何创建、操作和管理 ArrayList。接着，我们会揭示 ArrayList 的内部工作机制，包括其底层数据结构、扩容策略和性能优化等方面的内容。最后，我们将深入分析 ArrayList 的源码，探讨其设计思想和实现细节，以便读者能够更全面地掌握这一重要的集合类。
ArrayList 是最常用的 List 实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
ArrayList 是基于数组实现的，相当于动态数组，其容量能动态增长，类似于 C 语言中的动态申请内存，动态增长内存。
ArrayList 的每个实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是大于等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造 ArrayList 时指定其容量。
ArrayList 在被添加大量元素前，应用程序可以使用 ensureCapacity() 操作来指定 ArrayList 实例的容量，这可以减少递增式再分配的数量。
ArrayList 是非线程安全的，只能在单线程环境下使用，多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类，也可以使用 java.util.concurrent 并发包下的 CopyOnWriteArrayList 类。
ArrayList 的原理其实很好概括和理解，简单概括就是：我们先在 ArrayList 中定义声明一个 Java 数组，接着定义对这个 Java 数组的，添加、删除、修改以及查询这四类方法。这其中最值得注意的是两点，一个是，由于底层操作的是数组，所以在进行删除操作是会涉及对大量元素的移动；另一个则是在增加元素并达到底层 Java 数组容量后的数组扩容问题。
ArrayList 在 Java 中是基于数组实现的动态数组，其核心数据结构是一个 Object 类型的数组 elementData，用于存储元素。
package java.util;
import ...
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 省略其他方法和实现细节
...
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小空实例的共享空数组实例
// 当添加第一个元素时，会扩展为 DEFAULT_CAPACITY
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 用于存储 ArrayList 元素的数组缓冲区
// transient 关键字表示该字段不会被序列化
transient Object[] elementData;
// ArrayList 当前包含的元素数量
private int size;
/`
* 构造一个具有指定初始容量的空列表。
*
* @param initialCapacity 列表的初始容量
* @throws IllegalArgumentException 如果指定的初始容量为负数
*/
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); // 抛出非法参数异常
}
}
/`
* 构造一个初始容量为 10 的空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 使用默认大小的空数组实例
}
/`
* 构造一个包含指定集合元素的列表，这些元素按该集合的迭代器返回的顺序排列。
*
* @param c 要放入列表中的集合
* @throws NullPointerException 如果指定的集合为 null
*/
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray(); // 将集合转换为数组
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a; // 如果集合是 ArrayList 实例，直接使用该数组
} else {
elementData = Arrays.copyOf(a, size, Object[].class); // 否则，复制该数组
}
} else {
elementData = EMPTY_ELEMENTDATA; // 如果集合为空，使用共享的空数组实例
}
}
// 省略其他方法和实现细节
...
}
同样的，正因为 ArrayList 的底层实现是数组（一块连续的内存区域），所以可以轻松的实现快速的随机访问和按索引操作。
package java.util;
import ...
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 省略其他方法和实现细节
...
/`
* 在指定索引处获取元素。
*
* @param index 要获取元素的位置
* @return 指定索引处的元素
*/
E elementData(int index) {
return (E) elementData[index];
}
/`
* 获取指定索引处的元素，并进行范围检查。
*
* @param index 要获取元素的位置
* @return 指定索引处的元素
* @throws IndexOutOfBoundsException 如果索引超出范围
*/
public E get(int index) {
rangeCheck(index); // 检查索引是否在范围内
return elementData(index); // 返回指定索引处的元素
}
/`
* 替换指定位置的元素，并返回被替换的元素。
*
* @param index 要替换元素的位置
* @param element 要存储在指定位置的新元素
* @return 被替换的元素
* @throws IndexOutOfBoundsException 如果索引超出范围
*/
public E set(int index, E element) {
rangeCheck(index); // 检查索引是否在范围内
E oldValue = elementData(index); // 获取旧值
elementData[index] = element; // 替换为新值
return oldValue; // 返回旧值
}
/`
* 检查索引是否在范围内。
*
* @param index 要检查的索引
* @throws IndexOutOfBoundsException 如果索引超出范围
*/
private void rangeCheck(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
/`
* 构建索引超出范围的错误信息。
*
* @param index 超出范围的索引
* @return 错误信息字符串
*/
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
// 省略其他方法和实现细节
...
}
我们知道，数组需要使用着一块连续的内存空间，因此数组的大小一旦被规定就无法改变。那如果我们不断的往里面添加数据的话，ArrayList 是如何进行扩容的呢 ？答案就是 ArrayList 会复制一个新的更大容量的数组：
ensureCapacityInternal(int minCapacity) 的方法，对数组容量进行检查，判断剩余空间是否足够，不够时则进行扩容；package java.util;
import ...
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 省略其他方法和实现细节
...
/`
* 在 ArrayList 末尾添加一个元素。
*
* @param e 要添加的元素
* @return 总是返回 true
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够容纳新元素，增加 modCount
elementData[size++] = e; // 将新元素添加到数组中，size 自增
return true;
}
/`
* 确保 ArrayList 的容量足够容纳指定数量的元素。
*
* @param minCapacity 需要的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/`
* 计算所需的容量
*
* @param elementData 当前的数组
* @param minCapacity 需要的最小容量
* @return 计算后的容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/`
* 显式地确保 ArrayList 的容量足够。
*
* @param minCapacity 需要的最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
// 递增修改计数，以支持快速失败机制
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 如果所需容量超过当前数组长度，则扩展数组
}
/`
* 扩展数组的容量。
*
* @param minCapacity 需要的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
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);
}
// 省略其他方法和实现细节
...
}
grow(minCapacity) 方法对数组进行扩容package java.util;
import ...
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 省略其他方法和实现细节
...
/`
* 扩展数组的容量。
*
* @param minCapacity 需要的最小容量
*/
private void grow(int minCapacity) {
// 将数组长度赋值给 oldCapacity
int oldCapacity = elementData.length;
// 将 oldCapacity 右移一位再加上 oldCapacity，即相当于 newCapacity=1.5 倍 oldCapacity(不考虑精度损失)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果 newCapacity 还是小于 minCapacity，直接将 minCapacity 赋值给 newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 特殊情况：newCapacity 的值过大，直接将整型最大值赋给 newCapacity，
// 即 newCapacity=Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 将 elementData 的数据拷贝到扩容后的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
/`
* 如果大于临界值，进行整型最大值的分配
*
* @param minCapacity 需要的最小容量
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
// overflow
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
// 省略其他方法和实现细节
...
}
总结：ArrayList 在添加元素时，会进行一个判断，当「元素个数+1> 当前数组长度（size + 1 > elementData.length）」时，进行扩容，扩容后的数组大小是原大小的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。最后将旧数组进行复制（调用 Arrays.copyof()，再调用 System.arraycopy() ），达到扩容的目的，此时新旧列表的 size 大小相同，但 elementData 的长度即容量不同。
ArrayList 在进行根据索引删除时，通过系统 native 方法 System.arraycopy 完成的，原理就是将删除位置后的所有元素重新复制到删除位置到原来最后元素的前一位，并使用 elementData[--size] = null; 清空多余的值。
package java.util;
import ...
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 省略其他方法和实现细节
...
/`
* 从列表中移除指定位置的元素。
* 将所有后续元素左移（索引减一）。
*
* @param index 要移除元素的索引位置
* @return 被移除的元素
* @throws IndexOutOfBoundsException 如果索引超出范围抛出此异常
*/
public E remove(int index) {
rangeCheck(index); // 检查索引是否在合法范围内，防止索引越界
modCount++; // 修改次数加一，用于实现迭代器的快速失败机制（在迭代过程中如果检测到结构变化会抛出异常）
E oldValue = elementData(index); // 获取并保存将要被移除的元素值
int numMoved = size - index - 1; // 计算从 index 之后需要左移的元素数量
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved); // 使用系统方法 arraycopy 来高效地移动数组元素
elementData[--size] = null; // 将最后一个元素设为 null，帮助垃圾收集器回收，并减少实际元素数量
return oldValue; // 返回被移除的元素
}
/`
* 从列表中移除第一次出现的指定元素（如果存在）。
* 如果列表不包含该元素，则不做改变。
* 更正式地说，移除满足 (o==null ? get(i)==null : o.equals(get(i))) 条件的最低索引的元素。
*
* @param o 要从列表中移除的元素
* @return 如果列表包含指定元素则返回 true
*/
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; // 如果没有找到元素，返回 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; // 清理引用，帮助垃圾回收
}
// 省略其他方法和实现细节
...
}
在遍历 ArrayList 或其他类型的 List 集合时进行元素的删除，确实需要格外小心。这是因为集合的结构修改（如添加或删除元素）可能会影响遍历过程，导致 ConcurrentModificationException 异常或者跳过元素。这里详细解释下这两种情况：
ConcurrentModificationException 是 Java 在迭代器检测到除了它自身的 remove() 方法之外的任何修改时抛出的异常。这是 Java 集合框架的 “fail-fast” 行为的一部分，用来快速响应错误，防止未定义的行为。
当你使用迭代器或者增强型 for 循环（本质上使用的是迭代器）遍历 ArrayList 时，如果在遍历过程中通过集合的直接方法（如 list.remove(index)）修改集合，就会导致迭代器的内部状态与集合的状态不一致。因为迭代器内部有一个 expectedModCount 变量，用来记录初始化迭代器时集合的修改次数。每次迭代时，迭代器都会检查集合的当前修改次数是否仍然等于 expectedModCount。如果不等，就会抛出 ConcurrentModificationException。
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
for (Integer number : list) {
if (number % 2 == 0) {
list.remove(number); // 尝试删除元素
}
}
}
}
在这个例子中，尝试删除所有偶数。因为 list.remove(Object) 修改了集合，而这种修改没有通过迭代器进行，所以当迭代器检测到修改时（在下一次调用 next() 时），它将抛出 ConcurrentModificationException
另一个常见的问题是在使用普通的 for 循环遍历并同时删除元素时可能会跳过某些元素。这是因为删除元素会影响数组的索引：
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
for (int i = 0; i < list.size(); i++) {
if (list.get(i) % 2 == 0) {
list.remove(i); // 删除元素
i--; // 通过递减 i 来调整索引
}
}
}
}
在这个例子中，我们尝试删除所有偶数。如果不递减 i 的值，当元素被移除时，列表中的元素会向左移动，这导致下一个元素跳过检查。在上面的代码中，通过 i-- 调整，我们倒是可以确保即使删除了元素，也不会跳过任何元素。
当使用迭代器直接遍历时，应该使用迭代器自身的 remove() 方法来删除元素。这样可以安全地更新 modCount 和 expectedModCount，防止 ConcurrentModificationException：
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
Integer value = it.next();
if (value % 2 == 0) {
it.remove(); // 安全删除
}
}
Java 8 提供的 removeIf() 方法可以在内部安全地修改列表，并避免 ConcurrentModificationException：
java
复制代码
list.removeIf(n -> n % 2 == 0); // 删除所有偶数
使用传统的 for 循环时，从列表的尾部向前遍历和删除可以避免跳过元素的问题：
for (int i = list.size() - 1; i >= 0; i--) {
if (list.get(i) % 2 == 0) {
list.remove(i);
}
}
这些方法各有优势和适用场景。选择哪种方法取决于具体的需求和环境。在多数情况下，使用迭代器的 remove() 方法或 removeIf() 方法提供了最简洁和安全的解决方案。
下面是对 ArrayList 的常用方法和 Collections 类中的一些涉及 ArrayList 的方法进行详细介绍并
add(E e)ArrayList<String> list = new ArrayList<>();
list.add("Apple");
add(int index, E element)ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add(1, "Orange"); // 将 "Orange" 插入在 "Banana" 前面
remove(Object o)ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.remove("Apple");
remove(int index)ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.remove(0); // 删除 "Apple"
get(int index)ArrayList<String> list = new ArrayList<>();
list.add("Apple");
String item = list.get(0); // 获取第一个元素 "Apple"
set(int index, E element)功能：替换指定位置的元素，并返回旧值。
用例：
ArrayList<String> list = new ArrayList<>();
list.add("Apple");
String oldItem = list.set(0, "Orange"); // 将 "Apple" 替换为 "Orange"
size()ArrayList<String> list = new ArrayList<>();
list.add("Apple");
int size = list.size(); // size 为 1
isEmpty()ArrayList<String> list = new ArrayList<>();
boolean empty = list.isEmpty(); // 判断列表是否为空
clear()ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.clear(); // 清空列表
contains(Object o)ArrayList<String> list = new ArrayList<>();
list.add("Apple");
boolean contains = list.contains("Apple"); // 检查是否包含 "Apple"
indexOf(Object o) 和 lastIndexOf(Object o)ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple");
int firstIndex = list.indexOf("Apple"); // 返回 0
int lastIndex = list.lastIndexOf("Apple"); // 返回 2
toArray()ArrayList<String> list = new ArrayList<>();
list.add("Apple");
Object[] array = list.toArray(); // 转换为数组
ArrayList 自身的 API 中包括一些可以实现批量操作的方法，虽然它们不像 Collections 类中的方法那样明确被标记为批量操作。这些方法可以处理多个元素的添加或删除，以及批量的查询操作。以下是一些关键的批量操作方法，直接来自 ArrayList 或其继承的 Collection 接口：
addAll(Collection c)ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> newElements = new ArrayList<>(Arrays.asList(1, 2, 3));
list.addAll(newElements); // 添加多个元素
13, addAll(int index, Collection c)
ArrayList<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
ArrayList<String> newElements = new ArrayList<>(Arrays.asList("x", "y"));
list.addAll(1, newElements); // 在索引1的位置添加多个元素
removeAll(Collection c)ArrayList<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "b"));
list.removeAll(Collections.singleton("b")); // 移除所有 "b"
retainAll(Collection c)ArrayList<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
list.retainAll(Arrays.asList("a", "b")); // 保留 "a" 和 "b"
containsAll(Collection c)true。ArrayList<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
boolean contains = list.containsAll(Arrays.asList("a", "b")); // 检查是否包含 "a" 和 "b"
clear()ArrayList<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
list.clear(); // 清空列表
sort(List list) ArrayList<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5));
Collections.sort(list); // 对列表排序
reverse(List list)功能：反转列表中元素的顺序。
用例：
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
Collections.reverse(list); // 列表变为 [3, 2, 1]
shuffle(List list)ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
Collections.shuffle(list); // 打乱列表元素的顺序
binarySearch(List> list, T key)ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
Collections.sort(list);
int index = Collections.binarySearch(list, 3); // 在列表中查找数字 3 的索引
copy(List dest, List src)ArrayList<Integer> src = new ArrayList<>(Arrays.asList(1, 2, 3));
ArrayList<Integer> dest = new ArrayList<>(Arrays.asList(5, 6, 7, 8));
Collections.copy(dest, src); // 将 src 复制到 dest
fill(List list, T obj)ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
Collections.fill(list, 0); // 将列表中的所有元素替换为 0
addAll(Collection c, T... elements)ArrayList<Integer> list = new ArrayList<>();
Collections.addAll(list, 1, 2, 3, 4); // 向列表中添加多个元素
removeAll(Collection c, Object o)ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 2, 1));
list.removeAll(Collections.singleton(1)); // 删除所有1
copy(List dest, List src)ArrayList<Integer> src = new ArrayList<>(Arrays.asList(1, 2, 3));
ArrayList<Integer> dest = new ArrayList<>(Arrays.asList(4, 5, 6, 7));
Collections.copy(dest, src); // 将src的内容复制到dest
fill(List list, T obj)ArrayList<String> list = new ArrayList<>(Arrays.asList("apple", "banana", "cherry"));
Collections.fill(list, "filled"); // 将所有元素替换为 "filled"
replaceAll(List list, T oldVal, T newVal) ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 1, 3));
Collections.replaceAll(list, 1, 99); // 将所有1替换为99
frequency(Collection c, Object o)ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 1, 3));
int freq = Collections.frequency(list, 1); // 计算1在列表中出现的次数
13， disjoint(Collection c1, Collection c2)
ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(1, 2, 3));
ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(4, 5, 6));
boolean isDisjoint = Collections.disjoint(list1, list2); // 检查两个列表是否没有共同元素