1. 从一次线上OOM事故说起为什么需要关心ArrayList扩容那天下午系统监控突然告警一个核心服务的堆内存使用率在几分钟内飙升到90%以上紧接着就是一连串的java.lang.OutOfMemoryError: Java heap space。紧急排查后发现问题出在一个看似简单的数据聚合任务上。这个任务需要处理一批用户行为日志预估数据量在百万级别开发同学为了图省事直接使用了一个ArrayList来存储中间结果。代码大概是这样的ListUserAction actionList new ArrayList(); for (LogEntry log : hugeLogStream) { // ... 一些过滤和处理逻辑 actionList.add(processedAction); }问题就出在new ArrayList()这一行。我们都知道ArrayList的默认构造函数会创建一个初始容量为10的空列表。当数据量远超10时ArrayList会不断地进行扩容操作。每次扩容都需要在堆内存中申请一块新的、更大的连续空间然后将旧数组中的所有元素复制到新数组中。这个“申请新空间 复制数据”的过程在数据量巨大时会带来两个致命问题内存浪费与碎片化在扩容的间隙JVM堆中会同时存在旧的数组对象和新的数组对象直到旧数组不再被引用后被GC回收。在频繁扩容的场景下这种临时性的内存“双倍占用”会加剧内存压力尤其是在接近堆内存上限时很容易触发OOM。性能损耗数据复制 (System.arraycopy) 是一个O(n)操作。当列表有100万元素时从容量为10扩容到最终容纳100万中间可能经历十几次扩容累计复制的元素总量可能达到数百万甚至上千万次这完全是没必要的开销。那次事故的根因就是对ArrayList的扩容机制理解不足没有根据业务数据规模进行合理的初始化。这不仅仅是面试八股文里的一个知识点更是直接影响系统稳定性和性能的关键细节。今天我们就彻底拆解一下ArrayList的扩容原理让你不仅能在面试中对答如流更能写出高效、健壮的代码。2. 庖丁解牛ArrayList内部结构与扩容触发条件要理解扩容必须先看清ArrayList的“五脏六腑”。它本质上是对一个动态数组的封装这个数组就是它的核心。2.1 核心字段解析打开ArrayList的源码以OpenJDK 8为例你会看到这几个关键字段/** * 存储ArrayList元素的数组缓冲区。 */ transient Object[] elementData; /** * ArrayList中实际包含的元素数量。 */ private int size; /** * 默认初始容量。 */ private static final int DEFAULT_CAPACITY 10;elementData 这是ArrayList的“心脏”一个Object[]数组。我们add进去的所有元素实际上都存储在这个数组里。transient关键字意味着它不会被默认的序列化机制处理ArrayList有自己的writeObject和readObject方法来实现更高效的序列化。size 这是列表的逻辑大小即我们调用list.size()返回的值。它代表elementData数组中已经被使用的格子数量。size不一定等于elementData.length后者是数组的物理容量。DEFAULT_CAPACITY 常量10。这是使用无参构造函数new ArrayList()时在第一次添加元素后数组会达到的初始容量注意构造函数执行完瞬间容量还是0这是个小坑后面细说。2.2 扩容的“发令枪”add方法与ensureCapacityInternal扩容不是定时发生的而是在需要添加新元素但当前数组已满时触发的。我们最常用的add(E e)方法就是典型的触发器。public boolean add(E e) { ensureCapacityInternal(size 1); // 关键步骤确保容量足够 elementData[size] e; // 在size位置放入元素然后size加1 return true; }ensureCapacityInternal(size 1)是核心。它的意思是“为了再容纳1个新元素使总元素数达到size1请确保底层数组容量足够。” 如果不够就会触发扩容。我们跟进去看看为了清晰省略了一些边界检查代码private void ensureCapacityInternal(int minCapacity) { // 计算最小需要容量 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果当前数组是空的比如刚用无参构造创建那么最小需要容量至少是默认值10和minCapacity中较大的那个。 if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount; // 修改次数1用于迭代器的快速失败机制 // 如果最小需要容量 当前数组长度则必须扩容 if (minCapacity - elementData.length 0) grow(minCapacity); }这里有一个非常重要的坑点new ArrayList()创建的对象其内部的elementData并不是一个长度为10的数组而是一个名为DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组对象Object[0]。也就是说构造完成后物理容量是0逻辑大小size也是0。只有在第一次调用add方法时calculateCapacity方法才会识别出这个空数组并将所需的最小容量提升到10。所以ArrayList的“懒加载”策略避免了创建时即分配10个空位的内存浪费但也让一些初学者误以为一创建就有10个位置。实操心得正因为这个“懒初始化”机制如果你能预知列表大致的最终大小使用带初始容量的构造函数new ArrayList(initialCapacity)是绝对的最佳实践。这直接跳过了前面多次扩容的消耗。对于完全无法预估的小列表默认构造也无妨。3. 扩容的核心算法grow方法逐行解读当ensureExplicitCapacity方法判断需要扩容时就会调用grow方法。这是扩容逻辑的集中地。private void grow(int minCapacity) { // 旧容量 int oldCapacity elementData.length; // 新容量 旧容量 (旧容量 1)即旧容量的1.5倍 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); }我们来拆解每一步计算新容量基准值int newCapacity oldCapacity (oldCapacity 1);oldCapacity 1是位运算等价于oldCapacity / 2。所以newCapacity oldCapacity oldCapacity/2 1.5 * oldCapacity。1.5倍扩容是ArrayList选择的增长因子。这是一个经验值在空间浪费扩容倍数太大和时间效率减少扩容次数之间取得了较好的平衡。比如从10开始扩容序列是10 - 15 - 22 - 33 - 49 ... 扩容次数是对数增长的。容量修正if (newCapacity - minCapacity 0) newCapacity minCapacity;这里minCapacity是本次扩容必须满足的最小容量即size 1。当旧容量为0时即第一次扩容newCapacity 0 (0 1) 0显然小于minCapacity至少是10。所以会进入这个分支将newCapacity直接赋值为minCapacity。这保证了从0到初始容量的正确跳跃。在调用ensureCapacity(int minCapacity)方法手动扩容时如果传入的minCapacity大于1.5倍旧容量也会以此值为准。处理大容量边界if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity);MAX_ARRAY_SIZE Integer.MAX_VALUE - 8。为什么减8这是因为一些JVM实现会在数组对象头部存储一些元数据如对象头、数组长度预留8个字节可以避免这些元数据导致数组大小超过Integer.MAX_VALUE而溢出。hugeCapacity方法会处理极端情况如果minCapacity已经超过MAX_ARRAY_SIZE则直接尝试分配Integer.MAX_VALUE的容量否则最大只能分配到MAX_ARRAY_SIZE。执行扩容elementData Arrays.copyOf(elementData, newCapacity);这是最“重”的一步。Arrays.copyOf底层会调用System.arraycopy这个原生方法。它会在堆内存的年轻代或可能直接进入老年代取决于大小中寻找一块连续的、长度为newCapacity的内存空间。然后将旧elementData数组中的全部size个元素逐个复制到新数组的对应位置。最后将ArrayList内部的elementData引用指向这个新的数组。旧的数组失去了引用将在下一次GC时被回收。性能警示System.arraycopy虽然是原生方法速度很快但其时间复杂度是 O(n)n是旧数组中的元素数量。当列表内有上百万个元素时一次扩容的复制开销是巨大的会引发明显的STWStop-The-World式停顿。这也是文章开头OOM事故的间接推手——频繁扩容消耗了大量CPU时间进行复制拖慢了处理速度导致内存中的对象来不及释放。4. 扩容的代价时间与空间复杂度分析理解了过程我们就能定量分析扩容的代价。假设我们要向一个初始容量为10的ArrayList中插入N个元素N很大。4.1 时间复杂度如果不指定初始容量插入N个元素的总时间消耗包括两部分N次add操作本身的耗时O(N)。扩容过程中元素复制的耗时这是主要开销。设初始容量为 ( C )默认10增长因子为 ( r )1.5。扩容发生在容量达到 ( C, Cr, Cr^2, ... ) 的时候。最后一次扩容前的容量大约为 ( N/r )。那么所有扩容操作中被复制的元素总数大约是 [ C Cr Cr^2 ... \frac{N}{r} ] 这是一个等比数列求和。当N很大时总复制元素数量约为 ( (r/(r-1)) * N )。对于 ( r1.5 )系数约为 3。也就是说插入N个元素大约需要复制 3N 次元素。所以总的时间复杂度仍然是 O(N)但常数因子很大约为41次写入 3次复制。相比之下如果一次性指定容量为N则只有N次写入常数因子为1性能差异显著。4.2 空间复杂度在插入过程中ArrayList占用的最大空间并不是最终的N而是最后一次扩容后的容量 ( M )其中 ( N \le M N * r )。空间浪费平均而言有约 ( (r-1)/2 * N ) 的空间是闲置的。对于 r1.5约有 25% 的空间浪费。这是为了换取平摊O(1)的插入时间所付出的代价。峰值内存在扩容发生的那一刻旧数组容量为 ( M/r )和新数组容量为 ( M )会同时存在于内存中直到旧数组被GC。此时瞬时内存占用约为 ( (1 1/r) * M \approx 1.67M )比最终所需内存多出67%。在内存紧张时这个瞬时峰值非常危险。操作场景时间复杂度 (平摊)空间复杂度备注未预分配容量追加N个元素O(N)常数因子大(~4)O(N)有约25%浪费默认情况性能最差预分配容量为N追加N个元素O(N)常数因子小(~1)O(N)无浪费最佳实践在索引i处插入/删除元素O(N)O(N)需要移动i之后的所有元素5. 实战避坑指南如何与ArrayList扩容“和谐共处”知道了原理我们就能在编码中主动规避问题提升性能。5.1 黄金法则在构造时指定初始容量这是最重要、最有效的一条建议。如果你能大致估计列表最终的大小请务必使用new ArrayList(initialCapacity)。如何估算从数据库查询ListUser users new ArrayList(queryCount());处理文件行数ListString lines new ArrayList(estimatedLineCount);即使是模糊估计一个偏大的初始容量比如预估1000给1200也比默认的10要好得多。多出的200个空位占用的内存很小200个引用约1.6KB但避免了多次扩容。反面案例// 糟糕每次循环都可能触发扩容 ListResult results new ArrayList(); for (Item item : allItems) { if (item.isValid()) { results.add(process(item)); // 如果allItems有10万个这里会扩容很多次 } }正面案例// 优秀一次性分配足够空间 ListResult results new ArrayList(allItems.size()); // 即使有些item被过滤空间稍浪费但性能提升巨大 for (Item item : allItems) { if (item.isValid()) { results.add(process(item)); } } // 如果过滤比例很高且非常在意内存可以在最后使用trimToSize() // results.trimToSize(); // 释放多余空间但此操作会一次性复制数组慎用。5.2 理解ensureCapacity的适用场景如果你已经有一个ArrayList但即将要批量添加大量元素比如通过addAll你可以提前手动扩容。ListString list getExistingList(); // 一个已经有一些元素的列表 ListString hugeBatch getHugeBatch(); // 一个很大的集合 // 在addAll之前确保容量足够 list.ensureCapacity(list.size() hugeBatch.size()); list.addAll(hugeBatch); // 这次addAll内部就不会再触发扩容了这对于接收一个已存在的列表并追加数据的工具方法非常有用。5.3 警惕trimToSize的副作用ArrayList.trimToSize()方法会将底层数组的容量裁剪到恰好等于当前元素个数size以释放未使用的内存。听起来很美好但要注意这是一个“昂贵”的操作它需要创建一个新的、长度为size的数组并复制所有元素。时间复杂度是O(n)。可能适得其反如果你在trimToSize之后又添加了新元素那么会立刻触发一次新的扩容。这相当于用一次O(n)的复制换来了可能更频繁的后续扩容。使用建议只对那些确定不会再修改的ArrayList使用trimToSize。例如一个作为缓存或配置项的只读列表。在内存极度敏感的场景如移动端下对于生命周期较长且内容稳定的列表可以考虑使用。在服务端高性能场景下通常不推荐使用除非有明确证据表明内存浪费已成为瓶颈。5.4 与LinkedList的误用对比面试中常问ArrayList和LinkedList的区别。扩容机制是ArrayList的“阿喀琉斯之踵”而LinkedList没有扩容概念每个元素插入都是O(1)。但这绝不意味着LinkedList总是更好。ArrayList**适合“读多写少”或“尾部追加”**的场景。因为其底层是数组支持O(1)的随机访问get(int index)。尾部追加add(E e)在容量足够时也是O(1)。扩容的代价被平摊了。LinkedList适合“频繁在任意位置插入/删除”且不需要随机访问的场景。例如实现一个队列Deque。但它的get(int index)是O(n)的因为需要从头或尾遍历。一个经典误区为了“避免扩容”而在需要频繁随机访问的场景下使用LinkedList结果导致读取性能灾难。正确的做法是如果需要频繁随机访问就使用ArrayList并给它指定一个足够大的初始容量。6. 从源码看扩容的演进与细节差异不同版本的JDK在ArrayList扩容实现上略有微调但核心思想不变。了解这些细节有助于应对刁钻的面试题。6.1 JDK 8 与 JDK 11 的细微差别在JDK 8中grow方法计算新容量的代码就是我们上面分析的int newCapacity oldCapacity (oldCapacity 1);在JDK 11中这部分代码被重构得更清晰并增加了一个小的优化private Object[] 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); } return elementData Arrays.copyOf(elementData, newCapacity); }逻辑完全一致。主要的改进是在代码结构和可读性上。对于开发者而言行为没有变化。6.2Arrays.copyOf与System.arraycopygrow方法最后调用了Arrays.copyOf(elementData, newCapacity)。我们看看它的实现public static T T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } public static T,U T[] copyOf(U[] original, int newLength, Class? extends T[] newType) { SuppressWarnings(unchecked) T[] copy ((Object)newType (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); // 创建新数组 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); // 复制数据 return copy; }可以看到它做了两件事根据新长度和原数组类型使用反射 (Array.newInstance) 或直接new Object[newLength]创建新数组。调用System.arraycopy这个本地Native方法进行内存块复制。这是JVM层面用C/C实现的高效内存拷贝比用Java循环快得多。6.3 扩容中的“快速失败”机制注意ensureExplicitCapacity方法里有一行modCount。modCount是AbstractList中定义的字段记录列表结构被修改的次数如add、remove、clear但set修改元素值不算。这个字段主要用于迭代器的“快速失败”Fail-Fast机制。当你在用Iterator遍历列表时如果检测到modCount被意外修改即列表结构被其他线程修改或在单线程中用非迭代器方法修改就会立即抛出ConcurrentModificationException。在扩容时modCount意味着一次结构修改。如果你在迭代一个ArrayList的同时尝试添加元素导致扩容就会触发这个异常。这是ArrayList非线程安全的一个体现。7. 举一反三其他集合类的扩容策略理解ArrayList的扩容后可以对比看看其他常用集合类加深对数据结构设计的理解。HashMap(JDK 8) 默认初始容量16负载因子0.75。当元素数量 容量 * 负载因子时扩容新容量是旧容量的2倍。扩容后需要重新计算所有键的哈希索引并迁移数据代价比ArrayList更高。StringBuilder/StringBuffer 内部也是一个字符数组char[] value。默认初始容量16。扩容策略也是新容量 旧容量 * 2 2。它们也有ensureCapacity方法。Vector 这是ArrayList的线程安全古老版本。它的扩容策略可以通过capacityIncrement构造参数指定。如果不指定默认也是扩容为原来的2倍注意是2倍不是1.5倍。由于其同步开销大现代代码已不推荐使用可用Collections.synchronizedList(new ArrayList())或CopyOnWriteArrayList替代。通过对比可以发现动态数组结构的扩容是一个通用问题核心权衡都是扩容因子的选择。因子太小如1.1倍扩容频繁复制开销大因子太大如2倍内存浪费多。1.5倍和2倍是实践中常见的选择。回到我们开头的那个OOM案例根本的解决方案就是在创建ArrayList时根据数据源那个巨大的日志流的预估大小指定一个合理的初始容量。如果无法精确预估可以分批处理数据或者考虑使用更节省内存的数据结构如原始类型数组int[]或第三方库的Trove、FastUtil集合。对于海量数据最终可能需要跳出内存计算的范畴考虑流式处理Streaming或使用数据库/外部存储。ArrayList的扩容就像汽车换轮胎。如果你知道要跑长途处理大数据出发前就换上合适的轮胎指定初始容量旅途会平稳高效。如果抱着“路上再说”的心态用默认构造那么频繁的停车换胎扩容不仅耽误时间性能损耗还可能因为备用轮胎不够大内存不足而抛锚OOM。理解其原理就是掌握了这辆“Java集合之车”的保养手册能让你在编程的道路上行驶得更远、更稳。
1. 从一次线上OOM事故说起为什么需要关心ArrayList扩容那天下午系统监控突然告警一个核心服务的堆内存使用率在几分钟内飙升到90%以上紧接着就是一连串的java.lang.OutOfMemoryError: Java heap space。紧急排查后发现问题出在一个看似简单的数据聚合任务上。这个任务需要处理一批用户行为日志预估数据量在百万级别开发同学为了图省事直接使用了一个ArrayList来存储中间结果。代码大概是这样的ListUserAction actionList new ArrayList(); for (LogEntry log : hugeLogStream) { // ... 一些过滤和处理逻辑 actionList.add(processedAction); }问题就出在new ArrayList()这一行。我们都知道ArrayList的默认构造函数会创建一个初始容量为10的空列表。当数据量远超10时ArrayList会不断地进行扩容操作。每次扩容都需要在堆内存中申请一块新的、更大的连续空间然后将旧数组中的所有元素复制到新数组中。这个“申请新空间 复制数据”的过程在数据量巨大时会带来两个致命问题内存浪费与碎片化在扩容的间隙JVM堆中会同时存在旧的数组对象和新的数组对象直到旧数组不再被引用后被GC回收。在频繁扩容的场景下这种临时性的内存“双倍占用”会加剧内存压力尤其是在接近堆内存上限时很容易触发OOM。性能损耗数据复制 (System.arraycopy) 是一个O(n)操作。当列表有100万元素时从容量为10扩容到最终容纳100万中间可能经历十几次扩容累计复制的元素总量可能达到数百万甚至上千万次这完全是没必要的开销。那次事故的根因就是对ArrayList的扩容机制理解不足没有根据业务数据规模进行合理的初始化。这不仅仅是面试八股文里的一个知识点更是直接影响系统稳定性和性能的关键细节。今天我们就彻底拆解一下ArrayList的扩容原理让你不仅能在面试中对答如流更能写出高效、健壮的代码。2. 庖丁解牛ArrayList内部结构与扩容触发条件要理解扩容必须先看清ArrayList的“五脏六腑”。它本质上是对一个动态数组的封装这个数组就是它的核心。2.1 核心字段解析打开ArrayList的源码以OpenJDK 8为例你会看到这几个关键字段/** * 存储ArrayList元素的数组缓冲区。 */ transient Object[] elementData; /** * ArrayList中实际包含的元素数量。 */ private int size; /** * 默认初始容量。 */ private static final int DEFAULT_CAPACITY 10;elementData 这是ArrayList的“心脏”一个Object[]数组。我们add进去的所有元素实际上都存储在这个数组里。transient关键字意味着它不会被默认的序列化机制处理ArrayList有自己的writeObject和readObject方法来实现更高效的序列化。size 这是列表的逻辑大小即我们调用list.size()返回的值。它代表elementData数组中已经被使用的格子数量。size不一定等于elementData.length后者是数组的物理容量。DEFAULT_CAPACITY 常量10。这是使用无参构造函数new ArrayList()时在第一次添加元素后数组会达到的初始容量注意构造函数执行完瞬间容量还是0这是个小坑后面细说。2.2 扩容的“发令枪”add方法与ensureCapacityInternal扩容不是定时发生的而是在需要添加新元素但当前数组已满时触发的。我们最常用的add(E e)方法就是典型的触发器。public boolean add(E e) { ensureCapacityInternal(size 1); // 关键步骤确保容量足够 elementData[size] e; // 在size位置放入元素然后size加1 return true; }ensureCapacityInternal(size 1)是核心。它的意思是“为了再容纳1个新元素使总元素数达到size1请确保底层数组容量足够。” 如果不够就会触发扩容。我们跟进去看看为了清晰省略了一些边界检查代码private void ensureCapacityInternal(int minCapacity) { // 计算最小需要容量 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果当前数组是空的比如刚用无参构造创建那么最小需要容量至少是默认值10和minCapacity中较大的那个。 if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount; // 修改次数1用于迭代器的快速失败机制 // 如果最小需要容量 当前数组长度则必须扩容 if (minCapacity - elementData.length 0) grow(minCapacity); }这里有一个非常重要的坑点new ArrayList()创建的对象其内部的elementData并不是一个长度为10的数组而是一个名为DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组对象Object[0]。也就是说构造完成后物理容量是0逻辑大小size也是0。只有在第一次调用add方法时calculateCapacity方法才会识别出这个空数组并将所需的最小容量提升到10。所以ArrayList的“懒加载”策略避免了创建时即分配10个空位的内存浪费但也让一些初学者误以为一创建就有10个位置。实操心得正因为这个“懒初始化”机制如果你能预知列表大致的最终大小使用带初始容量的构造函数new ArrayList(initialCapacity)是绝对的最佳实践。这直接跳过了前面多次扩容的消耗。对于完全无法预估的小列表默认构造也无妨。3. 扩容的核心算法grow方法逐行解读当ensureExplicitCapacity方法判断需要扩容时就会调用grow方法。这是扩容逻辑的集中地。private void grow(int minCapacity) { // 旧容量 int oldCapacity elementData.length; // 新容量 旧容量 (旧容量 1)即旧容量的1.5倍 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); }我们来拆解每一步计算新容量基准值int newCapacity oldCapacity (oldCapacity 1);oldCapacity 1是位运算等价于oldCapacity / 2。所以newCapacity oldCapacity oldCapacity/2 1.5 * oldCapacity。1.5倍扩容是ArrayList选择的增长因子。这是一个经验值在空间浪费扩容倍数太大和时间效率减少扩容次数之间取得了较好的平衡。比如从10开始扩容序列是10 - 15 - 22 - 33 - 49 ... 扩容次数是对数增长的。容量修正if (newCapacity - minCapacity 0) newCapacity minCapacity;这里minCapacity是本次扩容必须满足的最小容量即size 1。当旧容量为0时即第一次扩容newCapacity 0 (0 1) 0显然小于minCapacity至少是10。所以会进入这个分支将newCapacity直接赋值为minCapacity。这保证了从0到初始容量的正确跳跃。在调用ensureCapacity(int minCapacity)方法手动扩容时如果传入的minCapacity大于1.5倍旧容量也会以此值为准。处理大容量边界if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity);MAX_ARRAY_SIZE Integer.MAX_VALUE - 8。为什么减8这是因为一些JVM实现会在数组对象头部存储一些元数据如对象头、数组长度预留8个字节可以避免这些元数据导致数组大小超过Integer.MAX_VALUE而溢出。hugeCapacity方法会处理极端情况如果minCapacity已经超过MAX_ARRAY_SIZE则直接尝试分配Integer.MAX_VALUE的容量否则最大只能分配到MAX_ARRAY_SIZE。执行扩容elementData Arrays.copyOf(elementData, newCapacity);这是最“重”的一步。Arrays.copyOf底层会调用System.arraycopy这个原生方法。它会在堆内存的年轻代或可能直接进入老年代取决于大小中寻找一块连续的、长度为newCapacity的内存空间。然后将旧elementData数组中的全部size个元素逐个复制到新数组的对应位置。最后将ArrayList内部的elementData引用指向这个新的数组。旧的数组失去了引用将在下一次GC时被回收。性能警示System.arraycopy虽然是原生方法速度很快但其时间复杂度是 O(n)n是旧数组中的元素数量。当列表内有上百万个元素时一次扩容的复制开销是巨大的会引发明显的STWStop-The-World式停顿。这也是文章开头OOM事故的间接推手——频繁扩容消耗了大量CPU时间进行复制拖慢了处理速度导致内存中的对象来不及释放。4. 扩容的代价时间与空间复杂度分析理解了过程我们就能定量分析扩容的代价。假设我们要向一个初始容量为10的ArrayList中插入N个元素N很大。4.1 时间复杂度如果不指定初始容量插入N个元素的总时间消耗包括两部分N次add操作本身的耗时O(N)。扩容过程中元素复制的耗时这是主要开销。设初始容量为 ( C )默认10增长因子为 ( r )1.5。扩容发生在容量达到 ( C, Cr, Cr^2, ... ) 的时候。最后一次扩容前的容量大约为 ( N/r )。那么所有扩容操作中被复制的元素总数大约是 [ C Cr Cr^2 ... \frac{N}{r} ] 这是一个等比数列求和。当N很大时总复制元素数量约为 ( (r/(r-1)) * N )。对于 ( r1.5 )系数约为 3。也就是说插入N个元素大约需要复制 3N 次元素。所以总的时间复杂度仍然是 O(N)但常数因子很大约为41次写入 3次复制。相比之下如果一次性指定容量为N则只有N次写入常数因子为1性能差异显著。4.2 空间复杂度在插入过程中ArrayList占用的最大空间并不是最终的N而是最后一次扩容后的容量 ( M )其中 ( N \le M N * r )。空间浪费平均而言有约 ( (r-1)/2 * N ) 的空间是闲置的。对于 r1.5约有 25% 的空间浪费。这是为了换取平摊O(1)的插入时间所付出的代价。峰值内存在扩容发生的那一刻旧数组容量为 ( M/r )和新数组容量为 ( M )会同时存在于内存中直到旧数组被GC。此时瞬时内存占用约为 ( (1 1/r) * M \approx 1.67M )比最终所需内存多出67%。在内存紧张时这个瞬时峰值非常危险。操作场景时间复杂度 (平摊)空间复杂度备注未预分配容量追加N个元素O(N)常数因子大(~4)O(N)有约25%浪费默认情况性能最差预分配容量为N追加N个元素O(N)常数因子小(~1)O(N)无浪费最佳实践在索引i处插入/删除元素O(N)O(N)需要移动i之后的所有元素5. 实战避坑指南如何与ArrayList扩容“和谐共处”知道了原理我们就能在编码中主动规避问题提升性能。5.1 黄金法则在构造时指定初始容量这是最重要、最有效的一条建议。如果你能大致估计列表最终的大小请务必使用new ArrayList(initialCapacity)。如何估算从数据库查询ListUser users new ArrayList(queryCount());处理文件行数ListString lines new ArrayList(estimatedLineCount);即使是模糊估计一个偏大的初始容量比如预估1000给1200也比默认的10要好得多。多出的200个空位占用的内存很小200个引用约1.6KB但避免了多次扩容。反面案例// 糟糕每次循环都可能触发扩容 ListResult results new ArrayList(); for (Item item : allItems) { if (item.isValid()) { results.add(process(item)); // 如果allItems有10万个这里会扩容很多次 } }正面案例// 优秀一次性分配足够空间 ListResult results new ArrayList(allItems.size()); // 即使有些item被过滤空间稍浪费但性能提升巨大 for (Item item : allItems) { if (item.isValid()) { results.add(process(item)); } } // 如果过滤比例很高且非常在意内存可以在最后使用trimToSize() // results.trimToSize(); // 释放多余空间但此操作会一次性复制数组慎用。5.2 理解ensureCapacity的适用场景如果你已经有一个ArrayList但即将要批量添加大量元素比如通过addAll你可以提前手动扩容。ListString list getExistingList(); // 一个已经有一些元素的列表 ListString hugeBatch getHugeBatch(); // 一个很大的集合 // 在addAll之前确保容量足够 list.ensureCapacity(list.size() hugeBatch.size()); list.addAll(hugeBatch); // 这次addAll内部就不会再触发扩容了这对于接收一个已存在的列表并追加数据的工具方法非常有用。5.3 警惕trimToSize的副作用ArrayList.trimToSize()方法会将底层数组的容量裁剪到恰好等于当前元素个数size以释放未使用的内存。听起来很美好但要注意这是一个“昂贵”的操作它需要创建一个新的、长度为size的数组并复制所有元素。时间复杂度是O(n)。可能适得其反如果你在trimToSize之后又添加了新元素那么会立刻触发一次新的扩容。这相当于用一次O(n)的复制换来了可能更频繁的后续扩容。使用建议只对那些确定不会再修改的ArrayList使用trimToSize。例如一个作为缓存或配置项的只读列表。在内存极度敏感的场景如移动端下对于生命周期较长且内容稳定的列表可以考虑使用。在服务端高性能场景下通常不推荐使用除非有明确证据表明内存浪费已成为瓶颈。5.4 与LinkedList的误用对比面试中常问ArrayList和LinkedList的区别。扩容机制是ArrayList的“阿喀琉斯之踵”而LinkedList没有扩容概念每个元素插入都是O(1)。但这绝不意味着LinkedList总是更好。ArrayList**适合“读多写少”或“尾部追加”**的场景。因为其底层是数组支持O(1)的随机访问get(int index)。尾部追加add(E e)在容量足够时也是O(1)。扩容的代价被平摊了。LinkedList适合“频繁在任意位置插入/删除”且不需要随机访问的场景。例如实现一个队列Deque。但它的get(int index)是O(n)的因为需要从头或尾遍历。一个经典误区为了“避免扩容”而在需要频繁随机访问的场景下使用LinkedList结果导致读取性能灾难。正确的做法是如果需要频繁随机访问就使用ArrayList并给它指定一个足够大的初始容量。6. 从源码看扩容的演进与细节差异不同版本的JDK在ArrayList扩容实现上略有微调但核心思想不变。了解这些细节有助于应对刁钻的面试题。6.1 JDK 8 与 JDK 11 的细微差别在JDK 8中grow方法计算新容量的代码就是我们上面分析的int newCapacity oldCapacity (oldCapacity 1);在JDK 11中这部分代码被重构得更清晰并增加了一个小的优化private Object[] 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); } return elementData Arrays.copyOf(elementData, newCapacity); }逻辑完全一致。主要的改进是在代码结构和可读性上。对于开发者而言行为没有变化。6.2Arrays.copyOf与System.arraycopygrow方法最后调用了Arrays.copyOf(elementData, newCapacity)。我们看看它的实现public static T T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } public static T,U T[] copyOf(U[] original, int newLength, Class? extends T[] newType) { SuppressWarnings(unchecked) T[] copy ((Object)newType (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); // 创建新数组 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); // 复制数据 return copy; }可以看到它做了两件事根据新长度和原数组类型使用反射 (Array.newInstance) 或直接new Object[newLength]创建新数组。调用System.arraycopy这个本地Native方法进行内存块复制。这是JVM层面用C/C实现的高效内存拷贝比用Java循环快得多。6.3 扩容中的“快速失败”机制注意ensureExplicitCapacity方法里有一行modCount。modCount是AbstractList中定义的字段记录列表结构被修改的次数如add、remove、clear但set修改元素值不算。这个字段主要用于迭代器的“快速失败”Fail-Fast机制。当你在用Iterator遍历列表时如果检测到modCount被意外修改即列表结构被其他线程修改或在单线程中用非迭代器方法修改就会立即抛出ConcurrentModificationException。在扩容时modCount意味着一次结构修改。如果你在迭代一个ArrayList的同时尝试添加元素导致扩容就会触发这个异常。这是ArrayList非线程安全的一个体现。7. 举一反三其他集合类的扩容策略理解ArrayList的扩容后可以对比看看其他常用集合类加深对数据结构设计的理解。HashMap(JDK 8) 默认初始容量16负载因子0.75。当元素数量 容量 * 负载因子时扩容新容量是旧容量的2倍。扩容后需要重新计算所有键的哈希索引并迁移数据代价比ArrayList更高。StringBuilder/StringBuffer 内部也是一个字符数组char[] value。默认初始容量16。扩容策略也是新容量 旧容量 * 2 2。它们也有ensureCapacity方法。Vector 这是ArrayList的线程安全古老版本。它的扩容策略可以通过capacityIncrement构造参数指定。如果不指定默认也是扩容为原来的2倍注意是2倍不是1.5倍。由于其同步开销大现代代码已不推荐使用可用Collections.synchronizedList(new ArrayList())或CopyOnWriteArrayList替代。通过对比可以发现动态数组结构的扩容是一个通用问题核心权衡都是扩容因子的选择。因子太小如1.1倍扩容频繁复制开销大因子太大如2倍内存浪费多。1.5倍和2倍是实践中常见的选择。回到我们开头的那个OOM案例根本的解决方案就是在创建ArrayList时根据数据源那个巨大的日志流的预估大小指定一个合理的初始容量。如果无法精确预估可以分批处理数据或者考虑使用更节省内存的数据结构如原始类型数组int[]或第三方库的Trove、FastUtil集合。对于海量数据最终可能需要跳出内存计算的范畴考虑流式处理Streaming或使用数据库/外部存储。ArrayList的扩容就像汽车换轮胎。如果你知道要跑长途处理大数据出发前就换上合适的轮胎指定初始容量旅途会平稳高效。如果抱着“路上再说”的心态用默认构造那么频繁的停车换胎扩容不仅耽误时间性能损耗还可能因为备用轮胎不够大内存不足而抛锚OOM。理解其原理就是掌握了这辆“Java集合之车”的保养手册能让你在编程的道路上行驶得更远、更稳。
