手写 Java 动态数组ArrayList从泛型原理到 1.5 倍扩容机制的全量实现本文基于一次 Java 课程的核心内容实现一个支持泛型、自动扩容、指定位置插入、去重添加与自定义排序的动态数组ZArrayListE。我们将从集合框架的分类讲起了解泛型的类型模板机制逐行实现核心功能并对扩容策略与时间复杂度进行严谨分析。一、前言为什么要手写动态数组在日常开发中ArrayList是使用频率最高的集合类之一。但会用和理解之间隔着一层窗户纸它如何做到容量自动增长为什么 JDK 优先选择1.5倍扩容而不是 2 倍泛型 在编译期和运行期分别做了什么很多成熟代码中大量篇幅其实用于性能优化、特殊场景兜底、安全与合规校验而核心逻辑往往只占一小部分。亲手实现一个动态数组是捅破这层窗户纸最有效的方式。补充JDK 是什么AI生成在动手实现之前先厘清一个贯穿全文的基础概念——JDK。JDKJava Development KitJava 开发工具包是 Oracle及 OpenJDK 社区提供的 Java 开发环境集合是编写、编译、调试、运行 Java 程序所必需的一整套工具。它包含三个层次组成全称作用JVMJava Virtual MachineJava 虚拟机负责加载并执行字节码是一次编写、到处运行的根基JREJava Runtime EnvironmentJava 运行时环境 JVM 核心类库只能运行 Java 程序不能编译JDKJava Development KitJava 开发工具包 JRE 编译器javac、调试器jdb、打包工具jar、文档工具javadoc等开发工具三者的包含关系可以简单记为JDK ⊃ JRE ⊃ JVM。只运行不开发装 JRE 即可要写代码、编译源码就必须装 JDK。JDK 中几个最常用的命令javac HelloWorld.java# 编译把 .java 源码编译成 .class 字节码javaHelloWorld# 运行由 JVM 加载并执行字节码javadoc-ddoc src/# 生成 API 文档本文后面讲到的文档注释就靠它javap-cZArrayList# 反编译字节码查看泛型擦除后的真实方法签名版本说明JDK 目前按半年一个特性版本迭代JDK 8、11、17、21……其中 8、11、17、21 为长期支持版LTS。本文的示例代码基于JDK 17ArrayList的源码分析同样以 JDK 17 为准代码本身只用到泛型、数组与Arrays.copyOf等基础 API在 JDK 8 及以上版本均可直接编译运行。顺带一提本文提到的JDK 源码指的就是 JDK 安装目录下src.zip中附带的 Java 标准库实现代码解压后即可在 IDE 中直接跳转阅读java.util.ArrayList的原始实现——这是学习集合框架最权威的一手资料。二、集合框架Java 集合框架Java Collections Framework按数据组织形式可以划分为三大体系体系核心结构典型实现数据特征线性表List数组、链表、队列、栈ArrayList、LinkedList元素有序、可重复、可按索引访问集合Set基于数组/链表/哈希组织HashSet、TreeSet元素不重复键值对Map哈希表、红黑树HashMap、TreeMapKey-Value 映射存储三、泛型类型模板符号的机制剖析3.1 泛型的定义与规则泛型Generics是一种类型模板符号。定义类时在类名右侧写括号内用一个字母如E、T、K、V也可以是一个单词来代表一种未知的类型。此后在类的内部所有需要类型声明的地方——参数类型、返回值类型、转型类型——都可以使用这个泛型名替代。使用泛型必须遵守四条核心规则1.泛型名只能做类型占位符不能实例化对象。new E()是非法的因为编译期无法确定 E 的实际类型也无法调用其构造方法2.创建对象时指定具体类型。new ZArrayListString()会将类中所有E替换为String3.替换是全方法的。使用该对象调用方法时方法的参数类型与返回值类型都会替换为具体类型从而获得编译期类型检查免除强制转换4.不指定泛型则默认为 Object。如果创建对象时未指定类型裸类型/raw type所有泛型位置默认按Object处理。3.2 为什么底层用 Object 数组Object是 Java 所有类的隐式父类未显式extends时默认继承Object因此Object[]数组可以存储任何引用类型。JDK 的ArrayList同样采用这一方案privateObject[]elementData;// Object 数组什么类型都能存对外接口则通过泛型E约束.四、类设计属性与构造方法4.1 核心属性一个动态数组最少需要两个状态量这是本类设计的基石属性类型含义elementDataObject[]真正存储元素的底层数组sizeint数组中实际元素个数同时是新元素待写入的下标注意size逻辑长度用户视角数组里装了多少个元素capacity物理容量内存视角底层数组一共能装多少个元素。容量信息可以直接通过elementData.length获取无需冗余字段教学版代码中若单独维护length字段必须保证其与elementData.length严格同步否则极易引发越界 BugJDK 源码中也不单独维护该字段。4.2 构造方法与合法性校验初始化时必须对传入的容量参数进行合法性判断这是防御式编程的基本要求publicclassZArrayListE{/** 默认初始容量与 JDK ArrayList 保持一致 */privatestaticfinalintDEFAULT_CAPACITY10;/** 底层存储数组使用 Object 类型可容纳任意引用类型 */privateObject[]elementData;/** 数组中实际元素的个数同时也是新元素待写入的下标 */privateintsize;/** 无参构造使用默认容量 */publicZArrayList(){this(DEFAULT_CAPACITY);}/** * 指定初始容量构造 * param initCapacity 初始容量 * throws IllegalArgumentException 容量小于等于 0 时抛出 */publicZArrayList(intinitCapacity){if(initCapacity0){thrownewIllegalArgumentException(初始容量必须为正数: initCapacity);}this.elementDatanewObject[initCapacity];}/** * 查询当前元素个数 * return 实际元素个数 */publicintsize(){returnsize;}/** * 判断集合是否为空 * return 为空返回 true */publicbooleanisEmpty(){returnsize0;}}设计要点容量常量使用static final修饰——它属于类级别的规则所有实例共享且不可修改下限校验直接抛出IllegalArgumentException而不是改为默认值让调用方在第一时间感知错误。五、核心功能实现增、插、删、查、改5.1 扩容机制1.5 倍增长策略先定义统一的扩容方法它是所有添加类操作的公共依赖/** * 扩容至至少满足 minCapacity 的容量需求 * 扩容策略新容量 旧容量 * 1.5若仍不足则直接扩至 minCapacity * param minCapacity 最小需要的容量 */privatevoidgrow(intminCapacity){intoldCapacityelementData.length;intnewCapacityoldCapacity(oldCapacity1);// 位运算等价于 oldCapacity * 1.5if(newCapacityminCapacity){// 一次批量插入的元素过多1.5 倍仍不够一次性扩容到位避免多次迁移newCapacityminCapacity;}// Arrays.copyOf按新容量创建数组并复制旧元素等价于新建 for 循环搬运 换引用三步elementDataArrays.copyOf(elementData,newCapacity);}为什么是 1.5 倍扩容倍数过小如 1.1 倍→ 扩容频繁每次扩容都要整体搬迁数组均摊成本高扩容倍数过大如 2 倍以上→空闲空间浪费严重内存利用率低oldCapacity (oldCapacity 1)使用位运算 1完成÷2比乘除法指令效率更高且当容量超过Integer.MAX_VALUE / 2时不易溢出到负数。批量插入场景的优化addAll一次追加 N 个元素时若按单元素逻辑逐次触发扩容可能发生多次数组搬迁。正确做法是先计算总需求、一次性扩容到位/** * 末尾批量添加元素 * param es 待添加的元素数组 */publicvoidaddAll(E[]es){if(esnull||es.length0){return;}intneedsizees.length;// 添加后的总需求容量if(needelementData.length){grow(need);// 一次性扩容到位}for(inti0;ies.length;i){elementData[size]es[i];}}关于旧数组的内存回收扩容后旧数组不再被elementData引用会成为不可达对象JVM 的垃圾回收器会自动回收其占用的内存无需程序员干预。课程代码中出现的System.gc()只是建议JVM 尽快执行一次回收并不能强制立即回收生产代码中不应依赖它。5.2 添加元素末尾追加 O(1)/** * 末尾添加单个元素 * param e 待添加的元素 * return 添加成功返回 true */publicbooleanadd(Ee){if(sizeelementData.length){grow(size1);// 数组已满先扩容再存入}elementData[size]e;returntrue;}5.3 指定下标插入整体后移 O(n)指定下标插入需要先判断扩容再将[index, size-1]区间的所有元素整体向后挪动一位腾出目标位置后写入/** * 指定下标插入单个元素 * param index 插入位置取值范围 [0, size] * param e 待插入的元素 * throws IndexOutOfBoundsException 下标越界时抛出 */publicvoidinsert(intindex,Ee){if(index0||indexsize){thrownewIndexOutOfBoundsException(下标越界: index, 合法范围: [0, size]);}if(sizeelementData.length){grow(size1);}for(intisize-1;iindex;i--){// 从最后一个元素开始逐位后移elementData[i1]elementData[i];}elementData[index]e;size;}常见坑插入场景下index size是合法的等价于末尾追加因此越界判断的上界是 size 而非 size - 1同时注意挪动循环必须从后往前遍历若从前往后挪会用前面的值覆盖后面未搬移的元素。批量插入同理先扩容、再挪动size - index个元素、最后写入此处从略。5.4 去重添加去重添加的原则是先扩容判断 遍历查重确认不存在后再追加避免重复元素反复进入数组。实现如下/** * 去重添加数组中已存在该元素时不再添加 * param e 待添加的元素 * return 实际添加成功返回 true元素已存在返回 false */publicbooleanaddUnique(Ee){if(contains(e)){returnfalse;}returnadd(e);}/** * 批量去重添加 * param es 待添加的元素数组 */publicvoidaddAllUnique(E[]es){for(Ee:es){addUnique(e);}}注意查重依赖equals方法比较元素自定义类如User若要正确去重需要重写equals()与hashCode()。5.5 删除、查询与修改/** * 删除指定下标的元素后续元素整体前移 * param index 待删除下标 * return 被删除的元素 */SuppressWarnings(unchecked)publicEremove(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(下标越界: index);}EoldValue(E)elementData[index];intnumMovedsize-index-1;// 需要前移的元素个数if(numMoved0){System.arraycopy(elementData,index1,elementData,index,numMoved);}elementData[--size]null;// 置 null帮助 GC 尽快回收失效引用returnoldValue;}/** * 按内容删除第一个匹配的元素 * param e 目标元素 * return 删除成功返回 true */publicbooleanremove(Ee){intindexindexOf(e);if(index0){remove(index);returntrue;}returnfalse;}/** * 返回元素首次出现的下标 * param e 目标元素 * return 存在返回下标不存在返回 -1 */publicintindexOf(Ee){for(inti0;isize;i){if(enull?elementData[i]null:e.equals(elementData[i])){returni;}}return-1;}/** * 判断元素是否存在 */publicbooleancontains(Ee){returnindexOf(e)0;}/** * 获取指定下标的元素 */SuppressWarnings(unchecked)publicEget(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(下标越界: index);}return(E)elementData[index];}/** * 替换指定下标的元素返回旧值 */SuppressWarnings(unchecked)publicEset(intindex,Ee){if(index0||indexsize){thrownewIndexOutOfBoundsException(下标越界: index);}EoldValue(E)elementData[index];elementData[index]e;returnoldValue;}两个细节1.从Object[]取元素时必须强制转型为 E并标注SuppressWarnings(unchecked)抑制编译器警告——由于泛型擦除转型在运行期是安全的2.remove 后将数组尾部槽位置nullelementData[--size] null及时切断失效引用避免内存泄漏这正是JDK ArrayList.remove的标准写法。5.6 遍历打印/** * 打印数组中的实际元素 */publicvoidprintArr(){StringBuildersbnewStringBuilder(数组元素为【);for(inti0;isize;i){sb.append(elementData[i]);if(isize-1){sb.append( );}}sb.append(】 size ).append(size);System.out.println(sb);}六、排序Lambda 表达式与标准比较器对自定义类型如按年龄排序的 User排序时有两条技术路线二者本质都是实现比较规则、返回正数 / 负数 / 0 来决定元素的左右位置是否交换返回正数则交换降序返回负数或 0 则保持升序。6.1 Lambda 表达式// 按年龄降序o2 排在前面时返回正数list.sort((o1,o2)-o2.age-o1.age);6.2 匿名内部类实现 Comparator 接口结构清晰// 按年龄升序o1 - o2 为负数或 0 时保持原顺序list.sort(newComparatorUser(){Overridepublicintcompare(Usero1,Usero2){returno1.age-o2.age;}});提示o1.age - o2.age这种减法写法在年龄等小范围数值上安全但若字段值可能接近Integer.MAX_VALUE减法会溢出标准写法应使用Integer.compare(o1.age, o2.age).七、测试验证运行输出节选 text 复制 数组元素为【0123456100712345612312234123245123666】 size24indexOf(123)1519181716151413121110...降序输出10111213141516171819...升序输出八、复杂度分析与常见问题8.1 时间复杂度一览操作时间复杂度说明末尾添加add均摊 O(1)偶发扩容的搬迁成本被均摊指定下标插入insertO(n)平均需移动 n/2 个元素删除removeO(n)平均需前移 n/2 个元素按下标查询getO(1)数组随机访问特性按内容查询indexOfO(n)线性扫描扩容growO(n)整体搬迁一次8.2 常见易错点汇总size与capacity混用遍历时必须以size为上界若误用elementData.length会把未使用的槽位一并打印出来输出一堆null插入不校验下标index size或负数下标会直接破坏数据或抛出越界异常应在方法入口统一校验从前往后挪动元素插入时的元素后移必须从尾部开始否则前面的值会覆盖尚未搬移的元素裸类型使用集合new ZArrayList()不指定泛型会退化为Object丧失编译期类型检查依赖System.gc()回收内存扩容后的旧数组由 GC 自动回收手动调用只是建议不应作为内存管理手段。九、总结本文完成了一个教学版动态数组的全量实现核心收获可以浓缩为四点泛型是类型模板符号定义期占位、使用期替换、不能实例化缺省时退化为Object动态数组的灵魂是size与elementData的分工size管逻辑边界底层数组管物理容量1.5 倍扩容 一次性到位是空间与时间的经典折中单元素添加走 1.5 倍批量插入则按总需求直接扩容排序的通用范式Lambda 或Comparator提供正数交换、负数保持的比较规则即可实现升序或降序。课后练习建议按由易到难排序补全removeRange(int fromIndex, int toIndex)区间删除实现按条件查询返回满足条件的元素子集合用链表重新实现一遍线性表并与本文实现对比各操作的性能差异在此基础上完成队列Queue与栈Stack的封装。