ArrayList 底层原理深度解析

在 Java 集合框架中，ArrayList 是 List 接口的动态数组实现类，位于 java.util 包下，兼具数组随机访问高效的特性与动态扩容的灵活性，是日常开发中最常用的集合之一。

一、核心底层结构

ArrayList 的底层依托定长数组存储元素，在 Java 源码中，这个数组的声明为：
transient Object[] elementData;
• transient 关键字表示该数组不会被默认序列化，ArrayList 会通过重写 writeObject() 和 readObject() 方法实现自定义序列化，只序列化实际存储的元素，节省空间。

• 数组的默认初始容量为 10（JDK 8 及以上版本），也可通过构造方法 new ArrayList(int initialCapacity) 指定初始容量。

二、动态扩容机制

ArrayList 之所以被称为“动态数组”，核心在于其自动扩容逻辑，当数组容量不足以容纳新元素时，会触发扩容流程。

1. 扩容触发条件

当调用 add() 方法添加元素时，会先检查当前元素数量（size）是否等于数组长度（elementData.length），若相等则触发扩容。

2. 扩容计算规则

扩容时，新容量的计算分两步：

1. 计算初步新容量：newCapacity = oldCapacity + (oldCapacity >> 1)，即原容量的 1.5 倍（位运算 >>1 等价于除以 2）。

2. 校验初步新容量：若初步新容量小于最小需要容量（如添加大量元素时），则直接使用最小需要容量作为新容量；同时，新容量最大不能超过 Integer.MAX_VALUE - 8（避免内存溢出）。

3. 扩容核心操作

扩容的本质是创建新数组 + 复制原数组元素，通过 Arrays.copyOf(elementData, newCapacity) 方法实现，该方法会创建一个长度为新容量的新数组，并将原数组的元素全部复制到新数组中，最后将 elementData 引用指向新数组。

注意：扩容操作涉及数组复制，会产生额外的性能开销，因此若已知元素数量，建议初始化时指定容量，减少扩容次数。

三、核心方法的时间复杂度

• 随机访问（get(int index)）：直接通过数组下标访问元素，时间复杂度为 O(1)，这是 ArrayList 的核心优势。

• 尾部添加（add(E e)）：若无需扩容，直接在数组尾部赋值，时间复杂度 O(1)；若触发扩容，需复制数组，时间复杂度 O(n)。

• 指定位置增删（add(int index, E e)/remove(int index)）：需要移动目标位置后的所有元素，时间复杂度为 O(n)，效率较低。

四、线程安全性

ArrayList 是非线程安全的集合类。

• 多线程环境下，若同时执行读写操作（如一个线程添加元素，另一个线程遍历），可能会抛出 ConcurrentModificationException（并发修改异常）。

• 若需线程安全，可使用 Collections.synchronizedList(new ArrayList<>()) 包装，或直接使用 CopyOnWriteArrayList 类。