ArrayList 源码剖析基于 JDK 8 源码部分内容在网络上搜集而来第一章ArrayList 整体认识1.1 ArrayList 是什么ArrayList 是 Java 集合框架中基于 List 接口的动态数组实现位于java.util包完整声明如下public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable这一行声明里已经藏着大量设计信息继承 AbstractList复用 List 接口的骨架代码模板方法模式。ArrayList 只需实现get()、set()、size()等核心操作其余如迭代器、子视图等通用逻辑由 AbstractList 基于这些基础操作自动实现。实现 List声明自己是有序、可重复、可按索引访问的集合。实现 RandomAccess这是一个没有任何方法的标记接口Marker Interface。它的作用只是告诉调用方我支持快速随机访问遍历我时请优先用 for 循环 下标而不是迭代器。Collections.binarySearch()内部正是通过这个接口判断该用索引遍历还是迭代器遍历的。实现 Cloneable 和 Serializable支持浅拷贝与自定义序列化。为什么elementData要加transient却还能正常序列化这正是 ArrayList 序列化设计的精妙之处第二章详解。剥开接口声明ArrayList 的本质一句话概括它是一个增强版的数组。1.2 从数组的困境说起为什么需要动态数组要理解 ArrayList 为什么存在必须先回到最基础的数据结构——数组。数组有两个其他结构无法比拟的硬件级优势优势一O(1) 随机访问。数组元素在内存中连续存放CPU 通过一次地址运算即可定位任意元素目标地址 数组首地址 索引 × 单个元素大小注意这是算出来而不是找出来——无论数组有多大定位第 n 个元素永远是一次乘法加一次加法。这就是数组随机访问 O(1) 的来源。而链表必须从头节点开始逐个指针跳转这就是 O(n) 的来源。优势二缓存亲和性Cache Locality。现代 CPU 以缓存行Cache Line通常 64 字节为单位读取内存。由于数组内存连续加载一个元素时后面若干个元素会被顺带装入缓存空间局部性原理。实际遍历数组时 CPU 缓存命中率极高性能往往比逻辑复杂度同为 O(n) 的链表高出一个数量级。但数组有一个致命问题长度固定。Java 数组在 JVM 分配内存后长度即记录在对象头中不可更改。于是我们写代码时永远面临两难// 数组创建时刻的灵魂拷问到底开多长 String[] arr new String[???];开小了存不下直接ArrayIndexOutOfBoundsException开大了浪费内存大数组还会增加 GC 压力。矛盾的根源在于容量必须在分配时确定而实际数据量往往运行时才知道。这是数组的根本性缺陷。1.3 动态数组思想ArrayList 的解法ArrayList 的解法非常优雅——它没有抛弃数组而是保留数组作为底层存储在数组之上封装一层自动扩容逻辑内部维护一个Object[] elementData数组真正存放数据每次添加元素前先检查elementData是否还有空位有空位直接存入没空位创建一个更大的新数组JDK 8 默认扩到原来的 1.5 倍把旧数组数据拷贝过去让elementData指向新数组旧数组失去引用等待 GC 回收。对调用方而言这个容器要多少装多少完全不需要关心容量——这就是动态数组思想静态数组 扩容机制 动态容量的错觉。这里要特别注意动态二字的含义扩容时改变的是内部数组引用的指向而不是把原来那块内存拉长。底层数组依然是连续的、定长的只是不够用了就换一块更大的。这个设计的精妙之处在于数组的随机访问性能优势被 100% 保留付出的代价只是偶尔一次扩容拷贝——而扩容频率随容量增大而指数级降低均摊下来每次 add 的额外成本几乎可以忽略。1.4 为什么 Java 需要 ArrayList如果没有 ArrayList每个开发者都得手写这样的样板代码// 手写版动态数组感受一下没有 ArrayList 的世界 Object[] arr new Object[10]; int size 0; void add(Object e) { if (size arr.length) { // 装满了 Object[] newArr new Object[arr.length arr.length / 2]; System.arraycopy(arr, 0, newArr, 0, size); // 数据迁移 arr newArr; // 切换引用 } arr[size] e; }容量判断、扩容策略、数据拷贝、计数维护——这套逻辑完全通用与业务无关。每个项目都重写一遍既容易写错也无从优化。Java 把它封装成 ArrayList 放进标准库这正是集合框架的基本哲学把重复的通用逻辑沉淀为经过千锤百炼的可复用组件。而且 ArrayList 处理了许多你未必想得到、但工程上至关重要的细节边界检查、序列化性能优化、fail-fast 迭代器、泛型类型安全……标准库组件存在的意义不只是能用而是正确地用、高效地用、安全地用。1.5 ArrayList 与普通数组的区别对比维度普通数组ArrayList长度固定创建后不可变动态不足时自动扩容元素类型基本类型、引用类型均可只能存引用类型泛型不支持基本类型元素计数开发者自行维护内部 size 字段自动维护越界行为ArrayIndexOutOfBoundsExceptionIndexOutOfBoundsException且检查时机更完整类型安全Object[] 可混装任意类型泛型编译期检查适用场景长度已知、极致性能场景数据量未知、绝大多数通用业务场景单独点出元素类型这一行是因为 ArrayList 不能存int只能存Integer——这是泛型擦除机制决定的也是面试高频追问点后文序列化部分会展开。1.6 本章小结本章三个关键结论ArrayList 本质是数组的增强版保留数组的随机访问与缓存亲和优势用扩容机制解决定长问题。底层选数组是权衡的结果查多改少是最普遍的访问模式数组 O(1) 查询 缓存亲和的收益远大于偶尔扩容的拷贝成本。动态数组思想扩容的本质是新数组替换旧数组变的是引用指向不是内存区域本身。下一章我们进入 ArrayList 源码内部剖析elementData、size等核心成员变量为什么用 Object 数组而不是泛型数组为什么elementData要加transient容量和元素数量到底有什么区别第二章ArrayList 底层数据结构深入分析 ArrayList 源码首先看它的核心成员变量transient Object[] elementData; // 私有 private int size; // 私有还有几个重要的静态常量static final int DEFAULT_CAPACITY 10; // 默认容量 static final Object[] EMPTY_ELEMENTDATA {}; // 空的共享实例 static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; // 未初始化占位符2.1 为什么使用 Object 数组而不是泛型数组ArrayList 内部使用的不是E[] elementData而是Object[] elementData。这看起来很奇怪因为 Java 支持泛型那为什么不直接用泛型数组呢原因有二原因一Java 不允许创建泛型数组// 编译错误 ListString[] listArray new ListString[10];编译器拒绝的原因很简单泛型是编译期的伪装的运行时被擦除掉了。new ListString[10]在运行时实际上等同于new List[10]但这会破坏类型安全——你随时可以在这个数组里放Integer、Boolean等等。所以 Java 干脆禁止了泛型数组的创建。既然不能创建E[]就只能退而求其次使用Object[]。ArrayList 内部通过类型转换return (E) elementData[index]把元素转回来这种转换之所以能正常工作依赖的是泛型的桥接方法bridge method和协变返回类型的配合。原因二反射可以绕过泛型检查即使允许创建E[]反射也能突破限制。假设我们写成E[] elementData那么通过反射我们可以ArrayListString list new ArrayList(); Field field ArrayList.class.getDeclaredField(elementData); field.setAccessible(true); Object[] array (Object[]) field.get(list); array[0] new Object(); // 硬塞了一个 Object String s list.get(0); // ClassCastException 发生在这里换成Object[] elementData反而更安全——因为Object[]本来就什么都能存不会给你误以为是泛型数组结果偷偷塞进不同类型的心理陷阱。把风险显式化比藏起来更安全。2.2 transient 关键字为什么存在elementData被标记为transient意味着它在序列化时会被跳过。但 ArrayList 确实能被序列化啊为什么还要加transient答案是为了性能优化。ArrayList 序列化流程是这样的调用writeExternal()或writeObject()循环写入实际有效的size个元素反序列化时读回size个元素重建elementData。如果不加transient序列化的过程会变成自动把整个elementData包括 null 尾巴全部序列化 → 浪费带宽和时间反序列化时也要重建整个数组含 null。有了transientArrayList 可以手动控制序列化只序列化有效元素只重建需要的空间。这对大数组特别有意义。举个例子ArrayListString list new ArrayList(1000); for (int i 0; i 10; i) { list.add(item- i); }此时elementData.length 1000但size 10。如果不用transient序列化时会把这 1000 个位置的引用全写一遍990 个是 null——浪费 90% 的 IO。加了transient只会序列化那 10 个有效元素。2.3 size 代表什么capacity 又是什么这里有两个概念容易混淆size: 实际元素个数即list.size()返回的值capacity: 内部数组长度即elementData.length。它们的关系是0 size capacity。案例 1初始化的瞬间ListString list new ArrayList();size 0elementData还没分配JDK 8 采用延迟初始化策略第三章详解。案例 2加入第一个元素list.add(a);此时触发扩容size 1capacity 10首次扩容的默认值。案例 3扩容后list.add(b); // ... list.add(j); // 第 10 个元素size10, capacity10 list.add(k); // 第 11 个元素触发扩容capacity 变成 15size11工程影响如果你在业务中明确知道要存多少数据一定要提前指定容量ListUser users new ArrayList(expectedCount);否则频繁扩容带来的数组拷贝开销会让你付出真金白银的性能代价第四章、第五章详述。2.4 三种空数组常量的设计意图源码里有几个看起来很啰嗦的空数组static final Object[] EMPTY_ELEMENTDATA {}; static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; abstract static boolean defaultCapacityElmptEmptyElementData 0;为什么要区分两个空数组答案藏在延迟初始化的设计里。JDK 7 的历史包袱JDK 7 及以前无参构造new ArrayList()会直接创建长度为 10 的数组public ArrayList() { this.elementData EMPTY_ELEMENTDATA; // 实际是长度为 10 的数组 }这意味着就算你从来不调用add()也白占了 10 个引用位的空间。JDK 8 的优化方案JDK 8 改成public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }这个占位符的作用是标记我还未初始化等你第一次 add 时再决定到底是多少。为什么要有第二个空数组因为我们需要区分两种情况用户显式创建了new ArrayList(0)——明确表示我就要空列表用户写了new ArrayList()——表示我懒得管你按默认来。前者对应EMPTY_ELEMENTDATA永远不变除非你 add后者对应DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次 add 时扩到 10。设计意图用最小的内存占用换取最大的灵活性。不用的时候不占空间用的时候才按需分配。这就是延迟初始化思想的体现第三章详细拆解。第二章小结通过本章分析我们得出以下关键结论用Object[]而非E[]是妥协的结果Java 不允许创建泛型数组加上反射可绕过的安全问题只能用Object[] 强制转换的组合拳。transient是为了序列化性能优化只序列化有效元素避免浪费 IO。size 与 capacity 是两个独立概念容量可以远超实际需求提前规划能避免扩容开销。空数组占位符的区分是为了支持延迟初始化DEFAULTCAPACITY_EMPTY_ELEMENTDATA用于标记待初始化状态EMPTY_ELEMENTDATA用于标记已明确为空状态。下一篇进入初始化源码的深入剖析重点讲解 JDK 8 延迟初始化背后的权衡。下期见~