面试突击：ArrayList源码详解

本文已收录于：https://github.com/danmuking/all-in-one（持续更新）

前言

哈喽，大家好，我是 DanMu。ArrayList 是我们日常开发中不可避免要使用到的一个类，并且在面试过程中也是一个非常高频的知识点，这篇文章将深入分析 ArrayList 的底层原理，助你彻底掌握 ArrayList相关的知识点。

数据结构

ArrayList 的底层是数组，与 Java 中的数组不同的是它的容量能动态增长，当空间不足时，ArrayList 将在底层自动增加数组空间，因此相对数组来说使用起来更加方便。

类图

从继承关系上看 ArrayList 继承于 AbstractList，实现了 List, RandomAccess , Cloneable , java.io.Serializable 等接口。

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
RandomAccess ：这个接口表示这个类具有随机访问的能力。
Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输。

什么是随机访问？
简单来说，就是可以在 O(1) 的时间复杂度内根据下标找到对应元素。典型的具有随机访问的数据结构就是数组，而链表查询下标对应元素需要从头结点开始遍历所有节点，需要 O(N) 的时间复杂度，因此链表就不具有随机访问能力。

核心源码解读

成员变量

每个 ArrayList 都维护了一些重要的成员变量，用于 ArrayList 的管理，其中比较重要的变量有：

// 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;// 空数组，所有初始化长度为0的Arraylist共用这个数组，减少内存
private static final Object[] EMPTY_ELEMENTDATA = {};// 用于默认构造函数，创建 ArrayList 时不分配空间，将空间分配推迟到第一次添加元素时
// 需要区分和 EMPTY_ELEMENTDATA 的区别
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 实际保存 ArrayList 数据的数组
// transient关键字表示这部分内容不会被序列化
transient Object[] elementData; // non-private to simplify nested class access// ArrayList 所包含的元素个数
private int size;

初始化

ArrayList 中主要有三种构造方法：

// 带初始容量参数的构造函数
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//如果传入的参数大于0，创建 initialCapacity 大小的数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//如果传入的参数等于0，创建空数组this.elementData = EMPTY_ELEMENTDATA;} else {//其他情况，抛出异常throw new IllegalArgumentException("Illegal Capacity: " +initialCapacity);}
}// 默认无参构造函数
// 先用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 初始化, 当插入第一个数据时才扩容为10.
// 这种方式也被称为懒加载
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}// 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
public ArrayList(Collection<? extends E> c) {//将指定集合转换为数组elementData = c.toArray();//如果elementData数组的长度不为0if ((size = elementData.length) != 0) {// 如果elementData不是Object类型数据（c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断）if (elementData.getClass() != Object[].class)//将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// 其他情况，用空数组代替this.elementData = EMPTY_ELEMENTDATA;}
}

扩容机制

add 方法

/**
* 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {// 加元素之前，先调用 ensureCapacityInternal 方法，保证数组有足够的空间ensureCapacityInternal(size + 1);  // Increments modCount!!// 这里看到ArrayList添加元素的实质就相当于为数组赋值elementData[size++] = e;return true;
}

ensureCapacityInternal 方法

// 确保内部容量达到指定的最小容量。
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(// 计算完成添加元素所需的最小容量calculateCapacity(elementData, minCapacity));
}// 计算完成添加元素所需的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {// 如果当前数组元素为空数组（初始情况），返回默认容量和最小容量中的较大值作为所需容量if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}// 否则直接返回最小容量return minCapacity;
}// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {// 这是ArrayList中维护的一个用来统计结构变化次数的变量，可以忽略modCount++;// 判断当前数组容量是否足以存储 minCapacity 个元素if (minCapacity - elementData.length > 0)// 存不下，调用 grow 方法进行扩容grow(minCapacity);
}

grow 方法

grow 方法是实现扩容的核心方法：

/*** 能分配的最大数组大小*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** ArrayList扩容的核心方法。*/
private void grow(int minCapacity) {// oldCapacity为旧容量，newCapacity为新容量int oldCapacity = elementData.length;// 将新容量更新为旧容量的1.5倍// 使用位运算，速度更快int newCapacity = oldCapacity + (oldCapacity >> 1);// 然后检查扩容后容量是否大于需要的容量，若还是小于需要的容量，直接扩容到需要的容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量超过最大值,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，// 处理边界条件if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);
}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();// 对minCapacity和MAX_ARRAY_SIZE进行比较// 若minCapacity大，将Integer.MAX_VALUE作为新数组的大小// 若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

流程图

集合.drawio.png

删除元素

ArryList提供了两个删除List元素的方法，分别通过下标和元素进行元素的删除。

通过下标删除元素

public E remove(int index) {// 检查下标是否越界rangeCheck(index);modCount++;// 取出元素的值E oldValue = elementData(index);// 计算需要移动元素的个数int numMoved = size - index - 1;// 如果删除的元素不是最后一位，将数组后面的元素移动到前面if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);// 将原来的最后一个index设为nullelementData[--size] = null; // clear to let GC do its work// 返回被删除元素return oldValue;
}

未命名绘图-第 2 页.drawio.png

通过元素删除元素

public boolean remove(Object o) {// 如果 o 为null,就删除 ArrayList中第一个值为 null 的元素if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {//  遍历 ArrayList,如果存在则删除第一个等于 o 的元素for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;
}
// 这边的逻辑和通过下标删除元素的逻辑一样
private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work
}

点关注，不迷路

好了，以上就是这篇文章的全部内容了，如果你能看到这里，非常感谢你的支持！
如果你觉得这篇文章写的还不错，求点赞👍 求关注❤️ 求分享👥 对暖男我来说真的 非常有用！！！
白嫖不好，创作不易，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！
如果本篇博客有任何错误，请批评指教，不胜感激！