上一篇我们对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_CAPACITY（10）。也就是说，"默认容量 10"不是在构造时生效的，而是在第一次添加元素时生效的。第一次 add 会触发一次从 0 到 10 的扩容，从此列表才真正拥有了自己的数组。

这里还有一个值得玩味的细节：JDK 为什么要维护两个不同的空数组常量？

private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

它们内容完全一样，都是空数组，为什么不共用一个？因为 ArrayList 需要区分两种"空"的语义：

• new ArrayList()：用户没表态，按默认规则走——第一次 add 时扩到 10；

• new 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 List<User> queryUsers(int pageNum, int pageSize) { List<User> result = new ArrayList<>(); // 容量 10 起步 List<User> page = userDao.queryPage(pageNum, pageSize); for (User user : page) { result.add(convert(user)); // 可能触发多次扩容 } return result; } // 正确姿势：直接把容量开够 public List<User> queryUsers(int pageNum, int pageSize) { List<User> page = userDao.queryPage(pageNum, pageSize); List<User> result = new ArrayList<>(page.size()); // 一步到位 for (User user : page) { result.add(convert(user)); // 全程零扩容 } return result; }

第一种写法里，如果 pageSize 是 1000，ArrayList 会经历 10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244 → 366 → 549 → 823 → 1234 共 12 次扩容，每次都要分配新数组、拷贝全部已有元素。第二种写法把这些开销一次性清零。在批量导入、报表生成、消息消费这类"数据量可预知"的场景中，这个差异会被放大成显著的性能差距。

还有一个容易被忽略的隐患：扩容期间，新旧两个数组是同时存在于堆内存中的。假设列表已经装到 823 个元素触发扩容，那一瞬间堆上既有 823 长度的旧数组，又有 1234 长度的新数组，内存峰值约为平时的 2.5 倍。对于装载大对象（如图片元数据、大报文）的列表，这种瞬时峰值可能成为压垮内存的最后一根稻草。提前指定容量，不仅是提速，也是在削减内存峰值。

这里可以引出一个面试中常被追问的点：既然提前指定容量这么好，为什么不把 ArrayList 的默认容量直接改成按需分配、永不浪费？因为 JDK 的设计者面对的是全量用户：绝大多数开发者不会去预估容量，默认容量 10 是一个对"小规模使用"友好的折中——既不至于太浪费，又能让最常见的"存几个元素"场景完全不扩容。这是标准库设计中"为大多数场景优化"的典型体现。

3.4 还有一个被严重低估的 API：ensureCapacity

很多人不知道，ArrayList 对外暴露了一个专门用于预扩容的方法：

public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }

当你无法在构造时确定容量，但在循环开始前能拿到总量时，它可以救场：

List<String> 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 → 1234

• 2 倍序列：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 还是 2，n 次 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(); List<Integer> 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(); List<Integer> 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 的耗时：

ArrayList<Integer> 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() { List<Message> 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() { List<Message> batch = new ArrayList<>(expectedBatchSize); // ... } // 方向二：控制单次处理规模，分批消费 while (queue.hasMore()) { List<Message> 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[i+1]、arr[i+2]……这些即将被访问的元素已经"搭顺风车"进了缓存。顺序遍历数组时，绝大多数访问都命中缓存，有效带宽极高。

链表则完全相反。每个节点是独立分配的对象，散落在堆的各处。遍历链表时，每访问一个节点，都可能是一次缓存未命中——CPU 要停下来等内存把数据送来。一个 10 万节点的链表遍历，可能伴随数万次缓存失效。

我们用一段可复现的代码感受一下：

public class CacheLocalityDemo { public static void main(String[] args) { int n = 10_000_000; int[] arr = new int[n]; LinkedList<Integer> 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)，更是缓存亲和性。复杂度分析告诉你渐近行为，硬件才决定实际快慢。

下一篇我们进入删除、遍历、线程安全与面试专题。下篇见~~~