Java ArrayList 深度解析

一、底层原理

1.1 ⭐初始化

无参构造

会将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 复制给 elementData 数组，这个很有用，便于确保无参构成函数创建的实例在添加第一个元素时，最小的容量是默认大小 10

有参集合构造，有参数值构造

如果传递集合的大小或者传递的参数值为 0，会将 EMPTY_ELEMENTDATA 赋值给 elementData 数组，优化创建 ArrayList 空实例时产生不必要的空数组，使得所有 ArrayList 空实例都指向同一个空数组。当然，如果传递的大小不为零，参数值不为零，那么还是会正常构造的

1.2 ⭐扩容机制

扩容触发流程

add 函数每次添加元素的时候都会调用 ensureCapacityInternal 函数保证容量足够，容量足够才会继续将元素添加到 elementData 数组中

扩容详细过程

如果调用 ensureCapacityInternal 函数之后发现容量不够了才会执行扩容逻辑，首先还是调用 ensureCapacityInternal 函数，然后 ensureCapacityInternal 函数再调用 ensureExplicitCapacity 和 calculateCapacity 函数：

• ensureExplicitCapacity - 用来判断容量够不够的，通过 minCapacity - elementData.length > 0 判断，不够会调用扩容函数
• calculateCapacity - 计算需要扩容的容量的，也就是 minCapacity，计算方式为 Math.max(size + 1, 10)

到了 grow 函数，新容量 newCapacity 是 Math.max(element.length * 1.5, minCapacity)，得到扩容的容量之后，会调用 Arrays.copyOf 函数，将原数组拷贝到新数组中，而且注意是浅拷贝不是深拷贝(而且一般 Java 中大多数类使用的都是浅拷贝)，新数组的大小就是扩容的容量

扩容总结

ArrayList 在 add 时会先计算最小所需容量，如果当前数组不够就触发扩容。

• 对于无参构造，第一次 add 会直接分配默认容量 10
• 如果是 new ArrayList(0)，第一次只会扩到 1，后续按 1.5 倍逐步扩容
• 扩容本质是创建新数组并进行一次浅拷贝，深拷贝会破坏引用语义，而且性能和语义都不合理

modCount 的作用

ensureExplicitCapacity 里有一个 modCount++，它用来记录集合的结构性修改次数。Iterator 通过对比 expectedModCount 实现 Fail-Fast 机制，用于在遍历过程中检测非法的并发修改。

1.3 扩容机制扩展

LinkedList

LinkedList 和上面两种容器的实现有点不同，上面两个底层是 elementData 数组，这个是双向链表，所以没有扩容一说

Vector

Vector 的初始容量默认为 10，如果需要扩容，会将该数组当前容量扩大为原来的 2 倍

---

二、扩展 - Fail-Fast / Safe 机制

2.1 ⭐Fail-Fast / 快速失败

底层实现原理

foreach 的底层实现是利用迭代器 Iterator 实现的，增删操作都会使 modCount++（modCount 记录的是修改此列表的次数）。

AbstractList 抽象类的内部类 Itr 实现了 Iterator 接口，ArrayList 实现 List 接口并继承 AbstractList 类。由于 ArrayList 追求性能，所以重写了保护的 Itr，和父类 Itr 的区别是直接使用 elementData[] 数组访问元素（比 get() 快）。所以实际上这部分内容是 Itr 做的

Fail-Fast 机制

Itr 的底层主要是通过比较 modCount 和 expectedModCount 变量，在 Itr 中会将 modCount 赋值给 expectedModCount，每个方法都在调用之前都会执行 checkForComodification() 方法，比如 next，remove 方法等等，如果 modCount != expectedModCount 则抛出 ConcurrentModificationException 异常，也就是并发修改异常（这也叫做 Fail-Fast 机制）

核心要点总结

• foreach 本质是 Iterator。ArrayList 继承 AbstractList，而 AbstractList 内部通过 Itr 实现 Fail-Fast
• ArrayList 为了性能，重写了 Itr，遍历时直接访问 elementData 数组而不是通过 get()
• modCount 在结构性修改时递增，Iterator 保存 expectedModCount，在遍历时对比，从而实现 Fail-Fast
• Iterator 只允许它自己修改集合，否则就抛 ConcurrentModificationException，这就是 Fail-Fast 的语义

2.2 Fail-Safe / 安全失败

机制说明

该机制是基于容器的一个克隆，对容器内容的修改不影响遍历。java.util.concurrent 包下的容器都是安全失败的，可以在多线程下并发使用，并发修改。

常见实现

常见的的使用 Fail-Safe 方式遍历的容器有 ConcurrentHashMap 和 CopyOnWriteArrayList 等。

注意事项

问题就是只能保证数据的最终一致性，不能保证数据的实时一致性

2.3 手撕代码 - 遍历删除

题目：写一段代码，遍历Map删掉value为输入的值

Iterator 方法对比

方法          ListIterator    Iterator    功能
remove()      ✅              ✅          删除上次 next() 返回的元素
set(E e)      ✅              ❌          修改上次 next() 返回的元素
add(E e)      ✅              ❌          在当前位置插入元素（插入后游标指向新元素后面）

List 遍历删除示例

@Test
void test1() {
    List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    list.removeIf(n -> n.equals(4));
    ListIterator<Integer> it = list.listIterator();
    while (it.hasNext()) {
        Integer i = it.next();
        if (i.equals(2)) {
            it.set(5);
            it.remove();
            it.add(4);
        }
    }
    list.forEach(System.out::println);
}

Map 遍历删除示例

@Test
void test2() {
    Map<String, Integer> map = new HashMap<>(Map.of("a", 1, "b", 2, "c", 3, "d", 4));
    Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
    while(it.hasNext()) {
        Map.Entry<String, Integer> i = it.next();
        if (i.getKey().equals("a")) {
            it.remove();
        }
    }
    map.entrySet().removeIf(i -> i.getKey().equals("b"));
    map.entrySet().removeIf(i -> i.getValue().equals(3));
    map.forEach((k, v) -> System.out.println(k + ":" + v));
}

---

三、扩展 - CopyOnWriteArrayList

3.1 ⭐底层实现

核心结构

从定义上来看其实 CopyOnWriteArrayList 比 ArrayList 多了一个 ReentrantLock，数组用 volatile 修饰保证可见性。

写操作机制

在添加新元素的时候，会将原来的数组内容拷贝到新数组上，因为尽管数组的确是使用了 volatile 修饰，但是这只能保证数组引用的可见性，不能保证数组元素的可见性，所以这里才会拷贝到新数组上。

线程安全实现

CopyOnWriteArrayList 的线程安全实现主要通过 ReentrantLock 和 volatile 关键字来实现：

• ReentrantLock - 可重入锁，可以保证同一时间只有一个线程可以修改数组
• volatile - 可以保证数组引用的可见性

在添加元素时，会先获取锁，然后拷贝数组，添加元素，最后释放锁。在读取元素时，会直接返回数组，不需要加锁。

通过将 array 声明为 volatile，当一个线程更新了这个数组的引用（比如添加元素时复制数组），其他线程能够看到这个更新的引用，而不会读到老的引用

3.2 与其他容器的对比

相比之下，CopyOnWriteArraylist 没有 ArrayList 的扩容方法，因为每次 add 操作其实都是在变相扩容，类似的 remove 也是一样的，都是使用 ReentrantLock + volatile + 数组拷贝 实现线程安全的。

比 Vector 先进的地方在 get 方法不用加锁，虽然不是强一致性，但是还是保证了最终一致性