Java ArrayList代码解读及原理

一、前言算是Java开发中比较常见的一个集合类了但是对于新手来说对他的了解大多是只是停留在他是一个存数据的数组使用的最多就是add、get。并不知道它为何能一直存数据换句话说就是它使用了哪些方法让一个固定长度的数组变成一个可以一直接收数据的仓库。本文将从Arraylist的源代码解读和方法分析以及ArrayList如何实现两个方面讲解。二、ArrayList 底层是怎么实现的核心原理ArrayList本质就是一个自动扩容的变长数组ArrayList底层基于普通数组实现Object[] elementData。普通数组的缺点长度固定、无法自动扩容ArrayList弥补普通数组缺点的思路数组满了 → 创建新的更大数组 → 复制旧数据 → 替换数组模拟出“动态变长”的效果。一.实现思路和扩容规则1.创建数组两种构造方法当创建的时候没有给数组长度和数据时空参构造方法数组只声明不创建内存空间。防止用户不给长度一直创建Arraylist集合节省内存空间当创建的时候给数组长度和数据时有参构造方法直接把定义ArrayList的长度作为数组的长度简化后续调用扩容数组的方法的次数2.数组容量不足时自动扩容为原来的1.5 倍。公式新容量 旧容量 旧容量 / 2空参构造初始化不创建长度为10的数组而是赋值空数组第一次 add 元素时才懒加载扩容为 10三、ArrayList 核心源码分析2. 构造方法源码解析① 空参构造最常用public ArrayList() { // 初始赋值空数组不占用内存懒加载 this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }空创建不初始化10容量第一次添加元素才扩容节省内存。② 指定初始容量构造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); } }3. add() 添加元素 扩容核心源码public boolean add(E e) { // 记录修改次数快速失败机制 modCount; add(e, elementData, size); return true; } private void add(E e, Object[] elementData, int s) { // 判断元素个数 数组容量 → 数组满了需要扩容 if (s elementData.length) elementData grow(); // 元素存入数组末尾 elementData[s] e; // 实际元素个数1 size s 1; }4. 重点grow() 扩容方法源码private Object[] grow() { return grow(size 1); } private Object[] grow(int minCapacity) { int oldCapacity elementData.length; // 无参构造后空数组第一次添加元素直接扩容为默认容量10 if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 核心扩容1.5倍 右移一位 /2 int newCapacity oldCapacity (oldCapacity 1); // 防止扩容后容量不够 if (newCapacity - minCapacity 0) newCapacity minCapacity; // 最大容量判断 if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); } else { // 首次插入容量直接赋值10 newCapacity DEFAULT_CAPACITY; } // 数组拷贝创建新数组、复制旧数据 return elementData Arrays.copyOf(elementData, newCapacity); }扩容全过程总结判断数组是否已满计算新容量原容量 1.5 倍通过Arrays.copyOf创建新数组复制旧数组所有元素到新数组替换底层数组引用完成扩容解析为什么扩容要选1.5倍首先看这行代码 int newCapacity oldCapacity (oldCapacity 1);1. 1直接除以 2效率极高二进制计算好实现2.扩容次数不会太多不用频繁复制数组2倍内存浪费大量空闲空间1.2扩容太慢1.5折中3.之前回收的内存仍然可以重复使用举最直观例子ArrayList 扩容过程初始容量101.5 倍扩容序列10 → 15 → 22 → 33 → 49…把前面所有废弃的旧数组加起来1015 25101522 4710152233 80新数组大小 ≈ 前面所有旧数组总和5. get() 查询方法源码public E get(int index) { // 下标越界检查 rangeCheck(index); // 直接通过数组下标取值 → O(1) 极快 return elementData(index); }这就是 ArrayList查询速度快的根本原因直接数组下标访问。6. remove() 删除方法源码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); // 末尾置空帮助GC elementData[--size] null; return oldValue; }删除中间元素需要做数据前移方法所以 ArrayList删除效率低。四、总结底层结构Object 动态数组扩容机制默认 1.5 倍扩容JDK8 懒加载初始化优缺点查询快、增删慢、有序可重复线程安全不安全多线程扩容会覆盖、报错初始容量空参构造首次 add 才变成10五、结尾ArrayList 的所有特性全部源于它底层是数组、需要动态扩容、增删要移动元素这一核心原理。看懂源码就彻底掌握了 ArrayList。