文档教程知识库【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址https://gitcode.com/doocs/source-code-hunter点击查看免费下载本文是 doocs/source-code-hunter 项目中 JDK 集合框架系列文章之一以 JDK 1.8 的ArrayList源码为对象完整拆解其初始化、add/set/get/remove与动态扩容的实现细节并提供一个可运行的自实现版本用于对照学习。读完本文你将能说清 ArrayList 的扩容公式、数组拷贝时机、modCount快速失败机制及其与Vector、LinkedList的取舍从而在面试中从会用进阶到讲透。ArrayList 是日常开发中出现频率最高的集合类之一也是面试的高频考点。它底层基于数组实现具备随机读快、随机写与扩容慢的鲜明特性。本仓库的定位正是从源码层面剖析互联网主流技术的底层实现原理见 README.md本文将延续这一思路把 ArrayList 的源码掰开揉碎讲清楚。一、写给小白ArrayList 的简单使用技巧先从一个完整的可运行 demo 入手熟悉 ArrayList 最常用的五个方法add(element)添加元素、get(index)获取下标元素、remove(index)移除下标对应元素、set(index, element)修改指定位置元素、size()获取元素个数。/** * 编写一个ArrayList的简单实用demo * ArrayList 的常见方法包括 * add(element):添加元素 * get(index):获取下标元素 * remove(index):移除下标对应元素 * set(index,element):将index处的元素修改为element */ public class arrayList { public static void main(String[] args) { // 创建 ArrayList 的对象 ArrayList al new ArrayList(); // 添加元素 al.add(finky); // 构造随机数并进行添加 Random rnd new Random(); for (int i 0; i 20; i) { al.add(rnd.nextInt(1000)); } // 取出ArrayList里的元素进行打印 for (int i 0; i al.size(); i) { System.out.print(al.get(i) ); } // 修改0号index成的元素为doocs System.out.println(); al.set(0, doocs); System.out.println(al.get(0)); // 移除“doocs”元素 al.remove(0); System.out.println(al.get(0)); } }运行结果示例随机数部分每次运行不同// 这是上面打印后的demo可以看到第0处下标元素先是修改成了doocs进行移除后第0处下标元素变成了912 finky 912 922 284 305 675 565 159 109 73 298 491 920 296 397 358 145 610 190 839 845 doocs 912二、ArrayList 源码分析说明以下源码均以 JDK 1.8 的java.util.ArrayList为准与本仓库 docs/JDK/collection/ArrayList.md 中讲解的版本一致。1. 初始化默认容量 10 是懒加载出来的// ArrayList 初始化时默认大小为10 private static final int DEFAULT_CAPACITY 10; // 直接初始化的话一个空数组 private static final Object[] EMPTY_ELEMENTDATA {}; // 初始化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); } } // 如果不传入大小的话就默认大小是10那么这里就有一个问题我们上面插入的元素超过了10继续插入元素就会进行拷贝扩容性能不是特别高。所以我们一般情况下初始化时给定一个比较靠谱的数组大小避免到时候导致元素不断拷贝 public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }三个容易被忽略的细节DEFAULT_CAPACITY 10只是名义容量无参构造时elementData实际指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA另一个空数组与EMPTY_ELEMENTDATA区分真正分配 10 个元素大小的数组发生在第一次调用add时由calculateCapacity判断后扩容到DEFAULT_CAPACITY。这种延迟分配懒加载机制避免了new 出来就占内存的浪费。EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA是两个不同常量前者服务于new ArrayList(0)后者服务于无参构造。它们的区别体现在首次扩容时的目标容量前者直接按minCapacity扩容后者会先提升到DEFAULT_CAPACITY10。容量不能为负数initialCapacity 0时直接抛出IllegalArgumentException。从仓库源码印证预分配容量的工程实践本仓库 docs/Dubbo/registry/Dubbo注册中心模块简析.md 中Dubbo 在已知列表规模时会写成new ArrayListURL(1)、new ArrayListURL(urls.size())、new ArrayListInvokerT(localUrlInvokerMap.values())正是为了在初始化时就给定一个比较靠谱的数组大小避免后续反复扩容拷贝——这与本文的结论完全一致是大型框架在真实场景中的最佳实践写照。2. add 方法先扩容再插入public boolean add(E e) { ensureCapacityInternal(size 1); // Increments modCount!! elementData[size] e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] element; size; } public void add(E e) { checkForComodification(); try { int i cursor; ArrayList.this.add(i, e); cursor i 1; lastRet -1; expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } private void rangeCheck(int index) { if (index 0 || index this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }流程可以归纳为三步容量检测ensureCapacityInternal(size 1)判断当前数组是否已满已满则触发扩容见第五节grow细节数组拷贝扩容后通过Arrays.copyOf把旧元素整体搬到新数组插入元素elementData[size] e写入并自增size。add(int index, E element)是按位插入版本先通过rangeCheckForAdd(index)校验下标合法性注意它允许index size即尾部追加再用System.arraycopy把index起的元素整体后移一位最后在index处写入新元素。注释里的// Increments modCount!!提示ensureCapacityInternal内部每次都会执行modCount这是后续快速失败机制fail-fast的计数来源。3. set 方法先查越界再替换返回旧值public E set(int index, E element) { rangeCheck(index); E oldValue elementData(index); elementData[index] element; return oldValue; } public void set(E e) { if (lastRet 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }逻辑非常简洁越界判断rangeCheck(index)校验下标越界抛出IndexOutOfBoundsException取旧值elementData(index)取出原位置元素替换并返回旧值elementData[index] element返回oldValue。注意set是纯替换不涉及扩容与数组移动因此复杂度为 O(1)是 ArrayList 效率最高的操作之一。4. get 方法随机访问的核心优势public E get(int index) { rangeCheck(index); return elementData(index); }同样先做rangeCheck(index)越界校验然后直接按下标从底层数组取值。数组是连续内存空间寻址只需一次基址偏移运算这就是 ArrayList随机读取快的根本原因也是它与链表结构最本质的性能差异。5. remove 方法元素前移 末尾置空public void remove() { if (lastRet 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor lastRet; lastRet -1; expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public E remove(int index) { // 进行index是否越界的判断 rangeCheck(index); checkForComodification(); E result parent.remove(parentOffset index); this.modCount parent.modCount; this.size--; return result; } public E remove(int index) { rangeCheck(index); modCount; E oldValue elementData(index); int numMoved size - index - 1; if (numMoved 0) System.arraycopy(elementData, index1, elementData, index, numMoved); elementData[--size] null; return oldValue; }上面三段remove分别来自ArrayList内部类Itr迭代器、SubList子列表视图与ArrayList本体。以本体remove(int index)为例越界判断rangeCheck(index)取被删元素elementData(index)暂存待返回的旧值元素前移计算numMoved size - index - 1若大于 0 则System.arraycopy把index1之后的元素整体向前拷贝一位末尾置空elementData[--size] null——这一步不仅是维护size更重要的是释放末尾引用帮助 GC 回收对象避免数组中仍持有已删除对象引用造成的内存泄漏隐患。复杂度删除末尾元素 O(1)删除中间/头部元素因涉及数组移动为 O(n)。6. 动态扩容与数组拷贝1.5 倍扩容的奥秘private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount; if (minCapacity - elementData.length 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity elementData.length; // 扩容的代码这里做了位运算相当于数组扩容了1.5倍 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); }完整调用链add→ensureCapacityInternal(minCapacity)→calculateCapacity首次添加时把容量抬升到DEFAULT_CAPACITY与minCapacity的较大者→ensureExplicitCapacitymodCount容量不足才继续→grow真正扩容→Arrays.copyOf内部调用System.arraycopy完成数组拷贝。1.5 倍扩容公式拆解newCapacity oldCapacity (oldCapacity 1)oldCapacity 1是右移一位等价于除以 2因此新容量 旧容量 旧容量的一半 1.5 倍。使用位运算而非oldCapacity / 2是 JDK 作者追求性能的典型细节。溢出保护代码注释写着overflow-conscious code。扩容结果若超过MAX_ARRAY_SIZEInteger.MAX_VALUE - 8预留 8 个字节给对象头会进入hugeCapacity分支兜底防止数组容量溢出造成内存分配异常。现在假定场景arraylist 中已经有 10 个元素类要放第 11 个元素。此时进行容量检测发现问题空间大小不够。解决方法此时进行数组扩容右位移 1相当于总容量多加 1.5 倍扩容老的大小老大小的一半进行元素拷贝。三、仿照 JDK 源码动手写一个自己的 ArrayList读源码的最高境界是能自己写出来。下面这份OwnArrayListE完整复刻了 JDK 的核心设计思想泛型数组存储、容量管理、下标越界校验、插入前移、删除前移、动态扩容全部逻辑不依赖任何 JDK 集合类可直接编译运行。public class OwnArrayListE { private E data[]; private int size; public OwnArrayList(int capacity) { data (E[]) new Object[capacity]; size 0; } // 初始化是默认设置大小为20 public OwnArrayList() { this(20); } // 获取数组容量 public int getCapacity() { return data.length; } // 获取数组元素个数 public int getSize() { return size; } // 判断数组是否为空 public boolean isEmpity() { return size 0; } // 获取index索引位置的元素 public E get(int index) { if (index 0 || index size) throw new IllegalArgumentException(add failed,the index should 0 or size); return data[index]; } // 修改index索引位置的元素为e public void set(int index, E e) { if (index 0 || index size) throw new IllegalArgumentException(add failed,the index should 0 or size); data[index] e; } // 在数组中间插入一个元素 public void add(int index, E element) { if (size data.length) { throw new IllegalArgumentException(AddLast failed,array has already full); } if (index 0 || index size) { throw new IllegalArgumentException(add failed,the index should 0 or size); } for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] element; size; } // 向数组元素末尾添加一个元素 public void addLast(E element) { add(size,element); } // 在数组头部插入一个元素 public void addFirst(E element) { add(0, element); } // 判断是否含有元素 public boolean contains(E e) { for (int i 0; i size; i) if (data[i] e) return true; return false; } // 查找元素e的位置 public int find(E e) { for (int i 0; i size; i) { if (data[i] e) { return i; } } return -1; } // 删除index位置的元素 public E remove(int index) { if (index 0 || index size) { throw new IllegalArgumentException(index should be 0 to size); } E remove_element data[index]; for (int i index 1; i size; i) { data[i - 1] data[i]; } size--; return remove_element; } // 删除末尾元素 // 注意这是逻辑删除但是size的大小已经做了相应的减少所以从实际意义上我们外界并不能访问到末尾元素的值 public E removelast() { return remove(size - 1); } // 删除开头元素 public E removeFirst() { return remove(0); } // 将数组空间的容量变成newCapacity大小 private void resize(int newCapacity) { newCapacity getCapacity()*2; E[] newData (E[]) new Object[newCapacity]; for (int i 0; i size; i) newData[i] data[i]; data newData; } }与 JDK 源码的对照要点get/set的越界校验对应 JDK 的rangeCheckadd(index, element)的从后往前循环移位对应 JDK 的System.arraycopy前移逻辑只是 JDK 用native方法实现、效率更高remove(index)的往前循环移位 size--对应 JDK 删除后元素前移resize方法对应 JDK 的grow示例采用 2 倍扩容JDK 是 1.5 倍——读者可以自行改成oldCapacity (oldCapacity 1)与 JDK 保持一致removelast注释中的逻辑删除点出了核心size减小后末尾元素对使用者不可见但旧引用仍残留在数组中所以 JDK 的remove会额外执行elementData[--size] null来释放引用这个细节值得在自己的实现中补上。四、面试时关于 ArrayList 要说的事如果有人问你 ArrayList 知多少可以从以下几个层次组织回答层层递进底层结构定基调ArrayList 的底层是基于数组进行的进行随机位置的插入和删除、以及扩容时性能很差但进行随机的读和取时速度却很快数组连续内存 下标寻址 O(1)。源码细节做支撑接着从源码的角度分析 add、remove、set、get、数组扩容拷贝的过程场景——重点讲清楚grow的 1.5 倍扩容公式oldCapacity (oldCapacity 1)、Arrays.copyOf底层System.arraycopy的拷贝时机、rangeCheck与rangeCheckForAdd的区别、删除后elementData[--size] null的 GC 友好设计以及modCount支撑的快速失败fail-fast机制。横向对比显深度最后也是特别重要的一点就是要积极掌握主动性延伸出 LinkedList 的特点、源码、两者间的对比等——例如ArrayList 随机读写 O(1)、中间插入删除 O(n)、扩容有拷贝开销LinkedList 双向链表、头尾操作 O(1)、随机访问 O(n)。本仓库 docs/JDK/collection 目录下收录了ArrayList、LinkedList、HashMap、ConcurrentHashMap等系列文档可对照阅读构建完整的集合框架知识网络。关于 Vector 的补充说明当需要动态数组时我们通常使用 ArrayList 而不是使用类似的 vector这里有一点说明一下就是尽管 Vector 的方法都是线程安全的但其在单线程下需要花费的时间更多每个方法都有synchronized同步开销而 ArrayList 尽管不是线程安全的但其花费的时间很少。因此在单线程场景下应优先选择 ArrayList多线程场景则需要自行加锁或改用CopyOnWriteArrayList等并发容器可参考仓库中 JUC并发包UML全量类图 了解并发容器全貌。终参考资料JDK 集合框架 ArrayList 源码JDK 1.8java.util.ArrayList《Core.Java.Volume.I.Fundamentals.11th.Edition》doocs/source-code-hunter 仓库 docs/JDK/collection/ArrayList.md 与 docs/JDK/collection 系列文档赞分享文档教程知识库【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址https://gitcode.com/doocs/source-code-hunter点击查看免费下载相关推荐剖析doocs/source-code-hunter中的MyBatis基础支持层剖析doocs/source code hunter中的MyBatis基础支持层 本文深入解析MyBatis基础支持层的核心组件包括反射工具箱、TypeHan文档教程知识库Sentinel底层计数器doocs/source-code-hunter中的LongAdder应用Sentinel底层计数器doocs/source code hunter中的LongAdder应用 1. 高并发计数痛点与解决方案 在分布式系统中流量控制文档教程知识库解析doocs/source-code-hunter中的MyBatis核心处理层解析doocs/source code hunter中的MyBatis核心处理层 引言为什么需要深入理解MyBatis核心处理层 在日常的Java开发中M文档教程知识库上一篇3分钟上手FilesWindows高效文件管理新体验下一篇Vuetify主题切换终极指南CSS变量与样式表深度对比创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
文档教程知识库【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址https://gitcode.com/doocs/source-code-hunter点击查看免费下载本文是 doocs/source-code-hunter 项目中 JDK 集合框架系列文章之一以 JDK 1.8 的ArrayList源码为对象完整拆解其初始化、add/set/get/remove与动态扩容的实现细节并提供一个可运行的自实现版本用于对照学习。读完本文你将能说清 ArrayList 的扩容公式、数组拷贝时机、modCount快速失败机制及其与Vector、LinkedList的取舍从而在面试中从会用进阶到讲透。ArrayList 是日常开发中出现频率最高的集合类之一也是面试的高频考点。它底层基于数组实现具备随机读快、随机写与扩容慢的鲜明特性。本仓库的定位正是从源码层面剖析互联网主流技术的底层实现原理见 README.md本文将延续这一思路把 ArrayList 的源码掰开揉碎讲清楚。一、写给小白ArrayList 的简单使用技巧先从一个完整的可运行 demo 入手熟悉 ArrayList 最常用的五个方法add(element)添加元素、get(index)获取下标元素、remove(index)移除下标对应元素、set(index, element)修改指定位置元素、size()获取元素个数。/** * 编写一个ArrayList的简单实用demo * ArrayList 的常见方法包括 * add(element):添加元素 * get(index):获取下标元素 * remove(index):移除下标对应元素 * set(index,element):将index处的元素修改为element */ public class arrayList { public static void main(String[] args) { // 创建 ArrayList 的对象 ArrayList al new ArrayList(); // 添加元素 al.add(finky); // 构造随机数并进行添加 Random rnd new Random(); for (int i 0; i 20; i) { al.add(rnd.nextInt(1000)); } // 取出ArrayList里的元素进行打印 for (int i 0; i al.size(); i) { System.out.print(al.get(i) ); } // 修改0号index成的元素为doocs System.out.println(); al.set(0, doocs); System.out.println(al.get(0)); // 移除“doocs”元素 al.remove(0); System.out.println(al.get(0)); } }运行结果示例随机数部分每次运行不同// 这是上面打印后的demo可以看到第0处下标元素先是修改成了doocs进行移除后第0处下标元素变成了912 finky 912 922 284 305 675 565 159 109 73 298 491 920 296 397 358 145 610 190 839 845 doocs 912二、ArrayList 源码分析说明以下源码均以 JDK 1.8 的java.util.ArrayList为准与本仓库 docs/JDK/collection/ArrayList.md 中讲解的版本一致。1. 初始化默认容量 10 是懒加载出来的// ArrayList 初始化时默认大小为10 private static final int DEFAULT_CAPACITY 10; // 直接初始化的话一个空数组 private static final Object[] EMPTY_ELEMENTDATA {}; // 初始化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); } } // 如果不传入大小的话就默认大小是10那么这里就有一个问题我们上面插入的元素超过了10继续插入元素就会进行拷贝扩容性能不是特别高。所以我们一般情况下初始化时给定一个比较靠谱的数组大小避免到时候导致元素不断拷贝 public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }三个容易被忽略的细节DEFAULT_CAPACITY 10只是名义容量无参构造时elementData实际指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA另一个空数组与EMPTY_ELEMENTDATA区分真正分配 10 个元素大小的数组发生在第一次调用add时由calculateCapacity判断后扩容到DEFAULT_CAPACITY。这种延迟分配懒加载机制避免了new 出来就占内存的浪费。EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA是两个不同常量前者服务于new ArrayList(0)后者服务于无参构造。它们的区别体现在首次扩容时的目标容量前者直接按minCapacity扩容后者会先提升到DEFAULT_CAPACITY10。容量不能为负数initialCapacity 0时直接抛出IllegalArgumentException。从仓库源码印证预分配容量的工程实践本仓库 docs/Dubbo/registry/Dubbo注册中心模块简析.md 中Dubbo 在已知列表规模时会写成new ArrayListURL(1)、new ArrayListURL(urls.size())、new ArrayListInvokerT(localUrlInvokerMap.values())正是为了在初始化时就给定一个比较靠谱的数组大小避免后续反复扩容拷贝——这与本文的结论完全一致是大型框架在真实场景中的最佳实践写照。2. add 方法先扩容再插入public boolean add(E e) { ensureCapacityInternal(size 1); // Increments modCount!! elementData[size] e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] element; size; } public void add(E e) { checkForComodification(); try { int i cursor; ArrayList.this.add(i, e); cursor i 1; lastRet -1; expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } private void rangeCheck(int index) { if (index 0 || index this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }流程可以归纳为三步容量检测ensureCapacityInternal(size 1)判断当前数组是否已满已满则触发扩容见第五节grow细节数组拷贝扩容后通过Arrays.copyOf把旧元素整体搬到新数组插入元素elementData[size] e写入并自增size。add(int index, E element)是按位插入版本先通过rangeCheckForAdd(index)校验下标合法性注意它允许index size即尾部追加再用System.arraycopy把index起的元素整体后移一位最后在index处写入新元素。注释里的// Increments modCount!!提示ensureCapacityInternal内部每次都会执行modCount这是后续快速失败机制fail-fast的计数来源。3. set 方法先查越界再替换返回旧值public E set(int index, E element) { rangeCheck(index); E oldValue elementData(index); elementData[index] element; return oldValue; } public void set(E e) { if (lastRet 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }逻辑非常简洁越界判断rangeCheck(index)校验下标越界抛出IndexOutOfBoundsException取旧值elementData(index)取出原位置元素替换并返回旧值elementData[index] element返回oldValue。注意set是纯替换不涉及扩容与数组移动因此复杂度为 O(1)是 ArrayList 效率最高的操作之一。4. get 方法随机访问的核心优势public E get(int index) { rangeCheck(index); return elementData(index); }同样先做rangeCheck(index)越界校验然后直接按下标从底层数组取值。数组是连续内存空间寻址只需一次基址偏移运算这就是 ArrayList随机读取快的根本原因也是它与链表结构最本质的性能差异。5. remove 方法元素前移 末尾置空public void remove() { if (lastRet 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor lastRet; lastRet -1; expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public E remove(int index) { // 进行index是否越界的判断 rangeCheck(index); checkForComodification(); E result parent.remove(parentOffset index); this.modCount parent.modCount; this.size--; return result; } public E remove(int index) { rangeCheck(index); modCount; E oldValue elementData(index); int numMoved size - index - 1; if (numMoved 0) System.arraycopy(elementData, index1, elementData, index, numMoved); elementData[--size] null; return oldValue; }上面三段remove分别来自ArrayList内部类Itr迭代器、SubList子列表视图与ArrayList本体。以本体remove(int index)为例越界判断rangeCheck(index)取被删元素elementData(index)暂存待返回的旧值元素前移计算numMoved size - index - 1若大于 0 则System.arraycopy把index1之后的元素整体向前拷贝一位末尾置空elementData[--size] null——这一步不仅是维护size更重要的是释放末尾引用帮助 GC 回收对象避免数组中仍持有已删除对象引用造成的内存泄漏隐患。复杂度删除末尾元素 O(1)删除中间/头部元素因涉及数组移动为 O(n)。6. 动态扩容与数组拷贝1.5 倍扩容的奥秘private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount; if (minCapacity - elementData.length 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity elementData.length; // 扩容的代码这里做了位运算相当于数组扩容了1.5倍 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); }完整调用链add→ensureCapacityInternal(minCapacity)→calculateCapacity首次添加时把容量抬升到DEFAULT_CAPACITY与minCapacity的较大者→ensureExplicitCapacitymodCount容量不足才继续→grow真正扩容→Arrays.copyOf内部调用System.arraycopy完成数组拷贝。1.5 倍扩容公式拆解newCapacity oldCapacity (oldCapacity 1)oldCapacity 1是右移一位等价于除以 2因此新容量 旧容量 旧容量的一半 1.5 倍。使用位运算而非oldCapacity / 2是 JDK 作者追求性能的典型细节。溢出保护代码注释写着overflow-conscious code。扩容结果若超过MAX_ARRAY_SIZEInteger.MAX_VALUE - 8预留 8 个字节给对象头会进入hugeCapacity分支兜底防止数组容量溢出造成内存分配异常。现在假定场景arraylist 中已经有 10 个元素类要放第 11 个元素。此时进行容量检测发现问题空间大小不够。解决方法此时进行数组扩容右位移 1相当于总容量多加 1.5 倍扩容老的大小老大小的一半进行元素拷贝。三、仿照 JDK 源码动手写一个自己的 ArrayList读源码的最高境界是能自己写出来。下面这份OwnArrayListE完整复刻了 JDK 的核心设计思想泛型数组存储、容量管理、下标越界校验、插入前移、删除前移、动态扩容全部逻辑不依赖任何 JDK 集合类可直接编译运行。public class OwnArrayListE { private E data[]; private int size; public OwnArrayList(int capacity) { data (E[]) new Object[capacity]; size 0; } // 初始化是默认设置大小为20 public OwnArrayList() { this(20); } // 获取数组容量 public int getCapacity() { return data.length; } // 获取数组元素个数 public int getSize() { return size; } // 判断数组是否为空 public boolean isEmpity() { return size 0; } // 获取index索引位置的元素 public E get(int index) { if (index 0 || index size) throw new IllegalArgumentException(add failed,the index should 0 or size); return data[index]; } // 修改index索引位置的元素为e public void set(int index, E e) { if (index 0 || index size) throw new IllegalArgumentException(add failed,the index should 0 or size); data[index] e; } // 在数组中间插入一个元素 public void add(int index, E element) { if (size data.length) { throw new IllegalArgumentException(AddLast failed,array has already full); } if (index 0 || index size) { throw new IllegalArgumentException(add failed,the index should 0 or size); } for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] element; size; } // 向数组元素末尾添加一个元素 public void addLast(E element) { add(size,element); } // 在数组头部插入一个元素 public void addFirst(E element) { add(0, element); } // 判断是否含有元素 public boolean contains(E e) { for (int i 0; i size; i) if (data[i] e) return true; return false; } // 查找元素e的位置 public int find(E e) { for (int i 0; i size; i) { if (data[i] e) { return i; } } return -1; } // 删除index位置的元素 public E remove(int index) { if (index 0 || index size) { throw new IllegalArgumentException(index should be 0 to size); } E remove_element data[index]; for (int i index 1; i size; i) { data[i - 1] data[i]; } size--; return remove_element; } // 删除末尾元素 // 注意这是逻辑删除但是size的大小已经做了相应的减少所以从实际意义上我们外界并不能访问到末尾元素的值 public E removelast() { return remove(size - 1); } // 删除开头元素 public E removeFirst() { return remove(0); } // 将数组空间的容量变成newCapacity大小 private void resize(int newCapacity) { newCapacity getCapacity()*2; E[] newData (E[]) new Object[newCapacity]; for (int i 0; i size; i) newData[i] data[i]; data newData; } }与 JDK 源码的对照要点get/set的越界校验对应 JDK 的rangeCheckadd(index, element)的从后往前循环移位对应 JDK 的System.arraycopy前移逻辑只是 JDK 用native方法实现、效率更高remove(index)的往前循环移位 size--对应 JDK 删除后元素前移resize方法对应 JDK 的grow示例采用 2 倍扩容JDK 是 1.5 倍——读者可以自行改成oldCapacity (oldCapacity 1)与 JDK 保持一致removelast注释中的逻辑删除点出了核心size减小后末尾元素对使用者不可见但旧引用仍残留在数组中所以 JDK 的remove会额外执行elementData[--size] null来释放引用这个细节值得在自己的实现中补上。四、面试时关于 ArrayList 要说的事如果有人问你 ArrayList 知多少可以从以下几个层次组织回答层层递进底层结构定基调ArrayList 的底层是基于数组进行的进行随机位置的插入和删除、以及扩容时性能很差但进行随机的读和取时速度却很快数组连续内存 下标寻址 O(1)。源码细节做支撑接着从源码的角度分析 add、remove、set、get、数组扩容拷贝的过程场景——重点讲清楚grow的 1.5 倍扩容公式oldCapacity (oldCapacity 1)、Arrays.copyOf底层System.arraycopy的拷贝时机、rangeCheck与rangeCheckForAdd的区别、删除后elementData[--size] null的 GC 友好设计以及modCount支撑的快速失败fail-fast机制。横向对比显深度最后也是特别重要的一点就是要积极掌握主动性延伸出 LinkedList 的特点、源码、两者间的对比等——例如ArrayList 随机读写 O(1)、中间插入删除 O(n)、扩容有拷贝开销LinkedList 双向链表、头尾操作 O(1)、随机访问 O(n)。本仓库 docs/JDK/collection 目录下收录了ArrayList、LinkedList、HashMap、ConcurrentHashMap等系列文档可对照阅读构建完整的集合框架知识网络。关于 Vector 的补充说明当需要动态数组时我们通常使用 ArrayList 而不是使用类似的 vector这里有一点说明一下就是尽管 Vector 的方法都是线程安全的但其在单线程下需要花费的时间更多每个方法都有synchronized同步开销而 ArrayList 尽管不是线程安全的但其花费的时间很少。因此在单线程场景下应优先选择 ArrayList多线程场景则需要自行加锁或改用CopyOnWriteArrayList等并发容器可参考仓库中 JUC并发包UML全量类图 了解并发容器全貌。终参考资料JDK 集合框架 ArrayList 源码JDK 1.8java.util.ArrayList《Core.Java.Volume.I.Fundamentals.11th.Edition》doocs/source-code-hunter 仓库 docs/JDK/collection/ArrayList.md 与 docs/JDK/collection 系列文档赞分享文档教程知识库【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址https://gitcode.com/doocs/source-code-hunter点击查看免费下载相关推荐剖析doocs/source-code-hunter中的MyBatis基础支持层剖析doocs/source code hunter中的MyBatis基础支持层 本文深入解析MyBatis基础支持层的核心组件包括反射工具箱、TypeHan文档教程知识库Sentinel底层计数器doocs/source-code-hunter中的LongAdder应用Sentinel底层计数器doocs/source code hunter中的LongAdder应用 1. 高并发计数痛点与解决方案 在分布式系统中流量控制文档教程知识库解析doocs/source-code-hunter中的MyBatis核心处理层解析doocs/source code hunter中的MyBatis核心处理层 引言为什么需要深入理解MyBatis核心处理层 在日常的Java开发中M文档教程知识库上一篇3分钟上手FilesWindows高效文件管理新体验下一篇Vuetify主题切换终极指南CSS变量与样式表深度对比创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
