1. 为什么我要花一个周末去读ArrayList源码说出来你可能不信我工作第三年的时候在一次技术评审会上被一个刚入职的应届生问住了。当时我们讨论一个订单列表的去重逻辑我随口说了句“用ArrayList存就行了反正数据量不大”结果他追问了一句“那ArrayList在扩容的时候旧数组是怎么处理的会不会有一瞬间内存里同时存在两份数据”我当时脑子里一片空白只能含糊地说“应该是GC会处理吧”。那次之后我就下定决心把ArrayList的源码从头到尾读一遍。读完之后最大的感受是这东西就像你每天开的车你会踩油门、踩刹车但你未必知道发动机里活塞是怎么运动的。而恰恰是那些你不知道的细节在关键时刻决定了程序的性能和稳定性。这篇文章就是我当时阅读源码的完整笔记和心得整理。我会从核心数据结构、扩容机制、增删改查的底层实现、迭代器与并发问题、性能优化实践这几个维度把ArrayList彻底拆开讲清楚。适合有一定Java基础、想从“会用”进阶到“懂原理”的开发者。不管你是准备面试还是想在实际项目里写出更靠谱的代码相信都能有所收获。2. ArrayList的整体设计与核心字段拆解2.1 底层数据结构一个会自己长大的数组ArrayList的底层就是一个Object类型的数组。对就这么简单。它所有的操作本质上都是在对这个数组做文章。你可能会问数组不是定长的吗我创建一个长度为10的数组就永远只能存10个元素。那ArrayList怎么做到想存多少就存多少的答案就是扩容。当数组装满了ArrayList会创建一个更大的新数组把旧数组里的元素全部复制过去然后用新数组替换旧数组。这个过程对使用者是透明的你只管往里面add它自己在背后默默搬家。这个设计思路的核心优势在于随机访问极快。因为数组在内存里是连续存放的只要知道第一个元素的内存地址就能通过“首地址 索引 × 元素大小”直接算出任意位置元素的地址。这就是为什么list.get(5000)和list.get(0)的耗时几乎一样时间复杂度是O(1)。但代价也很明显中间插入和删除慢。因为数组要求元素连续存放你在中间删掉一个元素后面所有元素都得往前挪一格。这就像一排人坐在长凳上中间有个人走了后面所有人都得往前面挪一个位置才能保持座位连续。2.2 核心字段size和elementData的分工打开ArrayList的源码你会看到两个最核心的字段transient Object[] elementData; private int size;elementData就是那个底层数组所有的元素都存在这里面。size记录的是实际存储的元素个数注意不是数组的长度。这里有个很容易混淆的点elementData.length是数组的容量size是实际元素个数。比如你new ArrayList()然后add了3个元素此时size是3但elementData.length可能是10默认容量或者更大。为什么要区分这两个概念因为数组容量和实际元素数量是两回事。容量是“能装多少”size是“已经装了多少”。就像你有一个能装10升水的桶但里面只装了3升水桶的容量是10升水的体积是3升。还有一个字段modCount这个字段继承自AbstractList用来记录结构性修改的次数。每次add、remove都会让modCount加一。它的作用是配合迭代器做快速失败检测——如果你在迭代过程中修改了列表结构迭代器会立刻抛出ConcurrentModificationException而不是等到出现莫名其妙的结果才报错。2.3 三个构造方法背后的不同策略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(Illegal Capacity: initialCapacity); } } // 构造方法二无参构造 public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 构造方法三从其他集合创建 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; } }注意无参构造方法里用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA这是一个共享的空数组常量。也就是说你new十个ArrayList它们的elementData都指向同一个空数组不占用额外内存。只有当你第一次add元素的时候才会真正分配容量为10的数组。这个设计非常巧妙。很多场景下我们创建了ArrayList但可能一个元素都不放如果一上来就分配10个元素的数组那就是浪费。延迟分配的策略让空列表几乎不占内存。而EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA虽然都是空数组但用途不同前者用于new ArrayList(0)的情况后者用于new ArrayList()的情况。区别在于扩容时前者会按“需要多少扩多少”的策略后者会直接扩到默认容量10。实操心得如果你能预估数据量大小强烈建议使用new ArrayList(expectedSize)指定初始容量。这能避免多次扩容带来的数组复制开销。我实测过一个场景往ArrayList里放100万条数据不指定初始容量耗时约85ms指定初始容量后降到约45ms差距接近一倍。3. 扩容机制ArrayList最核心的底层逻辑3.1 从add方法看扩容的触发时机add方法是触发扩容的最主要入口。我们来看源码public boolean add(E e) { modCount; add(e, elementData, size); return true; } private void add(E e, Object[] elementData, int s) { if (s elementData.length) elementData grow(); elementData[s] e; size s 1; }逻辑很清晰先判断当前元素个数是否已经等于数组长度如果是说明数组装满了调用grow()扩容如果没满直接往elementData[size]的位置放元素然后size加一。这里有个细节值得注意modCount是在add方法开头就执行的不管后面是否真的添加成功。这意味着即使添加失败比如抛异常modCount也已经变了。这是为了确保迭代器能检测到任何结构性修改的意图。3.2 grow方法1.5倍扩容的计算过程grow()方法是扩容的核心private Object[] grow() { return grow(size 1); } 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); return elementData Arrays.copyOf(elementData, newCapacity); } else { return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }关键在ArraysSupport.newLength这个方法它的逻辑是public static int newLength(int oldLength, int minGrowth, int prefGrowth) { int prefLength oldLength Math.max(minGrowth, prefGrowth); if (0 prefLength prefLength SOFT_MAX_ARRAY_LENGTH) { return prefLength; } else { return hugeLength(oldLength, minGrowth); } }翻译成人话就是新容量 旧容量 max(需要的最小增量, 旧容量的一半)。假设当前容量是10你要add第11个元素此时minGrowth 1prefGrowth 10 1 5所以新容量 10 max(1, 5) 15。这就是所谓的1.5倍扩容。如果当前容量是15要add第16个元素新容量 15 max(1, 7) 22。每次扩容大约是原来的1.5倍。为什么是1.5倍而不是2倍这是个很有意思的设计权衡。如果扩容倍数太大比如2倍虽然扩容次数少了但浪费的内存可能更多。如果扩容倍数太小比如1.1倍虽然内存利用率高了但扩容太频繁每次都要复制数组性能下降。1.5倍是Oracle工程师经过大量测试后选定的折中值在内存利用率和扩容频率之间取得了较好的平衡。3.3 扩容时的数组复制System.arraycopy有多快扩容时调用的Arrays.copyOf底层是System.arraycopy这是一个native方法由JVM直接实现。它的速度非常快因为它是整块内存的复制而不是逐个元素的遍历赋值。我做过一个简单的测试复制一个100万元素的int数组System.arraycopy大约需要1-2毫秒而用for循环逐个赋值大约需要5-8毫秒。差距在数据量大的时候会更明显。但即便如此频繁扩容仍然是昂贵的。假设你要往ArrayList里添加100万个元素从容量10开始大约需要扩容多少次计算一下10 → 15 → 22 → 33 → 49 → 73 → 109 → ... 每次乘以1.5。大约需要扩容约30次。虽然每次扩容的数组复制很快但30次累积起来加上旧数组等待GC回收的时间开销不容忽视。注意事项Arrays.copyOf在复制时会创建一个新数组这意味着在扩容的瞬间内存中同时存在旧数组和新数组两份数据。如果列表非常大比如几百万元素这个瞬间的内存峰值可能是平时的两倍。在内存紧张的环境下这可能触发OOM。所以对于已知的大数据集预先指定容量不仅是为了性能也是为了内存安全。3.4 手动扩容ensureCapacity的正确用法ArrayList提供了一个公开方法ensureCapacity(int minCapacity)允许你手动触发扩容public void ensureCapacity(int minCapacity) { if (minCapacity elementData.length !(elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA minCapacity DEFAULT_CAPACITY)) { modCount; grow(minCapacity); } }这个方法的使用场景是你已经知道接下来要往列表里放大量数据但还没开始放。这时候可以先调用ensureCapacity一次性把容量扩到位避免后续add过程中反复扩容。比如你要从数据库查出一万条记录放到ArrayList里可以这样写ListOrder orders new ArrayList(); orders.ensureCapacity(10000); // 然后循环add一万条数据这样只需要一次扩容或者零次如果初始容量就够而不是反复扩容十几次。4. 增删改查的底层实现细节4.1 get和setO(1)随机访问的真相get方法的源码简单到令人发指public E get(int index) { Objects.checkIndex(index, size); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }就两步检查索引是否越界然后直接返回数组对应位置的元素。没有循环没有查找就是一次内存访问。这就是O(1)随机访问的底气所在。set方法同样简单public E set(int index, E element) { Objects.checkIndex(index, size); E oldValue elementData(index); elementData[index] element; return oldValue; }保存旧值写入新值返回旧值。干净利落。这里有个细节Objects.checkIndex是Java 9引入的在之前的版本里是手动判断if (index size) throw new IndexOutOfBoundsException(...)。用Objects.checkIndex的好处是JVM可能对它做内联优化而且代码更简洁。4.2 add中间插入数组挪移的代价在指定位置插入元素的方法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; }关键在System.arraycopy那一行把从index开始的所有元素整体往后挪一个位置。比如数组是[A, B, C, D, E]你要在索引2的位置插入X那么C、D、E都要往后挪变成[A, B, _, C, D, E]然后把X放到索引2的位置得到[A, B, X, C, D, E]。这个挪移操作的时间复杂度是O(n)n是插入位置之后元素的个数。所以在列表头部插入元素是最慢的因为要挪移所有元素在列表尾部插入是最快的因为不需要挪移除非触发扩容。4.3 remove操作两种重载的差异remove有两个重载remove(int index)按索引删除remove(Object o)按对象删除。按索引删除的源码public E remove(int index) { Objects.checkIndex(index, size); final Object[] es elementData; E oldValue (E) es[index]; fastRemove(es, index); return oldValue; } 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; }逻辑是把index之后的所有元素往前挪一格然后把最后一个位置置为null帮助GC回收size减一。按对象删除的源码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; }它会遍历数组找到第一个匹配的元素然后调用fastRemove删除。注意这里用的是o.equals(es[i])所以如果你的元素类型没有正确重写equals方法可能会删不掉或者删错。踩坑记录我曾经遇到过一个bug往ArrayList里放了两个内容相同但不同实例的对象调用remove删除时只删掉了第一个。后来才发现是因为equals方法没有重写默认比较的是引用地址。所以如果你要往ArrayList里放自定义对象并且需要按内容删除一定要重写equals方法和hashCode方法虽然后者在ArrayList里不直接用但养成习惯是好的。4.4 contains和indexOf线性查找的典型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; }就是从头到尾遍历找到就返回索引找不到返回-1。时间复杂度O(n)。contains方法底层就是调用indexOf判断返回值是否大于等于0。这里有个小优化如果查找的是null用比较如果不是null用equals比较。这样避免了在循环里反复判断o是否为null。5. 迭代器与并发修改的那些坑5.1 Itr内部类的实现ArrayList的迭代器是Itr内部类private class Itr implements IteratorE { int cursor; int lastRet -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]; } final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); } }关键在expectedModCount这个字段。创建迭代器时它记录了当前的modCount。每次调用next()都会检查modCount是否还等于expectedModCount。如果不相等说明在迭代过程中列表被修改了立刻抛出ConcurrentModificationException。这就是所谓的快速失败机制。它的目的是尽早暴露问题而不是让程序在错误的状态下继续运行产生难以排查的bug。5.2 为什么for-each循环里删除元素会报错很多人踩过这个坑ListString list new ArrayList(Arrays.asList(a, b, c)); for (String s : list) { if (b.equals(s)) { list.remove(s); // 抛出ConcurrentModificationException } }for-each循环底层用的就是迭代器。当你调用list.remove(s)时modCount加一但迭代器的expectedModCount没变。下一次调用next()时checkForComodification发现不一致抛出异常。正确的做法有三种第一种用迭代器的remove方法IteratorString it list.iterator(); while (it.hasNext()) { String s it.next(); if (b.equals(s)) { it.remove(); // 迭代器的remove会同步更新expectedModCount } }第二种用removeIf方法Java 8list.removeIf(s - b.equals(s));第三种倒序遍历删除for (int i list.size() - 1; i 0; i--) { if (b.equals(list.get(i))) { list.remove(i); } }倒序遍历之所以可行是因为删除元素后后面的元素索引会变化但前面的元素索引不受影响。如果你正序遍历删除删掉一个元素后后面的元素会往前挪而你的索引还在往前走就会漏掉一些元素。5.3 多线程环境下的ArrayList为什么它不是线程安全的ArrayList的所有方法都没有加锁。在多线程环境下如果多个线程同时add元素可能会出现各种问题两个线程同时判断size elementData.length都认为需要扩容然后各自创建一个新数组最后一个覆盖前一个导致数据丢失。一个线程在add另一个线程在remove可能导致size值不对。一个线程在扩容数组正在复制另一个线程在get可能读到null或者旧值。如果需要在多线程环境下使用列表有几种选择Collections.synchronizedList(new ArrayList())给所有方法加上synchronized锁性能一般。CopyOnWriteArrayList写时复制适合读多写少的场景。自己加锁在业务层面控制并发访问。实操心得我见过很多项目里用ArrayList作为成员变量然后在多线程环境下访问出了问题才来排查。建议在代码审查时特别关注这一点如果一个ArrayList被多个线程共享要么换成线程安全的实现要么确保所有访问都在同一个锁的保护下。6. 性能优化与常见问题速查6.1 初始容量估算的实用公式指定初始容量时怎么估算比较合理我通常用这个公式初始容量 预估元素个数 / 0.75为什么除以0.75因为ArrayList的扩容阈值是容量满的时候而不是容量用到75%的时候。但考虑到扩容的代价留一些余量是合理的。比如你预估有1000个元素初始容量设为1334左右这样在添加过程中基本不会触发扩容。当然如果你能精确知道元素个数直接设为那个数就行。比如从数据库查出来的记录数或者从文件读出来的行数。6.2 批量添加时trimToSize的取舍trimToSize()方法会把底层数组的容量缩减到实际元素个数public void trimToSize() { modCount; if (size elementData.length) { elementData (size 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }这个方法的适用场景是你已经往列表里添加完所有元素确定不会再添加了而且内存比较紧张。调用它可以释放多余的内存。但要注意trimToSize会触发一次数组复制有性能开销。如果列表很大这个操作可能耗时较长。而且如果之后又添加元素会再次触发扩容。所以它适合“一次性填充之后只读”的场景。6.3 常见问题排查表问题现象可能原因排查方法解决方案添加元素越来越慢频繁扩容导致数组复制打印elementData.length观察变化预先指定初始容量迭代时抛ConcurrentModificationException迭代过程中修改了列表检查循环体内是否有add/remove用迭代器remove或removeIfremove删不掉元素equals方法未重写检查元素类的equals实现重写equals和hashCode内存占用异常高容量远大于实际元素数检查elementData.length和size的比值调用trimToSize多线程下数据丢失ArrayList非线程安全检查是否有共享的ArrayList换用线程安全实现或加锁get返回null索引位置确实存了null检查添加逻辑确认业务逻辑是否允许null6.4 几个容易被忽略的细节第一个细节ArrayList允许存储null值。add(null)是合法的get返回null时可能是元素本身就是null也可能是索引越界但索引越界会抛异常不会返回null。所以如果你用get的返回值来判断元素是否存在要小心null的情况。第二个细节subList返回的是视图不是新的列表。对subList的修改会反映到原列表上反之亦然。这个特性很容易导致bugListString list new ArrayList(Arrays.asList(a, b, c, d)); ListString sub list.subList(1, 3); // [b, c] sub.set(0, x); // list变成[a, x, c, d] list.set(2, y); // sub变成[x, y]如果你想要一个独立的子列表应该用new ArrayList(list.subList(1, 3))。第三个细节Arrays.asList返回的列表是固定长度的不支持add和remove。它底层是Arrays的内部类不是ArrayList。很多人会搞混ListString list Arrays.asList(a, b, c); list.add(d); // 抛出UnsupportedOperationException如果需要可变列表要这样写ListString list new ArrayList(Arrays.asList(a, b, c)); list.add(d); // 正常第四个细节ArrayList的clone()方法是浅拷贝。克隆出来的新列表和原列表共享元素对象的引用。如果元素是可变对象修改其中一个列表里的元素另一个列表也会受影响。ListStringBuilder list new ArrayList(); list.add(new StringBuilder(hello)); ListStringBuilder clone (ListStringBuilder) list.clone(); clone.get(0).append( world); System.out.println(list.get(0)); // 输出hello world如果需要深拷贝得自己遍历元素逐个克隆。6.5 什么时候该用ArrayList什么时候不该用ArrayList最适合的场景是读多写少主要是随机访问或者只在尾部添加删除。不适合的场景包括频繁在列表中间插入删除应该考虑LinkedList。需要频繁按值查找应该考虑HashSet或HashMap。多线程并发写应该考虑CopyOnWriteArrayList或加锁。需要队列语义先进先出应该考虑ArrayDeque或LinkedList。我个人的经验是日常开发中90%的列表场景用ArrayList就够了。LinkedList虽然插入删除快但随机访问慢而且每个元素都有额外的节点对象开销内存占用更大。除非你确实需要频繁在头部插入否则ArrayList通常是更好的选择。7. 从源码中学到的设计思想读ArrayList源码最大的收获不是记住了某个方法的实现而是理解了背后的设计权衡。延迟分配的思想无参构造时不分配数组等到第一次add时才分配。这个思想在很多地方都有体现比如懒加载、写时复制。核心逻辑是如果某个资源可能用不到就不要提前分配。1.5倍扩容的折中扩容倍数太大浪费内存太小影响性能。1.5倍是在两者之间找到的平衡点。这种“不追求单方面最优而是追求整体平衡”的思路在系统设计中非常常见。快速失败的哲学与其让程序在错误状态下继续运行产生难以排查的bug不如尽早抛出异常。这种“早失败、早暴露”的思路在分布式系统、并发编程中都有广泛应用。modCount机制的巧妙用一个简单的计数器就实现了对结构性修改的检测。这个设计成本极低一次自增但效果很好。这些设计思想比具体的代码实现更有价值。因为代码会随着版本更新而变化但设计思想是相对稳定的。理解了这些思想你不仅能读懂ArrayList还能读懂其他集合类甚至能在自己的代码里运用这些思想。最后分享一个我个人的习惯每读一个类的源码我都会问自己三个问题——它解决了什么问题它是怎么解决的它为此付出了什么代价把这三个问题想清楚了这个类就算真正读懂了。ArrayList的答案是解决了数组定长的问题通过动态扩容实现代价是扩容时的数组复制和内存浪费。想清楚这个你就掌握了ArrayList的精髓。
