上一篇我们对ArrayList进行了初步讲解这一篇开始深入来看第三章ArrayList 初始化源码分析3.1 从一行代码开始new ArrayList() 到底做了什么很多人以为new ArrayList()会创建一个长度为 10 的数组。这个认知放在 JDK 7 是对的但放在 JDK 8 就是错的。我们直接看源码private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }整个无参构造只有一行代码把elementData指向一个共享的空数组常量。注意这里没有任何new Object[10]。也就是说当你写下new ArrayList()的那一刻JVM 堆上根本没有为这个列表分配任何数组空间它只是拿到了一个全局共享的空数组引用。这行代码背后藏着一个重要的设计转变。在 JDK 7 及更早的版本中无参构造是这样的// JDK 7 的写法 public ArrayList() { this.elementData new Object[DEFAULT_CAPACITY]; // 立刻 new 一个长度 10 的数组 }那时候不管你用不用这个列表创建即分配。JDK 8 的设计者为什么要改掉这个行为我们可以做一个思想实验在一个典型的 Web 应用里一个 HTTP 请求的处理过程中可能会创建几十个 ArrayList——用于收集查询参数、组装响应字段、临时存放中间结果。其中相当一部分列表创建之后要么没被使用要么只存了一两个元素。如果每个列表都立即分配 10 个槽位的数组这些半成品数组会成为 Young 区里最频繁的垃圾来源之一。把它们改成延迟分配等于把这部分内存开销推迟到真正需要的时刻用不到的列表则完全不产生数组对象。这就是**延迟初始化Lazy Initialization**思想不预先付出成本把开销推迟到真正使用的时刻。它不是 ArrayList 独有的智慧——Spring 的懒加载 Bean、双重检查锁的单例模式、JVM 类加载机制本质上都是同一个思路。3.2 那默认容量 10去哪了既然无参构造不分配数组那传说中的默认容量 10体现在哪里答案藏在第一次add()调用的路径里。当你对一个刚创建的列表执行list.add(Java)执行链条是这样的public boolean add(E e) { ensureCapacityInternal(size 1); // size 0所以 minCapacity 1 elementData[size] e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity Math.max(DEFAULT_CAPACITY, minCapacity); // 关键提升到 10 } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount; if (minCapacity - elementData.length 0) grow(minCapacity); // 第一次扩容0 → 10 }注意ensureCapacityInternal里的那个判断如果当前elementData还是那个共享的空占位符就把最小容量需求从 1 提升到DEFAULT_CAPACITY10。也就是说默认容量 10不是在构造时生效的而是在第一次添加元素时生效的。第一次 add 会触发一次从 0 到 10 的扩容从此列表才真正拥有了自己的数组。这里还有一个值得玩味的细节JDK 为什么要维护两个不同的空数组常量private static final Object[] EMPTY_ELEMENTDATA {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};它们内容完全一样都是空数组为什么不共用一个因为 ArrayList 需要区分两种空的语义new ArrayList()用户没表态按默认规则走——第一次 add 时扩到 10new ArrayList(0)用户明确声明要一个从 0 起步的列表——第一次 add 时只扩到 1。两个常量就像两个状态标记通过引用比较就能判断当前列表属于哪种状态。用两个空数组常量代替一个布尔标志位是源码中常见的以对象身份表达状态的技巧代价极小语义清晰。3.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); } }这段代码本身很简单但它引出了一个重要的工程问题为什么 JDK 要给用户提供手动指定容量的入口答案是扩容是有成本的而 ArrayList 自己无法预知你要存多少数据但你往往知道。来看一个真实的场景——从数据库分页查询结果组装列表// 反模式明明知道结果集大小却让 ArrayList 自己摸索 public ListUser queryUsers(int pageNum, int pageSize) { ListUser result new ArrayList(); // 容量 10 起步 ListUser page userDao.queryPage(pageNum, pageSize); for (User user : page) { result.add(convert(user)); // 可能触发多次扩容 } return result; } // 正确姿势直接把容量开够 public ListUser queryUsers(int pageNum, int pageSize) { ListUser page userDao.queryPage(pageNum, pageSize); ListUser result new ArrayList(page.size()); // 一步到位 for (User user : page) { result.add(convert(user)); // 全程零扩容 } return result; }第一种写法里如果 pageSize 是 1000ArrayList 会经历 10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244 → 366 → 549 → 823 → 1234 共 12 次扩容每次都要分配新数组、拷贝全部已有元素。第二种写法把这些开销一次性清零。在批量导入、报表生成、消息消费这类数据量可预知的场景中这个差异会被放大成显著的性能差距。还有一个容易被忽略的隐患扩容期间新旧两个数组是同时存在于堆内存中的。假设列表已经装到 823 个元素触发扩容那一瞬间堆上既有 823 长度的旧数组又有 1234 长度的新数组内存峰值约为平时的 2.5 倍。对于装载大对象如图片元数据、大报文的列表这种瞬时峰值可能成为压垮内存的最后一根稻草。提前指定容量不仅是提速也是在削减内存峰值。这里可以引出一个面试中常被追问的点既然提前指定容量这么好为什么不把 ArrayList 的默认容量直接改成按需分配、永不浪费因为 JDK 的设计者面对的是全量用户绝大多数开发者不会去预估容量默认容量 10 是一个对小规模使用友好的折中——既不至于太浪费又能让最常见的存几个元素场景完全不扩容。这是标准库设计中为大多数场景优化的典型体现。3.4 还有一个被严重低估的 APIensureCapacity很多人不知道ArrayList 对外暴露了一个专门用于预扩容的方法public void ensureCapacity(int minCapacity) { int minExpand (elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity minExpand) { ensureExplicitCapacity(minCapacity); } }当你无法在构造时确定容量但在循环开始前能拿到总量时它可以救场ListString lines new ArrayList(); // 先扫一遍文件统计行数或者从文件头拿到 count int total countLines(file); lines.ensureCapacity(total); // 一次性扩到位 for (String line : readLines(file)) { lines.add(line); // 后续全程零扩容 }这个 API 的存在本身就说明JDK 设计者把容量规划视为 ArrayList 使用者的责任并提供工具支持。会用 ArrayList 和用好 ArrayList差距往往就在这些细节里。第四章添加元素源码深度分析4.1 完整追踪一次 list.add(Java)现在我们把第四章的主角请出来——add(E e)。这是 ArrayList 中被调用频率最高的方法也是理解扩容机制的入口。完整源码如下public boolean add(E e) { ensureCapacityInternal(size 1); // Increments modCount!! elementData[size] e; return true; }只有三行但每一行都有讲究。我们逐行推演。第一行ensureCapacityInternal(size 1)。 在放入元素之前先问一句还装得下吗。参数size 1表示放完这个元素之后列表至少需要的容量。这个顺序不能颠倒——必须先确保容量再写入否则写入时可能越界。同时注意源码里的注释Increments modCount扩容路径上的ensureExplicitCapacity会递增modCount这正是 fail-fast 机制的伏笔第八章展开。第二行elementData[size] e。 把元素放到当前 size 指向的位置然后 size 自增。这里有个细节值得注意ArrayList 的添加是尾部追加下标正好等于 size不需要移动任何已有元素所以只要不触发扩容这一步就是纯粹的数组赋值O(1)。第三行return true。 返回 true 是为了符合Collection.add的接口约定集合因调用而改变则返回 true。ArrayList 永远返回 true但有些集合如不允许重复的 Set可能返回 false——接口签名必须照顾所有实现。整个方法没有任何同步代码。这意味着两件事单线程下它足够快多线程下它不安全第九章展开。JDK 把要不要同步的决定权交给了使用者这是 ArrayList 与 Vector 分道扬镳的根本原因。4.2 容量检查的三层调用链add的第一行开启了一条三层调用链我们把它完整走一遍private void ensureCapacityInternal(int minCapacity) { if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount; if (minCapacity - elementData.length 0) grow(minCapacity); }第一层处理首次添加的特殊情况前面已经讲过。第二层的判断条件值得细看为什么写minCapacity - elementData.length 0而不是更直观的minCapacity elementData.length这两种写法在语义上等价但减法写法规避了整数溢出。虽然在这个具体场景下minCapacity不会大到溢出但 JDK 源码普遍采用减法比较的风格如Integer.compare之前的年代这是一种防御性编程习惯的延续。阅读 JDK 源码时你会反复遇到这种模式理解它的动机比记住它的形式更重要。第三层才是重头戏grow(minCapacity)。4.3 grow()扩容的心脏private 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); }六行代码完成了一次完整的扩容。我们逐句推演它在做什么、为什么这么做。int newCapacity oldCapacity (oldCapacity 1);—— 计算新容量。oldCapacity 1是右移一位等价于除以 2向下取整所以新容量 旧容量 旧容量/2 1.5 倍。用位运算替代乘除一方面是历史习惯早期 CPU 上移位确实更快另一方面也避免了浮点运算——整数运算全程不离开整数域不会有精度问题。if (newCapacity - minCapacity 0) newCapacity minCapacity;—— 兜底逻辑。1.5 倍并不总是够用。考虑一个场景列表当前容量为 10调用方执行list.addAll(anotherListWith1000Elements)此时 minCapacity 1010而 1.5 倍只有 15。这种情况下直接把容量设为 1010一步到位避免扩容到 15、不够、再扩到 22、还不够……的连环扩容。扩容策略必须同时照顾逐个添加和批量添加两种模式这个 if 就是对后者的补偿。if (newCapacity - MAX_ARRAY_SIZE 0)—— 数组长度上限保护。MAX_ARRAY_SIZE的值是Integer.MAX_VALUE - 8源码注释解释了原因有些 JVM 实现会在数组对象头里保留若干字节请求完整Integer.MAX_VALUE长度的数组可能抛出OutOfMemoryError。超过这个阈值时交给hugeCapacity处理如果 minCapacity 为负溢出直接抛 OOM否则在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间取 minCapacity 所需的值。这是极端场景的兜底日常开发几乎遇不到但标准库必须考虑。elementData Arrays.copyOf(elementData, newCapacity);—— 真正执行扩容的地方分配新数组、拷贝旧数据、切换引用。这一行完成了旧数组退场、新数组登场的全部动作。4.4 为什么是 1.5 倍一道经典权衡题为什么扩容是 1.5 倍而不是 2 倍是 ArrayList 面试中被问得最多的问题之一。回答这个问题的关键不是背结论而是把权衡的三个维度讲清楚扩容次数、内存浪费、均摊成本。我们先把扩容序列实际推演一遍。假设从容量 10 开始一路添加元素1.5 倍序列10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244 → 366 → 549 → 823 → 12342 倍序列10 → 20 → 40 → 80 → 160 → 320 → 640 → 1280添加 1000 个元素1.5 倍扩容 12 次2 倍扩容 7 次。看起来 2 倍更好但要把三个因素放在一起看。第一扩容次数 vs 单次成本。扩容次数越少越好但每次扩容的成本是 O(n)——要拷贝全部已有元素。扩容倍数越大后期单次扩容的绝对成本越高。2 倍扩容意味着某一次要把 640 个引用整体搬迁而 1.5 倍对应的单次搬迁规模更小、更平滑响应时间的抖动也更小。对延迟敏感的服务来说少而大的停顿和多而小的停顿是两种不同的体验。第二内存浪费。任何时刻ArrayList 的容量都大于等于实际元素数差额就是浪费。倍数越大这个差额的上限越大2 倍扩容时容量最多可以是实际大小的近 2 倍刚扩完容只放了 1 个新元素时浪费接近一半1.5 倍时这个上限约为 1/3。如果有成千上万个 ArrayList 同时存活这在服务端应用中很常见这 1/6 的差距就是实打实的堆内存。第三均摊复杂度。可以证明无论扩容倍数是 1.5 还是 2n 次 add 的总拷贝次数都与 n 成正比等比数列求和的性质均摊到每次 add 仍是 O(1)。区别在于常数项倍数越大均摊常数越小但内存浪费越大。所以 1.5 倍不是数学上的最优解而是工程上的折中点扩容频率可接受、内存浪费可控、单次停顿不至于太大。有意思的是不同语言做了不同选择——C 的std::vector常见实现用 2 倍Python 的 list 用约 1.125 倍加上固定增量它们各自的语言生态对内存和性能的侧重不同。理解这一点后面试时你就能跳出1.5 倍是标准答案的窠臼展现出这是一个权衡区间JDK 选了其中一个点的视角。4.5 Arrays.copyOf 与 System.arraycopy拷贝的实现扩容的最后一步是数据迁移。Arrays.copyOf的内部实现最终落到一个 native 方法上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; }它做两件事按目标类型创建新数组然后调用System.arraycopy完成拷贝。而System.arraycopy是一个native方法底层由 JVM 用高度优化的机器码实现它会针对元素类型选择最优的拷贝路径引用数组拷贝无需逐元素处理基本类型语义利用 CPU 的块拷贝指令如 x86 的rep movs并由 JIT 做边界检查消除。实测中它比手写 for 循环拷贝快数倍——手写循环不仅有方法调用和边界检查开销还难以被编译器向量化。这个细节对工程实践的启示是当你自己在业务代码中需要数组/列表搬迁时优先使用Arrays.copyOf、System.arraycopy或List.subList等标准 API而不是手写循环。标准库在这些热点路径上的优化深度是业务代码难以企及的。4.6 场景复现扩容到底拖慢了多少空谈误事我们用一个可复现的实验量化扩容的代价public class ExpansionCostTest { public static void main(String[] args) { int n 1_000_000; long t1 System.nanoTime(); ListInteger lazy new ArrayList(); // 不指定容量 for (int i 0; i n; i) lazy.add(i); System.out.println(默认容量: (System.nanoTime() - t1) / 1_000_000 ms); long t2 System.nanoTime(); ListInteger eager new ArrayList(n); // 预分配 for (int i 0; i n; i) eager.add(i); System.out.println(预分配 : (System.nanoTime() - t2) / 1_000_000 ms); } }在普通笔记本上典型输出约为 130ms vs 25ms差距 5 倍左右不同电脑存在差距。注意这个差距全部来自约 30 次扩容的分配与拷贝——单次elementData[size] e的写入成本两者是一样的。再进一步如果想亲眼看到扩容瞬间的尖峰可以记录每次 add 的耗时ArrayListInteger list new ArrayList(); for (int i 0; i 100_000; i) { long start System.nanoTime(); list.add(i); long cost System.nanoTime() - start; if (cost 10_000) { // 只打印明显变慢的调用 System.out.println(i i 耗时 cost ns); } }你会看到慢调用恰好出现在 10、15、22、33……这些扩容临界点上耗时比平时高出两到三个数量级。这个实验直观地解释了一个线上现象P99 延迟的毛刺有时就是某次扩容。如果你的服务对尾部延迟敏感预分配容量几乎是必选项。第五章ArrayList 扩容机制源码剖析5.1 一个本质问题数组为什么不能原地变长第四章讲清了扩容怎么做这一章回答一个更根本的问题为什么扩容必须搬家而不能像链表那样直接长答案在内存模型里。数组的元素在物理内存中必须连续存放——这是数组能用首地址 偏移实现 O(1) 随机访问的前提。连续带来了一个硬约束当数组满了它背后的那块内存很可能已经被其他对象占用JVM 无法保证就地把数组延长。所以扩容的唯一办法是找一块更大的新地方把家当整体搬过去然后换个地址挂牌。这也回答了为什么 ArrayList 不能像链表一样无限添加。链表的节点彼此独立、散落在堆的各处新增节点只需要在任意空闲处分配一个对象再挂上指针而 ArrayList 每长大一次都要寻找一块足够大的连续空间。当堆内存碎片化严重时即使总剩余内存足够也可能找不到连续的可用块——这正是大数组扩容可能抛OutOfMemoryError: Java heap space的深层原因之一。5.2 扩容瞬间的内存全景我们把扩容那一瞬间的堆内存状态画出来。假设列表当前容量 10、已满正在添加第 11 个元素扩容前 elementData ──→ [ 旧数组10 个槽位全部装满 ] grow() 执行中Arrays.copyOf 内部 elementData ──→ [ 旧数组10 个元素 ] [ 新数组15 个槽位前 10 个正在拷贝 ] ← 两者同时存在 扩容后 elementData ──→ [ 新数组10 个元素 5 个空位 ] 旧数组失去所有引用 → 等待 GC有三个关键结论第一扩容期间内存峰值是新旧容量之和。如果列表已经很大比如装载了 100 万个大对象扩容瞬间的额外内存开销可能高达原数组的一半以上。这就是为什么大列表的扩容可能成为 OOM 的诱因——不是元素太多而是搬家时的双份占用压垮了堆。第二旧数组变成垃圾的时机非常明确elementData引用切换完成的那一刻。在此之前它仍是 GC Root 可达的在此之后它只能在下次 GC 时被回收。如果扩容频繁Young 区会不断产生大块的短命数组触发更频繁的 Minor GC甚至因为数组过大直接晋升老年代埋下 Full GC 的隐患。第三扩容不会收缩。如果你往列表里加了 10 万个元素再删到只剩 10 个elementData依然是 10 万 的容量——ArrayList 从不自动缩容。这对脉冲式使用的列表是个隐患详见 5.4 的场景复现。5.3 扩容为什么是 ArrayList 的头号性能瓶颈把扩容的成本拆开看它由三部分组成分配成本。JVM 在堆上分配一个数组需要找到连续空间、更新分配指针、把整块内存清零Java 语义要求新数组元素为 null/0。数组越大清零本身就是一笔不小的开销——一个 100 万容量的引用数组光是填零就要写 4~8MB 内存。拷贝成本。System.arraycopy虽然快但终究是 O(n)n 个引用要逐个从旧数组搬到新数组。而且这次拷贝对 CPU 缓存并不友好——它触碰的是一大段刚刚还热乎、但马上要被抛弃的内存。GC 成本。旧数组从活对象变成垃圾这笔账最终由 GC 偿还。大数组若在老年代回收它意味着更长的停顿。三笔账加起来使得扩容成为 ArrayList 所有操作中唯一的重操作。其他操作——尾部 add、get、set——都是几条指令的事唯独扩容容量越大越疼。这也反过来解释了 ArrayList 的一切使用建议的由来预分配容量、避免大列表反复重建、脉冲使用后手动trimToSize全都是在围绕这个瓶颈做文章。5.4 场景复现扩容引发的内存尖峰与 GC 抖动来看一个贴近生产的场景。某服务从消息队列批量拉取数据组装成列表后落库// 问题代码列表在方法内反复创建、装满、丢弃 public void consumeBatch() { ListMessage batch new ArrayList(); // 容量 10 起步 while (queue.hasMore()) { batch.add(queue.poll()); // 假设一批 50 万条 } db.saveBatch(batch); // batch 随方法返回变成垃圾一个装载过 50 万引用的大数组进入 GC }每次consumeBatch调用这个列表都会经历约 20 次扩容峰值时堆上同时存在约 75 万容量的数组空间方法返回后整个大数组变成垃圾。如果调用频繁监控上就会看到Young GC 频率升高、老年代增长加快、偶尔的 Full GC 停顿。问题的根源不在 GC而在扩容模式。优化思路有两个方向// 方向一预分配 复用若批次大小可预知或可配置 public void consumeBatch() { ListMessage batch new ArrayList(expectedBatchSize); // ... } // 方向二控制单次处理规模分批消费 while (queue.hasMore()) { ListMessage batch new ArrayList(BATCH_SIZE); for (int i 0; i BATCH_SIZE queue.hasMore(); i) { batch.add(queue.poll()); } db.saveBatch(batch); }方向一消灭扩容次数方向二则把大数组拆成小数组两者常常结合使用。这个案例说明扩容机制虽然是 ArrayList 的内部实现但它的外部表现内存峰值、GC 压力、延迟毛刺必须由使用方通过容量规划来治理。第六章ArrayList 查询源码分析6.1 get()简单到极致的源码查询是 ArrayList 的看家本领源码简单得几乎让人失望public E get(int index) { rangeCheck(index); return elementData(index); } private void rangeCheck(int index) { if (index size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } E elementData(int index) { return (E) elementData[index]; }一次边界检查一次数组取值完事。但越是简单的代码越值得追问为什么数组取值能做到 O(1)这个 O(1) 是理论上的还是实际上的6.2 O(1) 的物理基础地址是算出来的数组的随机访问之所以是 O(1)是因为数组元素的地址可以通过算术直接计算elementData[i] 的地址 数组首地址 数组头长度 i × 引用大小这个计算对 CPU 来说只是一次乘加在引用大小是 4 或 8 时甚至可以优化成一次移位加一次加法与数组多大、i 是多少完全无关。访问第 1 个元素和访问第 1000 万个元素寻址成本一模一样。这就是随机访问四个字的真正含义访问任意位置的成本都相同不需要走过去。对比一下链表就明白了。LinkedList 取第 i 个元素必须从头节点或尾节点看哪边近出发沿着 next/prev 指针一跳一跳地走走 i 步才能到达。每一跳意味着读一个节点对象、取出其中的指针字段、再按指针去访问另一块可能完全不相邻的内存。步数与 i 成正比所以是 O(n)。但理论复杂度只讲了故事的一半。实际运行中ArrayList 对 LinkedList 的优势比 O(1) vs O(n) 显示出的还要悬殊得多——这就要引入缓存的话题。6.3 缓存亲和性被复杂度分析掩盖的性能真相现代 CPU 访问内存的延迟大约在百纳秒量级而访问 L1 缓存只需 1 纳秒左右。为了弥合这个鸿沟CPU 以**缓存行Cache Line通常 64 字节**为单位成块地从内存搬数据你读一个字节它顺手把这个字节前后 64 字节一起搬进缓存。这个机制对数组极其友好。数组元素连续存放当 CPU 读取arr[i]时arr[i1]、arr[i2]……这些即将被访问的元素已经搭顺风车进了缓存。顺序遍历数组时绝大多数访问都命中缓存有效带宽极高。链表则完全相反。每个节点是独立分配的对象散落在堆的各处。遍历链表时每访问一个节点都可能是一次缓存未命中——CPU 要停下来等内存把数据送来。一个 10 万节点的链表遍历可能伴随数万次缓存失效。我们用一段可复现的代码感受一下public class CacheLocalityDemo { public static void main(String[] args) { int n 10_000_000; int[] arr new int[n]; LinkedListInteger list new LinkedList(); for (int i 0; i n; i) { arr[i] i; list.add(i); } long t1 System.nanoTime(); long sum1 0; for (int i 0; i n; i) sum1 arr[i]; // 数组顺序遍历 long t2 System.nanoTime(); long sum2 0; for (Integer x : list) sum2 x; // 链表顺序遍历 long t3 System.nanoTime(); System.out.println(数组: (t2 - t1) / 1_000_000 ms); System.out.println(链表: (t3 - t2) / 1_000_000 ms); } }两者的逻辑复杂度都是 O(n)但实测数组通常比链表快 20~50 倍。这个巨大的常数差距就是缓存亲和性的价值也是为什么 ArrayList 在绝大多数场景下优于 LinkedList的底层答案——算法复杂度相同的时候硬件说了算。顺带一提这也是RandomAccess标记接口存在的意义Collections.binarySearch、一些 Stream 内部实现会检查列表是否实现RandomAccess从而决定用下标直取还是迭代器推进来遍历。ArrayList 实现了它LinkedList 没有各自得到适合自己的遍历策略。6.4 rangeCheck 的一个有趣细节回头看边界检查你会发现一个不对称rangeCheck只检查了index size没有检查index 0。负数下标怎么办答案是交给数组访问本身。如果 index 是负数elementData[index]会由 JVM 直接抛出ArrayIndexOutOfBoundsException。ArrayList 在这里做了一个务实的选择上限检查必须自己做因为 index 在 size 和 capacity 之间是合法数组下标但越过了逻辑边界JVM 检查不出来下限检查可以委托给 JVM负数下标反正会被数组访问拦截。少一次比较热路径上省一条指令。这个细节体现了源码级优化的典型思路在绝对的热路径上每一个多余的判断都值得审视但前提是语义正确性不受影响。注意remove(int)用的是rangeCheckForAdd等不同的检查方法因为删除和添加的合法边界定义不同——检查逻辑与操作语义精确匹配而不是笼统地复用。6.5 查询性能的工程边界get() 本身无可优化但围绕查询的工程决策有讲究如果你需要按下标频繁随机访问ArrayList 是最优容器无需任何额外处理。如果你要做有序数据的二分查找可以直接用Collections.binarySearch——它检测到 ArrayList 实现了RandomAccess后会走下标路径O(log n) 实至名归同样的调用用在 LinkedList 上会退化成迭代器推进常数大得多。真正要注意的是删除/插入后再查询的组合场景。删除中间元素是 O(n)第七章详述如果你的工作负载是频繁删中间 频繁随机查ArrayList 的删除成本会拖累整体这时应该考虑 TreeMap、跳表或专门的索引结构而不是指望换一个 List 实现解决。第三至六章小结这四章我们沿着创建 → 添加 → 扩容 → 查询的生命周期完整走了一遍 ArrayList 的核心路径。回顾一下最关键的几个认知第一默认容量 10 在 JDK 8 中是第一次 add 时才生效的这是延迟初始化思想在标准库中的落地——不用的东西不付出成本。第二grow() 的每一步都在处理边界情况1.5 倍不够时取 minCapacity、超过 MAX_ARRAY_SIZE 时特殊处理、溢出时抛 OOM。标准库的健壮性就藏在这些不显眼的 if 里。第三1.5 倍扩容是工程折中而非数学最优理解它要同时考虑扩容次数、内存浪费、单次停顿三个维度。第四扩容的真实代价是分配 拷贝 GC三笔账它解释了预分配容量、trimToSize、分批处理等一系列工程建议的由来。第五ArrayList 的查询优势不只是 O(1)更是缓存亲和性。复杂度分析告诉你渐近行为硬件才决定实际快慢。下一篇我们进入删除、遍历、线程安全与面试专题。下篇见~~~