1. 动态数组在Java学习路线里的位置1.1 为什么Step1一定要啃下动态数组很多人学Java的第一步是照着教程敲一遍Hello World然后背数据类型、if、for循环接着就卡在了集合框架上。原因是教材总把ArrayList、HashMap这些东西当成“工具”教告诉你怎么add、怎么get却很少讲清楚它底层究竟做了什么。结果写了两年代码的人被面试官问一句“ArrayList扩容机制是怎样的”照样懵。动态数组就是捅破这层窗户纸的地方。它属于基本数据结构里的线性表同时又嵌着Java基础语法里的类、泛型、方法重载、数组拷贝这些核心知识点。说白了动态数组是一个把“基本语法”和“数据结构”拧在一起的小项目。我见过很多学习路径有的先系统啃语法再碰数据结构有的直接刷算法题用集合类都不如自己在Step1阶段手写一个动态数组效率高。这里想先说清楚本文说的动态数组不是让你去用Java自带的ArrayList而是带你从零手写一个支持自动扩容的一维数组容器。写完之后你再看ArrayList源码基本就是看自己的代码被优化过的版本理解成本会骤降。1.2 动手前必须掌握的基础语法清单既然标题里挂了“基础语法”就得先摆出这块需要预备的知识点。我不推荐零基础的人直接上手写动态数组但也不是说要完全学完语法再来只需要掌握以下几条就可以边写边补类和对象知道怎么定义一个类、写构造方法明白this指代当前对象。方法定义与重载add方法可能有不同参数版本靠方法签名区分。数组的创建与拷贝new int[10]、Arrays.copyOf或System.arraycopy的基本用法。泛型入门能用E或T标识元素类型写一个能装任意对象的容器。异常基础了解IndexOutOfBoundsException、IllegalArgumentException什么时候该抛。如果上述知识还比较模糊先去刷两天基础语法题再回来写动态数组会顺畅很多。我当时学的时候是语法书看了三章就直接上手写边写边查API文档遇到错误看堆栈反而比纯背语法记得牢。动态数组这个项目的妙处就是它强迫你同时使用语法、调试工具和数据结构设计思维。2. 动态数组的核心设计思路拆解2.1 从静态数组的痛点引出设计目标先把问题还原一下。原生数组一旦创建长度就不能改变int[] arr new int[5]; arr[0] 1; arr[1] 2; // 想存第6个元素做不到。这种设计在内存管理上是高效的但业务场景里你经常不知道数据最终会有多少条。从用户输入、文件读取、网络请求里拿到一批数据总不能先数一遍再建数组。动态数组要解决的只有一个核心问题让数组在运行时按需增长。但“按需”两个字展开来看藏了三个设计目标对外行为透明使用者只管调用add、get、remove不需要关心内部数组被换了几次。性能和空间平衡不能每次新增元素都重建数组那样时间复杂度会爆炸也不能一次性把容量顶得太大浪费内存。边界行为明确越界访问必须报错而不是返回垃圾值或者静默处理。这三个目标对应到代码层面分别是封装、扩容策略、边界检查。我见过初学者写的动态数组内部数组是public的扩容全靠拷贝大数组get和set方法里完全没有边界判断崩溃全靠运气这是把“数据结构”写成了“工具类”没有抓住设计本质。2.2 为什么扩容策略是动态数组的灵魂这是整个项目里最值得花时间琢磨的一块。一个成熟的动态数组扩容策略直接决定它在频繁插入场景下的运行效率。先说最简单的方案每次插入新元素时如果数组满了就新建一个长度1的数组把所有元素拷贝过去。这个方案思路直白代码也好写但性能很差。假设要插入n个元素每次插入都可能触发拷贝总操作次数是123...n也就是O(n²)级别。n小的时候没关系n到一万以上卡顿肉眼可见。业内通用的做法是“成倍扩容”。Java的ArrayList默认扩容到原来的1.5倍很多C的vector是2倍。我用的是扩容到原来的2倍。为什么是2倍而不是1.5倍、3倍这里有一个摊销时间复杂度的计算逻辑假设当前容量为C每次扩容到2C那么前C次插入不需要扩容后面扩容一次累计拷贝2C个元素。把拷贝成本摊到每次插入上平均下来每次插入的操作量是O(1)。这就是“均摊常数时间”的来源——比O(n²)方案不知道高到哪里去了。从内存角度来看2倍扩容意味着数组末尾有一段闲置空间。忽略它就是浪费利用它就得做缩容设置一个扩容时容量翻倍、删除时容量减半还要防止频繁震荡一边扩容一边缩容导致反复拷贝。我在这个项目里采用了一个简化的缩容策略当元素个数只有容量的四分之一时才把容量缩到一半。这样给“删除”预留了缓冲空间避免在边界上反复重建数组。具体实现后面会贴核心代码。2.3 泛型与Object数组的类型陷阱写动态数组时如果你想让它能装任意类型的数据就得引入泛型。这里藏着一个Java特有的坑不能直接创建泛型数组。// 编译报错 E[] data new E[capacity];合法写法是先建一个Object数组再做强制类型转换SuppressWarnings(unchecked) E[] data (E[]) new Object[capacity];我在初学阶段经常把这个警告直接忽略后来才意识到SuppressWarnings(unchecked)不是让你“屏蔽报错就算了”而是在你已经确保安全的前提下告诉编译器“这里我负责”。手动写动态数组跟用ArrayList不一样ArrayList里你可能从没关注过这个细节但手写时它会被直接暴露出来。如果你不理解为什么会有这个转换建议去查一下Java数组的协变特性和泛型擦除这会帮你彻底理解Java类型系统的历史包袱。这块知识面试也常考属于“简历里写熟悉集合源码”必须答上来的点。3. 手写动态数组完整实现与步骤详解3.1 基础架子字段、构造方法、扩容方法下面给出我维护的一个简化版动态数组实现去掉了并发控制和迭代器只保留核心逻辑方便你一步一步对照。import java.util.Arrays; public class DynamicArrayE { // 真正存数据的数组 private E[] data; // 当前已存元素个数 private int size; // 默认初始容量 private static final int DEFAULT_CAPACITY 10; public DynamicArray() { this(DEFAULT_CAPACITY); } SuppressWarnings(unchecked) public DynamicArray(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数); } data (E[]) new Object[capacity]; size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } public int getCapacity() { return data.length; } }这段代码有五个细节值得注意。第一size和data.length是两回事。size是逻辑长度表示容器里有多少个元素data.length是物理容量。很多初学者把两者混为一谈写add方法的时候要么用data.length判断满不满要么直接data[size] elem却不更新size代码一会儿就崩了。第二无参构造器里调用this(DEFAULT_CAPACITY)这是构造器互相调用的写法目的是避免代码重复。Java要求this(...)必须出现在构造器第一行。第三容量传入负数时抛IllegalArgumentException。这是防御式编程的入门动作对外暴露的入口必须把非法输入挡在外面。第四SuppressWarnings(unchecked)的位置是方法级别用来压住“类型转换可能不安全”的编译警告。这里转换确实不安全因为Object[]在运行时并不知道自己里面装了E类型但我们用泛型约束了所有写入操作所以内部是安全的。第五getCapacity方法暴露物理容量方便测试和观察扩容行为实际项目中这个接口也很有用可以监控容器内存占用。接下来是扩容逻辑。这是动态数组的核心引擎private void grow() { int oldCapacity data.length; // 防止溢出如果oldCapacity已经很大直接扩大为oldCapacity 1 int newCapacity; if (oldCapacity 0) { newCapacity 1; } else if (oldCapacity (Integer.MAX_VALUE - 1) / 2) { // 避免 newCapacity oldCapacity * 2 溢出int newCapacity oldCapacity 1; } else { newCapacity oldCapacity * 2; } data Arrays.copyOf(data, newCapacity); }这个grow方法看着简单其实有两个坑。第一个坑是oldCapacity * 2可能溢出int最大值。比如初始容量已经在10亿以上翻倍直接变成负数Arrays.copyOf收到负数容量会抛NegativeArraySizeException。上面代码里先判断oldCapacity (Integer.MAX_VALUE - 1) / 2正数乘以2即将超过最大值时就不再翻倍了改成1。这是写通用容器类时必须考虑的边界安全。第二个坑是Arrays.copyOf底层做了什么。它是Java提供的高效数组拷贝方法内部本质是System.arraycopy是一个本地方法速度比手动for循环拷贝快很多。所以写代码不要自己写拷贝循环用官方提供的方法即可。3.2 新增元素尾部追加与按索引插入有了扩容方法新增就简单了。我先写add尾部追加public void add(E element) { if (size data.length) { grow(); } data[size] element; size; }size恰好是下一个空闲位置的索引比如当前有5个元素size就是5新元素放在data[5]。扩容判断放在写入之前保证写入时数组一定有空位。按索引插入就麻烦一点需要把插入位置之后的元素整体后移一位public void add(int index, E element) { // 允许 index size相当于尾部追加 if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置越界: index); } if (size data.length) { grow(); } // 从最后一个元素开始依次后移一位 for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] element; size; }这里最容易写错的地方是后移的遍历顺序。如果从index开始往右挪会把后面的元素覆盖掉。必须从size - 1开始倒着往前挪。你可以拿一个只有4个元素的数组自己比划一下正着挪一次数据必丢倒着挪一次每个元素都安全移动一格。另外index允许等于size这是插入到末尾的意思与add(element)行为一致。如果index size说明中间存在“空隙”这种数据结构不允许有空隙要直接抛异常。我在开发中遇到过不少同事对这种边界情况不加判断结果线上数据错乱之后排查到是插入越界实属不该。3.3 删除元素按索引删除与按值删除删除逻辑和插入是对称的却是另一个容易出错的点。public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置越界: index); } E oldValue data[index]; // 从 index 之后的所有元素前移一位 for (int i index 1; i size; i) { data[i - 1] data[i]; } size--; data[size] null; // 释放引用避免内存泄漏 // 缩容策略元素个数只有容量四分之一时容量减半 if (size 0 size data.length / 4) { shrink(); } return oldValue; }删除元素之后最后一个位置data[size]还留着被删除对象的引用在泛型容器里这会导致“对象无法被垃圾回收”的问题专业说法是“内存泄漏”其实更像是在花园里藏了不再使用的花盆你不专门清理它就一直在那。把最后一位置为null是好习惯。返回被删除的元素值可以让调用方式更灵活也是ArrayList的做法之一。按值删除则是先找到目标的索引再复用上面的逻辑public boolean remove(Object element) { int index indexOf(element); if (index -1) { return false; } remove(index); return true; } public int indexOf(Object element) { for (int i 0; i size; i) { if (element null ? data[i] null : element.equals(data[i])) { return i; } } return -1; }这里有一个细节允许元素为null时比较逻辑必须处理空指针。用三元表达式或者Objects.equals(element, data[i])都可以。Objects.equals是JDK 7以后推荐的写法内部已经处理了双方都为null的情况比三元表达式更简洁。写到这里动态数组的骨架已经能跑起来了增、删、查、扩容全部齐活。但跑起来只是第一步你还要理解为什么这么写、性能如何、和官方实现有何差异。4. 性能分析与参数选择的经验之谈4.1 插入操作的三种形态与时间复杂度对一个动态数组来说“插入”不是一个统一的概念要分场景看待。尾部插入大多数情况下不需要扩容直接data[size] elem时间复杂度O(1)。需要扩容时极端单次操作是O(n)但均摊下来仍是O(1)。头部插入每次都要把所有元素后移一位单次O(n)。如果业务确实需要频繁头部插入动态数组就不是合适的数据结构了应该选用链表或者ArrayDeque。随机位置插入平均移动n/2个元素单次O(n)。元素量小没事元素量大且插入频繁性能就会明显恶化。这个分析直接关系到实际开发里对容器的选型。我经常碰到有人用ArrayList做消息队列频繁从头部取出数据结果在压测阶段CPU飙高换成LinkedList反而更慢——因为LinkedList在内存里不连续缓存命中率低。性能问题要具体场景具体分析动态数组的优势场景是“下标随机访问”和“尾部增删”。4.2 初始容量、扩容因子和缩容阈值怎么设这三个参数是动态数组可调的核心旋钮参数默认方案适用场景初始容量10通用省内存初始容量1000预先知道数据量很大减少扩容次数扩容因子1.5~2倍追求性能用2倍追求省内存用1.5倍缩容阈值size 容量/4避免频繁删除时在扩容缩容边界来回震荡从小到大各解释一句。初始容量设10是经典的“懒加载”思路是工程上长期验证出来的经验值大部分小场景下够用又不至于一创建就分配很大的内存。如果你明确知道要装5000条数据直接new DynamicArray(5000)省去4次扩容和拷贝性能好不少。扩容因子用2倍是简单粗暴的选择数学上好分析均摊成本常数很小Java源码用1.5倍是经过内存利用率斟酌的扩容后旧数据占三分之二、空闲占三分之一相对更省内存。从测试结果看1.5倍和2倍在真实业务上有差别但没有天壤之别。你如果写通用容器可以学Java用1.5倍如果追求极致写性能敏感的代码可以用2倍。缩容阈值设在四分之一的逻辑是这样的假如容量10万、元素只有1个这套数组占了10万个引用位是真浪费。但如果只在size小到容量/2就缩容删除发生在边界上时每次删除都可能触发缩容随后插入又触发扩容造成“抖动”。设成四分之一等于给了删除操作两倍的缓冲空间。5. 对照ArrayList源码看看官方怎么优化5.1 ArrayList的扩容细节与modCount机制如果你已经手写完了动态数组再翻ArrayList源码会发现很多地方是“熟悉的配方”但也有几个第一眼看不懂的优化点。第一个是ArrayList的扩容并不是总是走grow(int minCapacity)而是先看minCapacity够不够当前容量不够才扩容。这看起来是多此一举其实是避免频繁调用ensureCapacity时做无用的数组拷贝。我们手写版只在add时检查一次官方版把这个检查封装得更细但核心思路一致。第二个是modCount字段。每次结构性修改增、删、扩容都会让modCount。它的作用是配合迭代器做“快速失败”检测如果在迭代过程中发现集合被修改了就抛ConcurrentModificationException。这也是一个经典的设计模式——用一个计数器把并发修改的风险显式暴露出来而不是让迭代器默默返回脏数据。第三个是ArrayList把elementData数组声明为transient。序列化时它会单独遍历size范围内的元素写入流而不是直接序列化整个数组。这么做的原因是数组里可能有大量null空位用默认序列化方式会浪费空间和时间。5.2 手写版与ArrayList的差距在哪里手写动态数组和官方ArrayList的差距主要不是“会不会写”而是“考虑了几个层级”。第一层功能可用性。我的版本提供了add、remove、get、set、size、indexOf已经能应付绝大多数基础需求。但官方还有addAll、removeAll、retainAll、subList、iterator、listIterator等一批批量操作和视图操作。这些方法每一个背后都有一层边界条件的考量和迭代器配合的细节。第二层性能微优化。官方使用了System.arraycopy、Arrays.copyOf、ArrayList是延迟初始化第一添加元素才分配数组。这些优化单个看不复杂组合起来就让ArrayList的性能在大多数场景下优于手写实现。第三层并发和序列化。这两块手写容器一般不会涉及但真正的工业级容器必须考虑。如果你想进阶可以研究一下CopyOnWriteArrayList它采用“写时复制”策略适合读多写少的并发场景是动态数组思想在并发领域的一个漂亮延伸。我推荐对照学习的方法是把手写版跑通之后去ArrayList.java源码里逐一注释自己觉得“多余”的代码再分析去掉它们会发生什么。这个过程会让你的代码品味显著提升。6. 动态数组在面试题与算法场景里的典型用法6.1 面试常考的三类动态数组题目讲完实现和源码我们切换一下视角看看面试官怎么考这个知识点。第一类是“ArrayList和数组有什么区别”。这类题的得分点在于数组定长、支持基本类型、连续内存ArrayList变长、只能装引用类型泛型不支持基本类型、扩容有开销。能答出“ArrayList的底层就是数组”和“ArrayList不能存int但能存Integer”的人基本能过初筛。第二类是“手写一个动态数组”。面试官通常不会让用ArrayList而是考察你能否从零实现扩容插入删除。核心采分点是扩容的时机、拷贝方向、边界检查、缩容策略。如果你能主动讲出“均摊复杂度O(1)”说明你是真的理解而不仅是背代码。第三类是“基于动态数组的算法题”。最典型的就是“合并两个有序数组”和“删除有序数组的重复项”还有蓝桥杯、华为OD这类笔试里几乎每年都有的“数组循环移动”。做题的时候ArrayList可以直接用但面试官经常多加一句“不能用库里的动态数组自己实现”。这时候你手里的手写模板就能直接迁移用System.arraycopy做移动用扩容方法做大数组拼接。6.2 动态数组在冒泡排序和基础算法中的实际用法算法题里最常见的配套用法就是排序。以冒泡排序为例很多人用for循环嵌套写public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }这里用的是静态数组因为排序要求原地操作。但如果输入是动态数组排序逻辑和静态数组完全一样差别只在获取元素的下标和size()方法调用上。这说明一个重要的迁移思维算法题里习惯用静态数组是因为它性能可控、语法简洁但真实项目里业务数据的量是动态的用动态数组写算法的核心逻辑完全不耽误。另一个常见场景是从文件或网络逐行读取数据存入容器。我在实际开发里做过一个配置解析器需要把不定条目的配置项按顺序读进内存直接用动态数组尾部追加即可省去统计行数和预分配数组的步骤。6.3 从动态数组到其他数据结构的迁移启发把动态数组搞懂之后往其他数据结构迁移会轻松很多。举三个例子栈可以直接拿动态数组当底层存储只暴露push和pop两个操作就是“限制了一端操作的动态数组”。队列如果用动态数组做队列头部出队的效率低所以更推荐ArrayDeque它用循环数组解决“头部删除”效率问题。哈希表JDK 8的HashMap在链表长度超过8时转红黑树但它的内部数组也是会扩容的。理解了数组扩容和哈希重分布的原理看HashMap的源码会让你产生一种“不过如此”的错觉。所以动态数组在数据结构学习里像是一个多功能跳板。学透它后面的链表、队列、栈、树都有了一个参照物。学不透它后面看源码、调优、刷题都会觉得哪哪都别扭。7. 学习过程中的常见问题与排查技巧7.1 编译报错与运行异常的对照速查我在带初学者写动态数组的过程中总结了一张高频错误速查表。也分享给你现象可能原因解决方法ClassCastExceptionObject[]转E[]后内部实际存放了错误类型检查所有写入方法是否经过泛型约束IndexOutOfBoundsExceptionindex越界检查add和remove的边界判断是否用了size而不是data.lengthNullPointerExceptionremove(Object)里直接用element.equals改用Objects.equals或者先判断null扩容后数据丢失插入/删除时遍历顺序错误插入删除统一遵循“倒着后移、正着前移”口诀NegativeArraySizeException扩容时newCapacity溢出int参考上面的grow方法做溢出保护ConcurrentModificationException迭代过程中修改了容器改成用迭代器的add/remove方法或者copy一份再遍历这里第一栏的ClassCastException是大坑我当时自己也踩过。原因是某个remove方法把Object强制转成E时错误地使用了不安全的类型转换。解决思路其实不复杂要相信泛型约束而不是在运行时判断类型。7.2 调试动态数组的三个实用技巧写这个项目最容易卡住的地方不是语法而是“自己看不见数组内部状态”。推荐三个实测有效的调试方法。第一个是肉眼观察法。在关键操作点打印size和data.lengthSystem.out.println(add后 size size , capacity data.length);这样你能直观看到扩容是在第几次add后触发缩容是删到第几个元素后触发。这个习惯对理解“均摊复杂度”特别有用看着capacity从10跳到20再跳到40就等于用眼睛看到了扩容过程。第二个是断言调试法。强烈建议在indexOf、remove、grow方法里加上assert或临时校验assert size data.length : size不能大于capacity;JVM默认不开启断言测试时要加-ea参数。用断言的目是让逻辑错误在离出错点最近的地方暴露而不是等到最后运行结果不对了再回溯。第三个是借助IDE的调试器。在grow方法里打断点逐步看data数组中各元素的值效果比打印强十倍。看一遍拷贝过程你就不会再忘记为什么System.arraycopy的用法是那五个参数了。7.3 从编码规范角度看这个项目的自我修养最后说一点容易被忽略但长久受益的事写动态数组虽然是个小项目但它是养成编码习惯的绝佳训练场。命名上size和capacity必须区分grow和shrink动词要准确remove和delete别混用。规范不是束缚而是为了半年后你自己回头看代码时不用靠猜。注释上给grow方法写清楚“为什么选择翻倍策略”、给缩容条件写清楚“为什么是四分之一”这些信息比注释每一行data[size] null重要得多。注释应当解释原因和意图而不是复述代码本身。测试上别只测开心路径。至少覆盖这几类用例空容器上add、空容器上remove、插入到头部、插入到尾部、删除到只剩一个元素、删除空容器、扩容后再删除到缩容。我见过有人把容器写到remove后size变成负数就是在“空容器删除”这种边界用例上露馅的。把这些用例写成单元测试项目才算真正闭环。这一步学完之后我个人的建议是不要急着往下学链表而是先做一个“动态数组冒泡排序”的小综合练习往数组里随机塞50个数排序再删除指定元素最后打印结果。把动态数组用熟到形成肌肉记忆再进入下一个学习阶段后面的路会顺很多。