ArrayList源码深度解析：动态数组扩容机制与核心方法实战

1. 先搞清楚ArrayList到底是怎样一个动态数组要说Java里哪个集合类最常用ArrayList绝对排前三。做Java这几年从新手入门到面试别人ArrayList的核心方法反复被拿出来讨论。它的名字直白——基于数组实现的一个List但真正能把add、remove、扩容机制讲清楚的人并不多。这篇笔记把ArrayList的核心方法从源码层面过了一遍结合我在实际项目里踩过的坑和面试时的高频问题写给正在学Java基础、准备面试或者工作中想深入理解集合原理的朋友。1.1 从字段看本质elementData、size、modCount提到ArrayList几乎每个Java初学者都会背一句基于数组实现的动态数组。但问到底层维护了什么字段就有人卡壳。直接看JDK源码以JDK8版本为例后续JDK9把elementData改成了私有内部类Object[]逻辑基本一致public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable { private static final int DEFAULT_CAPACITY 10; private static final Object[] EMPTY_ELEMENTDATA {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; transient Object[] elementData; private int size; }核心就三个东西elementData真正装元素的数组类型是Object[]。这解释了为什么ArrayList可以装任意类型——泛型在编译期擦除运行时就是Object数组。size已经放入的元素个数不是数组容量。modCount继承自AbstractList的字段记录结构性修改次数。很多面试官喜欢问size和capacity有什么区别答案就藏在这几个字段里。数组一旦创建长度固定ArrayList之所以能动态靠的是当size要超过数组长度时重新new一个更大的数组把旧数据拷过去。这就是扩容。这里有个容易忽略的细节elementData被声明为transient。序列化的时候不会把整个数组写出去后面我会专门讲这个设计的目的。1.2 ArrayList vs LinkedList vs Vector各自定位搞清楚ArrayList的定位最好的办法是拿它和LinkedList、Vector对比。集合类底层结构随机访问尾部插入中间插入/删除线程安全ArrayListObject[]数组O(1)均摊O(1)O(n)否LinkedList双向链表O(n)O(1)O(n)需要先查找否VectorObject[]数组O(1)均摊O(1)O(n)是方法加synchronized选择很简单读多写少、按索引访问多用ArrayList频繁头尾插入删除、几乎不按索引访问才考虑LinkedList。有的教材说LinkedList插入快那是没有限定的——ArrayList中间插入需要搬移元素LinkedList也需要先找到位置除非你正好在头尾附近操作。真实项目中ArrayList的出场率远高于LinkedList因为绝大多数写操作是往尾部追加。Vector基本可以忘了真要线程安全的数组列表用CopyOnWriteArrayList。JDK1.0的遗留类方法级同步性能差日常项目里几乎没有合理的使用场景。2. 扩容机制ArrayList最核心、面试最高频的考点2.1 add(E e)完整流程从添加元素到触发扩容面试题最爱考的就是ArrayList扩容。JDK8的add(E e)长这样public boolean add(E e) { ensureCapacityInternal(size 1); elementData[size] e; return true; }ensureCapacityInternal会先判断elementData是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。如果是说明是用new ArrayList()创建后还没加过元素此时把最小容量取为DEFAULT_CAPACITY和传入值的较大者也就是第一次add时真正扩容到10。注意这个懒加载设计JDK8里new ArrayList()时elementData只是一个空数组并不预分配10个容量。只有第一次add时才会真正创建一个容量为10的数组。目的很简单避免创建后没存几个元素就浪费内存。如果直接new ArrayList(0)或者new ArrayList(3)elementData会被初始化为对应容量的数组。确认所需容量后如果实际存储数组的length不够就调用grow(minCapacity)扩容。所以扩容真正的触发点只有一个添加元素时size 1大于elementData.length。2.2 newCapacity怎么计算1.5倍扩容的来龙去脉看一下grow方法JDK8private void grow(int minCapacity) { 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); }oldCapacity 1就是oldCapacity除以2所以新容量是老的1.5倍。比如10扩容到1515扩容到2215 722扩容到33。为什么是1.5倍而不是固定的每次加10也不是2倍、3倍这是空间和时间的折中扩容倍数太小比如每次1add触发扩容频率太高频繁Arrays.copyOf性能灾难。扩容倍数太大比如3倍数组一次性占很大内存但可能大部分空间闲置。1.5倍在数学上有个特性随着连续扩容数组总容量呈等比增长总复制成本均摊到每次添加是O(1)。业界常见做法还有C的vector是2倍扩容Java选1.5倍略微保守一点在省内存和减少复制之间取了个中庸值。如果扩容后容量还不够minCapacity比如你用ensureCapacity一次性要加很多元素直接用minCapacity作为新容量。接着如果新容量超过MAX_ARRAY_SIZEInteger.MAX_VALUE - 8会走到hugeCapacity目的是让容量不能超过Integer.MAX_VALUE否则抛OutOfMemoryError。MAX_ARRAY_SIZE减8是因为有些JVM实现会在对象头里放点东西留余量。实际扩容动作就是Arrays.copyOf(elementData, newCapacity)底层调System.arraycopynative方法整体复制很快但元素量大时依然有开销。几千、几万条数据没感觉百万级数据反复扩容就能明显感知到卡顿。2.3 addAll与ensureCapacity主动扩容的正确姿势批量添加时单条add假设不太适用。看addAll(Collection? extends E c)public boolean addAll(Collection? extends E c) { Object[] a c.toArray(); int numNew a.length; ensureCapacityInternal(size numNew); System.arraycopy(a, 0, elementData, size, numNew); size numNew; return numNew ! 0; }它是一次性计算出总共需要的size numNew然后只做一次扩容到目标长度再把集合整体拷进来。这就是为什么批量添加时用addAll比循环调用add效率高得多。循环add会触发多次扩容和多次数组复制而addAll最多一次扩容。如果你大概知道要加多少个元素可以在add之前调用ensureCapacity(minCapacity)手动扩容ArrayListString list new ArrayList(); list.ensureCapacity(1000); for (int i 0; i 1000; i) { list.add(String.valueOf(i)); }这样一开始就分配好容量避免扩容复制。新建时如果预估规模明确直接new ArrayList(1000)也行。很多人忽略这个数据量上万之后反复扩容的时间损耗很明显。建议把预估容量写进自己的编码习惯。3. 常用核心方法逐一拆解从源码到复杂度3.1 get/set随机访问为什么快ArrayList实现了RandomAccess接口这是个标记接口含义就是支持快速随机访问。get和set的实现极其简单public E get(int index) { rangeCheck(index); return elementData(index); } public E set(int index, E element) { rangeCheck(index); E oldValue elementData(index); elementData[index] element; return oldValue; }rangeCheck就是判断index是否大于等于size越界抛IndexOutOfBoundsException。注意这里没有显式检查负数负数时数组会抛出ArrayIndexOutOfBoundsException最终也是index相关异常。set会先取旧值再替换返回旧值。整个操作复杂度O(1)就是一次数组下标访问。这也是ArrayList在按索引查改场景下碾压LinkedList的原因——链表要一个个节点找过去才能到第n个位置。3.2 add(int index, E element)中间插入的代价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; }rangeCheckForAdd允许index等于size这样就是尾插。中间插入时为了保证连续性需要把从index开始的所有元素整体后移一位这个动作通过System.arraycopy完成它自己会处理重叠区域这是native优化过的内存移动不是逐元素赋值。但即便如此插入位置越靠前移动的元素越多最坏情况O(n)。这里有个细节arraycopy的src和dest是同一个数组JDK保证重叠时结果是正确的不必担心数据被覆盖。也因为它copy是整块移动时间复杂度虽然O(n)但常数特别小通常比LinkedList边遍历边插入还要快。这就是我前面说的别盲目迷信LinkedList插入快。3.3 remove按索引删和按对象删的区别按索引删除public E remove(int index) { rangeCheck(index); modCount; E oldValue elementData(index); int numMoved size - index - 1; if (numMoved 0) System.arraycopy(elementData, index1, elementData, index, numMoved); elementData[--size] null; return oldValue; }同样需要搬移后续所有元素最坏O(n)。删除最后一个元素时numMoved为0只有一步把size减1并把最后一个位置置null。这里置null很关键如果不把elementData[--size]设为null数组最后一个位置还残留着对象引用会导致这个对象无法被GC回收虽然size变小了但引用链还在。这就是内存泄漏的隐患ArrayList官方特意做了这一步。按对象删除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; }注意两个点允许删除null元素单独开了个null分支。用的是equals比较而不是所以remove(a)删除的是和a相等的元素如果你往里面放了内容相同但不同对象的字符串也能删掉第一个匹配的。只删除第一个匹配后面重复的需要循环删或者用removeAll。fastRemove和remove(int index)逻辑类似只是不做index合法性检查也不返回旧值。3.4 indexOf/contains线性查找的效率边界public int indexOf(Object o) { if (o null) { for (int i 0; i size; i) if (elementData[i]null) return i; } else { for (int i 0; i size; i) if (o.equals(elementData[i])) return i; } return -1; }contains其实就是indexOf 0。这是一个典型的线性扫描时间复杂度O(n)ArrayList对按值查找其实不占优势。如果频繁需要contains判断数据量又大建议改用HashSetO(1)的哈希查找比O(n)的遍历快几个量级。但要注意HashSet不保证顺序要保序且去重可以用LinkedHashSet。这是ArrayList一个容易被忽略的边界随机访问快但随机查找慢。别把ArrayList当成查找利器。3.5 clear/trimToSize/ensureCapacity管理容量的三板斧clear:public void clear() { modCount; for (int i 0; i size; i) elementData[i] null; size 0; }注意clear不会缩减容量。你清空了一个容量10万的ArrayList它底层还是10万的数组等着下一次使用。如果不复用这个对象其实是一种浪费。所以如果要彻底释放可以把list本身置空或者调用trimToSize()。trimToSize:public void trimToSize() { modCount; if (size elementData.length) { elementData (size 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }把容量压缩到size等于把多余的空间砍掉。适合一次性构建完大量数据、后续不再插入的场景比如读配置文件拼一个很大的配置List构建完调用trimToSize能省内存。ensureCapacity上面说过是反方向操作为后续添加预留容量。这三个方法可以看作同一套容量管理工具搞清楚它们就掌握了ArrayList的内存行为。4. 迭代器与fail-fast机制为什么不能在遍历时随便删除4.1 modCount与ConcurrentModificationExceptionArrayList的迭代器内部维护了一个expectedModCount字段初始化时等于当前modCount。每次调用next()和remove()都会先checkForComodificationfinal void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); }任何结构性修改add、remove、clear等都会让modCount增加而普通set不会。所以当你在迭代器循环中调用list.remove()modCount加1迭代器内部expectedModCount没变下一次next()时发现不一致立刻抛ConcurrentModificationException。这就是经典的fail-fast宁可快速失败也不让错误悄悄传播。很多人在遍历时删元素翻车都是因为用了for-each里面调用list.remove()。for-each底层就是迭代器自然踩雷。4.2 正确的遍历删除方式想要在遍历时删除元素有几种稳妥写法使用Iterator迭代器自带的remove():IteratorString iterator list.iterator(); while (iterator.hasNext()) { String s iterator.next(); if (条件) { iterator.remove(); } }迭代器remove会同步修改expectedModCount不会报错。实际上ArrayList的迭代器remove也是调用ArrayList.this.remove(lastRet)然后会把expectedModCount同步成新的modCount。使用list.removeIf()Java 8list.removeIf(s - 条件);这是最简洁的写法内部封装好了迭代器。如果要删除的是下标倒着删for (int i list.size() - 1; i 0; i--) { if (条件) { list.remove(i); } }倒序删除避免了元素前移后索引错位的问题。4.3 ArrayList线程安全吗CopyOnWriteArrayList怎么补位答案很直白ArrayList线程不安全。多线程同时读写时可能出现数据不一致、元素丢失极端情况下扩容时数组越界。解决方案用Collections.synchronizedList(new ArrayList())简单粗暴但读操作也要锁。用CopyOnWriteArrayList适合读多写少的场景。它的原理是每次写add/remove/set都复制一份新数组写完后用新数组替换旧数组读操作不加锁直接读当前数组。因为读的是快照所以迭代时不会抛ConcurrentModificationException。高并发写多时CopyOnWriteArrayList复制成本很高要慎重。我之前项目里有个读多写极少的配置白名单用的就是CopyOnWriteArrayList效果不错。如果写频繁还是老老实实加锁或用并发集合。5. 实战经验这些坑我不希望你等到线上才遇到5.1 Arrays.asList返回的不是ArrayList经典面试陷阱ListString list Arrays.asList(a, b, c);这个list的类型是Arrays$ArrayList一个内部类底层是固定长度的数组不支持add/remove调用就会抛UnsupportedOperationException。同时改原数组会反映到list里。想要一个真正的ArrayList得这样包装ListString list new ArrayList(Arrays.asList(a, b, c));这样才是独立的、可变长的ArrayList。很多人在把asList的结果当ArrayList用然后踩到add报错就是这个原因。5.2 subList视图改了原列表子列表直接报错ListString sub list.subList(2, 5);subList返回的是ArrayList的内部类SubList它持有父列表的引用没有复制数据。所以对sub的修改会直接反映到原list上。如果sub创建后往原list里add/removemodCount变化再操作sub时就会抛ConcurrentModificationException。sub的size手动设置可能导致全列表结构异常比如把sub大小变大会在原列表后面追加null元素。所以subList适合只读视图或临时范围操作不要长期持有并在之后随便改动原列表。想获得独立片段应该复制new ArrayList(list.subList(2, 5))。5.3 删元素遇到坑循环里remove的经典翻车正向遍历删除已经不安全了还有一个更隐蔽的坑for (int i 0; i list.size(); i) { if (条件) list.remove(i); }因为删除第i个元素后后面的元素全部前移索引i处的元素已经不是原来那个了跳过了一个元素。比如list [1,2,2,3]删除所有等于2的元素正向这样写会漏删。解决方式除了上面说的倒着删还可以用迭代器或removeIf。5.4 初始容量的合理设置别小看性能我见过一些离谱的代码循环往ArrayList里添加百万数据却没有预估容量导致扩容十几次。每次扩容都是全量复制加起来可能比插入本身还慢。经验法则如果能估算数量级new ArrayList(n)或者ensureCapacity(n)。负数容量抛IllegalArgumentException这个要知道。初始容量设太大也有内存开销按实际情况来。比如明确要装100万条直接new ArrayList(1000000)没问题如果不确定先给个大致数量级也行总比反复扩容好。5.5 序列化里transient elementData为什么不用默认序列化看到elementData字段声明为transient意味着默认的序列化机制不会把elementData整个数组写出去。为什么因为elementData数组中可能还有空闲位置如果整个序列化会把容量大小也带上浪费空间。所以ArrayList自己实现了writeObject/readObjectwriteObject遍历0到size-1只写实际存在的元素。readObject根据size重建数组按实际元素填充。这样序列化流里就只包含列表内容不包含null空洞。这也是为什么ArrayList能在不同JDK版本间保持较好的序列化兼容性。面试问transient在ArrayList里的作用本质就是在考察你有没有看过源码细节。6. 面试八股速查ArrayList高频问题快问快答6.1 你能手写一个简单的扩容逻辑吗面试经常让现场实现一个动态数组的add。我一般会写public class MyArrayListE { private Object[] data; private int size; public MyArrayList() { data new Object[10]; } public void add(E e) { if (size data.length) { int newCap data.length (data.length 1); data Arrays.copyOf(data, newCap); } data[size] e; } }重点不是代码多华丽而是能说出扩容时机size length、用右移实现除以2、用Arrays.copyOf复制、size自增。能说清楚为什么新容量是1.5倍比背代码更得面试官喜欢。6.2 ArrayList和LinkedList你选谁为什么随机访问多选ArrayList头部插入删除或需要频繁迭代并删除中间元素LinkedList理论上更好但实际由于局部性和拷贝开销ArrayList经常也不差。我的回答套路是先看业务操作模式不要背LinkedList插入快要指出每个操作的具体复杂度然后说如果性能敏感我会用JMH做简单压测再定。现代JVM和CPU缓存对数组更友好很多时候LinkedList反而更慢。6.3 怎么避免ConcurrentModificationException把能引发问题的操作拆开要么用迭代器remove、要么用removeIf、要么用CopyOnWriteArrayList的迭代器快照。如果只是遍历不修改就不会触发。如果多线程并发直接换线程安全容器。能答上fail-fast机制的原理再答解决方案这道题基本稳了。6.4 ArrayList默认容量是多少new ArrayList()时数组是空还是长度为10默认容量是10但new ArrayList()时elementData是空数组第一次add时才真正扩容到10。JDK6及之前有些版本是直接初始化10的JDK8开始改成了懒加载。这也是很多人记混的地方。扩展一下为什么要懒加载避免空列表占用无谓的内存。大量使用空ArrayList的场景下这个优化能省不少对象。6.5 ArrayList的扩容倍数是多少怎么计算1.5倍。计算式oldCapacity (oldCapacity 1)。如果加了还是不够minCapacity取minCapacity。超过MAX_ARRAY_SIZE再做特殊处理。这些都是能脱口而出的细节建议烂熟于心。这篇笔记写到这里。说实话ArrayList的源码在JDK集合里算简单的但越是基础的东西越能看出一个人的功夫。把elementData、size、modCount这三个字段的交互理清楚把add、remove、subList的边界情况摸透再遇到ArrayList相关的面试题或者线上问题你都不会慌。我个人建议读者把本文涉及的源码都自己打开JDK对照着看一遍不同版本代码可能略有差异但核心思路保持一致。遇到疑惑点就写个小demo验证这是学集合类最有用的习惯。