JAVA集合—ArrayList源码深度解析

前言ArrayList 可能是每个 Java 开发者最早接触、使用最频繁的集合类。但你是否真正理解过它的内部实现比如扩容机制是什么为什么扩容是 1.5 倍add()和remove()的时间复杂度分别是多少本文基于 JDK 21 源码逐行分析 ArrayList 的核心实现覆盖日常开发中的高频知识点。文末附有常见问题汇总可直接跳转查阅。一、ArrayList 的类定义与继承关系public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable { java.io.Serial private static final long serialVersionUID 8683452581122892189L; }几个关键接口的含义ListE有序集合支持按索引访问RandomAccess标记接口没有方法表示支持快速随机访问。Collections.binarySearch()会根据这个标记决定使用索引遍历还是迭代器遍历Cloneable支持clone()方法浅拷贝Serializable支持序列化JDK 21 变化serialVersionUID增加了java.io.Serial注解这是 JDK 14 引入的用于标记序列化相关的字段和方法方便编译器检查。二、核心成员变量// 默认初始容量 private static final int DEFAULT_CAPACITY 10; // 空数组实例用于有参构造指定容量为 0 时使用 private static final Object[ ] EMPTY_ELEMENTDATA {}; // 默认空数组实例用于无参构造与 EMPTY_ELEMENTDATA 区分以便第一次 add 时知道该扩容到多少 private static final Object[ ] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; // 存储元素的底层数组注意用 transient 修饰不直接序列化 transient Object[ ] elementData; // 实际元素个数不是数组长度 private int size;源码细节为什么有两个空数组EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA都是空数组但作用不同new ArrayList()→ 使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次add时扩容到 10new ArrayList(0)→ 使用EMPTY_ELEMENTDATA第一次add时扩容到 1这样设计是为了让无参构造的 ArrayList 在第一次添加元素时就分配一个合理的容量10而不是逐步从 1 开始扩容。三、构造方法3.1 无参构造/** * 构造一个初始容量为 10 的空列表 * 实际上此时并没有创建长度为 10 的数组而是在第一次 add 时才分配 */ public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }注意这里用了懒初始化lazy initialization无参构造时底层数组是空的直到第一次添加元素才真正分配容量为 10 的数组。3.2 指定初始容量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); } }3.3 通过集合构造public ArrayList(Collection? extends E c) { Object[ ] a c.toArray(); if ((size a.length) ! 0) { if (c.getClass() ArrayList.class) { elementData a; } else { elementData Arrays.copyOf(a, size, Object[ ].class); } } else { elementData EMPTY_ELEMENTDATA; } }这里的设计意图是如果传入的就是ArrayList可以直接复用其toArray()返回的数组因为 ArrayList 的toArray()保证返回Object[ ]省去一次不必要的数组拷贝否则通过Arrays.copyOf做类型安全拷贝。四、add() 方法与扩容机制核心重点4.1 尾部添加add(E e)public boolean add(E e) { modCount; add(e, elementData, size); return true; } /** * 私有辅助方法将元素添加到指定位置 * 将 elementData 和 size 作为参数传入避免重复读取成员变量JIT 优化友好 */ private void add(E e, Object[ ] elementData, int s) { if (s elementData.length) elementData grow(); elementData[s] e; size s 1; }注意这里的设计modCount放在公共方法中私有辅助方法elementData, int s) 将elementData和size作为参数传入避免重复读取成员变量对 JIT 编译更友好。当s elementData.length数组满了时调用grow()扩容。扩容的本质是新建一个更大的数组然后把旧数组的所有元素拷贝过去。具体过程根据 1.5 倍规则计算新容量通过ArraysSupport.newLength()调用Arrays.copyOf(elementData, newCapacity)创建新数组并拷贝数据将elementData引用指向新数组旧数组被 GC 回收return elementData Arrays.copyOf(elementData, newCapacity);这行代码是扩容最核心的操作——底层通过System.arraycopy()完成数组拷贝是一次 O(n) 的操作。这也是为什么扩容频繁发生会影响性能建议能预估元素数量时提前分配好容量。4.2 grow() —— 扩容的核心方法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)]; } } private Object[ ] grow() { return grow(size 1); }扩容计算通过ArraysSupport.newLength()完成// jdk.internal.util.ArraysSupport 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 { return hugeLength(oldLength, minGrowth); } }核心逻辑仍然是 1.5 倍扩容prefGrowth oldCapacity 1但用Math.max(minGrowth, prefGrowth)统一处理了1.5 倍不够时直接用 minCapacity的情况代码更简洁。无参构造的首次扩容走独立路径4.3 扩容流程图add(element) │ ├─ modCount │ ▼ add(e, elementData, size) │ └─ size elementData.length │ ├─ 否 → 直接赋值elementData[size] e; size │ └─ 是 → grow() │ ▼ grow(size 1) │ ├─ 无参构造首次 add │ └─ 是 → new Object[max(10, minCapacity)] │ └─ 否 → ArraysSupport.newLength(oldCap, minGrowth, oldCap 1) │ ▼ newCapacity oldCap max(minGrowth, oldCap 1) // 1.5 倍 │ ▼ Arrays.copyOf(elementData, newCapacity)4.4 扩容计算示例次数操作size扩容前容量扩容后容量是否发生扩容1add 第 1 个元素1010是首次扩容到 102~10add 第 2~10 个元素2~101010否11add 第 11 个元素111015是10 max(1, 5) 1516add 第 16 个元素161522是15 max(1, 7) 2223add 第 23 个元素232233是22 max(1, 11) 334.5 指定位置插入add(int index, E element)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; }注意这里使用局部变量s和elementData缓存成员变量值减少字段访问次数对 JIT 编译友好。扩容判断直接在方法内完成逻辑清晰。时间复杂度O(n)因为需要通过System.arraycopy移动元素。最坏情况在头部插入需要移动所有元素。五、get() 与 set() 方法public E get(int index) { Objects.checkIndex(index, size); return elementData(index); } public E set(int index, E element) { Objects.checkIndex(index, size); E oldValue elementData(index); elementData[index] element; return oldValue; } SuppressWarnings(unchecked) E elementData(int index) { return (E) elementData[index]; }时间复杂度O(1)这正是 ArrayList 实现RandomAccess接口的底气所在 —— 数组支持通过下标直接定位元素。注意Objects.checkIndex(index, size)同时检查index 0和index size并且是 JVM intrinsic 方法能够被 JIT 编译器识别为边界检查并进行消除优化性能很好。六、remove() 方法6.1 按索引删除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; }6.2 按对象删除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:标签配合break将搜索阶段和删除阶段分离——先定位元素找到后统一调用fastRemove代码结构清晰。6.3 fastRemove —— 统一的快速删除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; // clear to let GC do its work }fastRemove接收es 参数调用方已经缓存了数组引用避免重复读取成员变量对 JIT 友好的设计。关键点es[size newSize] null这行代码非常重要如果不置 null被删除的对象仍然被数组引用着导致无法被 GC 回收内存泄漏。注意remove(Object)只删除第一个匹配的元素并且使用equals()比较null 元素用。七、迭代器与 fail-fast 机制7.1 modCount 是什么modCount定义在AbstractList中记录集合被结构性修改的次数。所谓结构性修改指的是改变了集合大小的操作add、remove、clear 等而 set 不算。// 来自 AbstractList protected transient int modCount 0;7.2 迭代器源码public IteratorE iterator() { return new Itr(); } private class Itr implements IteratorE { int cursor; // 下一个要返回的元素索引 int lastRet -1; // 上一个返回的元素索引-1 表示还没开始 int expectedModCount modCount; // 创建迭代器时记录 modCount Itr() {} public boolean hasNext() { return cursor ! size; } SuppressWarnings(unchecked) 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]; } public void remove() { if (lastRet 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor lastRet; lastRet -1; expectedModCount modCount; // 同步 modCount } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } // fail-fast 的核心检查 final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); } }7.3 fail-fast 到底起到了什么作用fail-fast 不是快速失败就完了它的核心作用是让程序在并发修改或遍历删除的场景下立即暴露问题而不是悄悄产生不可预期的结果。举个例子如果一个线程在遍历 ArrayList 的同时另一个线程在往里面 add 元素没有 fail-fast 的情况下遍历线程可能读到不完整的中间态——漏掉元素、读到重复元素、甚至直接数组越界。这些 bug 非常隐蔽线上很难排查。fail-fast 通过抛出ConcurrentModificationException把问题提前暴露让开发者在开发阶段就能发现并修复。同样遍历时直接调用list.remove()而不使用迭代器的remove()也会导致遍历时漏掉元素或跳过检查。fail-fast 同样会抛出异常提醒你使用正确的方式。总结一句话fail-fast 是一种防御性设计宁可让程序崩溃也不要让它在错误的状态下继续运行。7.4 fail-fast 触发场景// ❌ 错误写法遍历时直接调用 list.remove() ListString list new ArrayList(Arrays.asList(a, b, c)); for (String s : list) { if (b.equals(s)) { list.remove(s); // 抛出 ConcurrentModificationException } } // ✅ 正确写法 1使用迭代器的 remove() IteratorString it list.iterator(); while (it.hasNext()) { if (b.equals(it.next())) { it.remove(); // 安全删除会同步 expectedModCount } } // ✅ 正确写法 2使用 removeIf()最简洁 list.removeIf(b::equals); // ✅ 正确写法 3倒序遍历删除 for (int i list.size() - 1; i 0; i--) { if (b.equals(list.get(i))) { list.remove(i); } }原理for-each 底层使用迭代器迭代器创建时记录了expectedModCount。直接调用list.remove()会修改modCount而迭代器的expectedModCount不变下次next()调用时检测到两者不一致抛出异常。九、序列化机制什么是序列化序列化Serialization是把 Java 对象转换成字节流的过程这样才能把对象写入文件、通过网络传输、或者存到缓存如 Redis中。反序列化则是把字节流恢复成 Java 对象的过程。ArrayList 为什么要自定义序列化你可能注意到了elementData被transient修饰按理说不会被序列化。但 ArrayList 实际上是可以序列化的原因在于它自定义了序列化逻辑。这么做的目的是只序列化有效元素而不是整个底层数组。举个具体的例子一个 ArrayList 的 capacity 是 1000但实际只存了 5 个元素。如果直接序列化整个数组会浪费 995 个空位的存储空间。通过自定义序列化只写入这 5 个有效元素大大节省了存储空间和网络传输开销。自定义序列化源码java.io.Serial private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { int expectedModCount modCount; s.defaultWriteObject(); // 写入 size而非 capacity保持与 clone() 的行为兼容 s.writeInt(size); // 只序列化有效元素而不是整个数组节省空间 for (int i 0; i size; i) { s.writeObject(elementData[i]); } if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } } java.io.Serial private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); s.readInt(); // 读取写入的 size此处未直接使用由 defaultReadObject 恢复 if (size 0) { SharedSecrets.getJavaObjectInputStreamAccess() .checkArray(s, Object[ ].class, size); Object[ ] elements new Object[size]; for (int i 0; i size; i) { elements[i] s.readObject(); } elementData elements; } else if (size 0) { elementData EMPTY_ELEMENTDATA; } else { throw new java.io.InvalidObjectException(Invalid size: size); } }readObject中有几个值得注意的设计先创建局部数组elements全部读取完毕后再赋值给elementData避免反序列化过程中elementData处于半初始化状态增加了SharedSecrets安全检查防止恶意构造超大数组导致 OOM还有size 0的防御性检查抛出InvalidObjectException。总结一下序列化的作用使 ArrayList 能够被写入文件、通过网络传输、或者存入缓存通过transient 自定义序列化只序列化有效元素节省空间和带宽readObject中的安全检查防止反序列化攻击十、trimToSize() 与 ensureCapacity()// 将数组容量缩减到实际元素个数释放多余空间 public void trimToSize() { modCount; if (size elementData.length) { elementData (size 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } // 预分配容量避免频繁扩容 public void ensureCapacity(int minCapacity) { if (minCapacity elementData.length !(elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA minCapacity DEFAULT_CAPACITY)) { modCount; grow(minCapacity); } }ensureCapacity的判断逻辑很直接只要minCapacity elementData.length且不是无参构造 请求容量 ≤ 10的情况就触发扩容。实际应用场景// 如果你明确知道要添加 10 万个元素提前分配容量避免多次扩容和数组拷贝 ArrayListInteger list new ArrayList(); list.ensureCapacity(100000); // 一次性分配 for (int i 0; i 100000; i) { list.add(i); } // 或者直接在构造时指定 ArrayListInteger list2 new ArrayList(100000);十一、ArrayList 常见使用坑坑 1修改 subList 会影响原列表subList()返回的不是一个新的 ArrayList而是原列表的一个视图内部类SubList它们共享同一个底层数组。ListString list new ArrayList(Arrays.asList(a, b, c, d, e)); ListString sub list.subList(1, 3); // [b, c] // 修改 subList 会影响原 list sub.set(0, X); System.out.println(list); // [a, X, c, d, e] // 对原列表做结构性修改后subList 的操作会报错 list.add(f); sub.get(0); // ConcurrentModificationException如果需要独立的子列表ListString safeSub new ArrayList(list.subList(1, 3));坑 2遍历过程中直接调用 list.remove()for-each 循环底层使用迭代器遍历期间直接调用list.remove()会修改modCount导致迭代器检测到不一致而抛出异常。// ❌ 会抛 ConcurrentModificationException for (String s : list) { if (b.equals(s)) { list.remove(s); } } // ✅ 正确写法 list.removeIf(b::equals);坑 3初始化时不预估容量// ❌ 频繁触发扩容和数组拷贝 ListUser users new ArrayList(); for (int i 0; i 100000; i) { users.add(fetchUser(i)); } // ✅ 预估容量避免多次扩容 ListUser users new ArrayList(100000);坑 4Arrays.asList() 返回的 List 不支持 add/removeListString list Arrays.asList(a, b, c); list.add(d); // UnsupportedOperationExceptionArrays.asList()返回的是java.util.Arrays$ArrayListArrays 的内部类不是java.util.ArrayList它的底层就是传入的数组不支持增删操作。正确做法ListString list new ArrayList(Arrays.asList(a, b, c));坑 5clone() 是浅拷贝不是深拷贝ListUser original new ArrayList(); original.add(new User(Alice)); ListUser cloned (ListUser) original.clone(); cloned.get(0).setName(Bob); System.out.println(original.get(0).getName()); // Bob — 原列表也被修改了clone()只复制了数组引用数组中的元素对象还是同一个。如果需要深拷贝需要手动对每个元素进行深拷贝。坑 6contains() 和 remove(Object) 依赖 equals()ListUser users new ArrayList(); users.add(new User(Alice)); // 如果 User 没有重写 equals()下面这行会返回 false boolean found users.contains(new User(Alice));contains()和remove(Object)内部使用equals()比较。如果元素类没有正确重写equals()方法只比较了引用地址而非字段内容会导致明明有却查不到的问题。坑 7线程不安全的 ArrayList 被多线程使用ListString list new ArrayList(); // 多线程同时写入 for (int i 0; i 10; i) { new Thread(() - { for (int j 0; j 1000; j) { list.add(Thread.currentThread().getName()); } }).start(); } // 最终 list.size() 很可能不是 10000 // 甚至可能抛出 ArrayIndexOutOfBoundsException多线程环境下应使用Collections.synchronizedList()或CopyOnWriteArrayList或者手动加锁。十二、ArrayList vs Vector vs CopyOnWriteArrayList特性ArrayListVectorCopyOnWriteArrayList线程安全否是synchronized是synchronized 写时复制扩容比例1.5 倍2 倍每次写都新建数组读性能高低锁竞争极高无锁写性能高低低每次复制数组迭代安全fail-fastfail-fast安全快照迭代推荐度⭐⭐⭐❌ 已过时⭐⭐读多写少场景十三、常见问题深入解答Q1ArrayList 的默认初始容量是多少怎么扩容的默认初始容量是 10但无参构造时实际是空数组第一次 add 才分配 10。扩容策略是 1.5 倍通过ArraysSupport.newLength(oldCapacity, minGrowth, oldCapacity 1)计算新容量核心逻辑是oldCapacity Math.max(minGrowth, oldCapacity 1)最后通过Arrays.copyOf()将旧数组元素拷贝到新数组。Q2为什么扩容是 1.5 倍而不是 2 倍这是空间和时间的权衡。扩容倍数太小如 1.2 倍扩容次数多频繁的数组拷贝影响性能扩容倍数太大如 2 倍浪费的内存空间多。1.5 倍是一个实践中的最优折中。另外使用位运算 1比除法更高效。对比Vector 的扩容是 2 倍空间利用率不如 ArrayList。Q3ArrayList 和 LinkedList 有什么区别维度ArrayListLinkedList底层结构动态数组双向链表随机访问O(1)支持 RandomAccessO(n)需要遍历头部插入O(n)需移动所有元素O(1)尾部插入均摊 O(1)O(1)中间插入O(n)O(n)定位 O(n) 插入 O(1)内存占用连续内存有未使用的预留空间每个节点额外存储两个指针CPU 缓存友好数组连续存储不友好节点分散在堆内存结论绝大多数场景优先选 ArrayList。LinkedList 只在频繁头部插入/删除且不需要随机访问的场景才有优势实际开发中这种场景很少。Q4ArrayList 是线程安全的吗如何保证线程安全不是线程安全的。保证线程安全有三种方式// 方式1Collections.synchronizedList包装所有方法加 synchronized ListString syncList Collections.synchronizedList(new ArrayList()); // 方式2CopyOnWriteArrayList读多写少场景推荐 ListString cowList new CopyOnWriteArrayList(); // 方式3手动加锁 synchronized (list) { list.add(element); }Q5为什么 elementData 用 transient 修饰因为elementData数组的长度capacity通常大于实际元素个数size直接序列化整个数组会浪费空间。ArrayList 通过自定义writeObject()/readObject()方法只序列化有效的size个元素节省存储空间和网络带宽。Q6遍历 ArrayList 时如何安全删除元素// 方法1使用迭代器的 remove() IteratorString it list.iterator(); while (it.hasNext()) { if (condition(it.next())) { it.remove(); } } // 方法2使用 removeIf()最简洁 list.removeIf(item - condition(item)); // 方法3倒序 for 循环 for (int i list.size() - 1; i 0; i--) { if (condition(list.get(i))) { list.remove(i); } }直接在 for-each 循环中调用list.remove()会导致ConcurrentModificationException因为 for-each 底层使用迭代器而list.remove()会修改modCount导致迭代器检测到不一致。Q7subList() 返回的是新集合吗不是。subList()返回的是原 ArrayList 的一个视图共享底层数组。对子列表的修改会反映到原列表对原列表的结构性修改会导致子列表操作抛出ConcurrentModificationException。如果需要独立副本ListString independent new ArrayList(list.subList(1, 3));Q8如何在创建 ArrayList 时优化性能如果能预估元素数量在构造时指定初始容量避免多次扩容带来的数组拷贝开销// 不推荐默认容量 10可能多次扩容 ListUser users new ArrayList(); // 推荐已知大约需要 1000 个元素 ListUser users new ArrayList(1000);阿里开发规约也建议集合初始化时指定集合初始值大小。Q9Arrays.asList() 返回的 List 能 add 吗ListString list Arrays.asList(a, b, c); list.add(d); // UnsupportedOperationException不能。Arrays.asList()返回的是java.util.Arrays$ArrayListArrays 的内部类不是java.util.ArrayList它不支持add()和remove()。正确做法// 方式 1传统写法 ListString list new ArrayList(Arrays.asList(a, b, c)); // 方式 2JDK 9 不可变集合如果不需要修改 ListString immutable List.of(a, b, c); // 方式 3JDK 9 可变集合 ListString mutable new ArrayList(List.of(a, b, c));Q10ArrayList 的 clone() 是深拷贝还是浅拷贝public Object clone() { try { ArrayList? v (ArrayList?) super.clone(); v.elementData Arrays.copyOf(elementData, size); v.modCount 0; return v; } catch (CloneNotSupportedException e) { throw new InternalError(e); } }是浅拷贝。虽然创建了新的数组但数组中存储的对象引用没有被复制新旧 ArrayList 中的元素指向相同的对象。如果需要深拷贝需要手动对每个元素进行深拷贝。总结ArrayList 的核心就是一个 动态扩容的数组理解它只需要抓住几个关键点底层结构Object[ ]数组支持 O(1) 随机访问扩容机制1.5 倍扩容通过ArraysSupport.newLength()统一计算懒初始化无参构造时是空数组首次 add 才分配容量 10fail-fast通过modCount机制检测并发修改序列化优化transient 自定义序列化只存有效元素subList 是视图共享底层数组注意并发修改陷阱理解了这几个核心ArrayList 在开发中遇到的绝大多数问题都能从源码层面找到答案。本文为 Java 集合系列第 2 篇欢迎关注后续更新。 如果对你有帮助点赞收藏是对我最大的支持