Go back

ArrayList与CopyOnWriteArrayList——1.5倍扩容与fail-fast机制

ArrayList：1.5 倍扩容 + fail-fast + CopyOnWriteArrayList

一句话结论（30s）

ArrayList 的本质是「基于数组的动态列表」，因为数组支持 O(1) 随机访问，所以扩容按 1.5 倍复制，并用 modCount 计数实现 fail-fast 迭代器尽早暴露遍历过程中的修改；CopyOnWriteArrayList 则用「写时复制数组 + volatile 引用 + synchronized 内置锁」让读完全无锁。权衡：1.5 倍是扩容频率与内存利用率的折中，COW 以写 O(n) 和 GC 压力换来读不阻塞，只适合读多写少场景。

核心原理（2min）

主流程：add 时容量不足就按 oldCapacity + (oldCapacity>>1)（1.5 倍）扩容，底层 System.arraycopy（Native 批量拷贝）比逐元素循环快数十倍。迭代器构造时记 expectedModCount = modCount，每次 next 检查是否一致，不一致抛 ConcurrentModificationException——这是「尽力而为」的并发修改检测。CopyOnWriteArrayList 写时加 synchronized 内置锁、Arrays.copyOf 复制整个数组后 volatile 写回，读直接读 volatile 数组引用无锁，写不阻塞读（读的是旧数组快照）。

想一想：ArrayList 为什么扩 1.5 倍而不是 2 倍？fail-fast 为什么用 modCount 计数而不是加锁？——前一个问题牵出「扩容频率 vs 内存利用率」的折中，后一个问题牵出「检测错误 vs 保证安全」的定位差异，往下逐层拆。

底层深入（5-10min）

ArrayList 的动态扩容

// java.util.ArrayList.add(E)——真实源码
public boolean add(E e) {
    modCount++;                   // 结构性修改计数 +1（供 fail-fast 检测）
    add(e, elementData, size);
    return true;
}

// 从 add(E) 拆出的私有辅助方法，控制字节码体积以利于 C1 内联
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)  // 当前 size 已顶满数组容量
        elementData = grow();     // 触发扩容
    elementData[s] = e;           // 放入新元素
    size = s + 1;
}

// 扩容核心——真实源码
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

private Object[] grow() {
    return grow(size + 1);
}

add(E e) 第一步就是 modCount++，把这次结构性修改记入版本号，迭代器靠它检测「遍历过程中被修改」。真正写元素的是私有 add(e, elementData, s)：当 s == elementData.length 说明数组已满，调用 grow() 扩容后再写入。

grow(int minCapacity) 里 ArraysSupport.newLength(oldCapacity, 最小增量, oldCapacity >> 1) 的第三个参数 oldCapacity >> 1 是「首选增长量」——等价于 oldCapacity + (oldCapacity >> 1)，即新容量约为旧容量的 1.5 倍；随后 Arrays.copyOf 分配新数组并搬移旧元素。

Arrays.copyOf() 底层是 System.arraycopy()——JVM 的 Native 批量内存拷贝（类似 memmove），比逐元素 for 循环快数十倍。

为什么是 1.5 倍？

2 倍扩容 → 每次扩容后容量完全覆盖之前所有分配的总和，内存碎片严重且浪费。1.5 倍是经验值——扩容频率足够低（每次操作均摊 O(1)），内存利用率足够高。Vector 用 2 倍扩容是历史遗留。

想一想：为什么不干脆用 2 倍、让扩容发生得更少？——因为容量是翻倍增长的，2 倍时新容量 = 之前所有容量之和，浪费空间随规模线性放大；1.5 倍在「扩容次数」与「内存浪费」之间取了平衡，均摊下来每次 add 仍是 O(1) 的一次拷贝。

fail-fast 迭代器

for (String s : list) {
    if (s.equals("target")) list.remove(s);  // ❌ ConcurrentModificationException
}

增强 for 循环内部用的是 Iterator。ArrayList 有一个 modCount 字段——每次结构性修改（add/remove）时 modCount++。迭代器构造时记录当前的 expectedModCount = modCount，每次 next() 时检查 expectedModCount == modCount，不相等则抛异常。

modCount 定义在父类 AbstractList 中（真实源码）：

// java.util.AbstractList——结构性修改计数，ArrayList 直接继承使用
protected transient int modCount = 0;

ArrayList 的 Itr 迭代器构造时快照这个值，并在每次遍历前校验（真实源码）：

// java.util.ArrayList.Itr——fail-fast 的实现
private class Itr implements Iterator<E> {
    int cursor;       // 下一个待返回元素的下标
    int lastRet = -1; // 上次返回元素的下标；-1 表示无
    int expectedModCount = modCount;   // 构造时快照版本号

    public E next() {
        checkForComodification();      // 每次 next 先校验版本号
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)        // 版本号变了说明被结构性修改
            throw new ConcurrentModificationException();
    }
}

expectedModCount 在迭代器构造那一刻把 modCount 记下来；此后每次 next() 都先跑 checkForComodification()，一旦 modCount != expectedModCount 就立即抛 ConcurrentModificationException。这就是 fail-fast 的全部机制——它不锁、不阻塞，只做一次整数比较。

想一想：为什么用 modCount 做「版本号比对」而不直接加锁？——因为 fail-fast 的定位是「尽早暴露错误」而非「保证并发安全」：加锁能保安全但代价高、且 ArrayList 本就非线程安全；modCount 只在构造时快照、每次 next 做一次整数比较，近乎零开销，恰好覆盖「遍历中被改」这类常见错误。

设计意图：在非线程安全的集合上检测并发修改（单线程场景也可检测到”遍历过程中修改”的错误）。但它是”尽力而为”的机制——不能保证一定检测到（多线程并发修改不保证 modCount 的可见性）。

RandomAccess：标记接口的妙用

public class ArrayList<E> implements RandomAccess { }

// Collections 内部的分支优化
if (list instanceof RandomAccess)
    for (int i = 0; i < n; i++) list.get(i);      // O(1) 随机访问
else
    for (Iterator it = list.iterator(); ...);       // 迭代器遍历

空接口，不定义任何方法——只是一个”标记”。LinkedList 不实现 RandomAccess——告诉算法”不要用下标循环遍历我”（get(i) 是 O(n) 的指针遍历）。

想一想：一个空接口凭什么能改变算法行为？——它不定义任何方法，只给 Collections 的排序/二分等算法一个「类型标记」：实现它 = 承诺 O(1) 随机访问，算法才敢用下标循环；LinkedList 不实现，算法就退回迭代器遍历，避免 O(n²) 灾难。

CopyOnWriteArrayList：读无锁、写复制

// java.util.concurrent.CopyOnWriteArrayList——底层字段（真实源码）
final transient Object lock = new Object();   // 保护所有写操作的锁
private transient volatile Object[] array;    // volatile 数组引用

final Object[] getArray() {                   // 读引用
    return array;
}

final void setArray(Object[] a) {             // 写引用
    array = a;
}

写操作 add() 完整走「读旧数组 → copyOf 扩容 → 写新元素 → setArray 原子替换」四步（真实源码）：

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();           // 1. 读旧数组（volatile 读）
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);    // 2. copyOf 扩容：复制整个数组并 +1 容量
        es[len] = e;                        // 3. 把新元素写到末尾
        setArray(es);                       // 4. setArray 原子替换：volatile 写回新数组
        return true;
    }
}

读操作完全无锁（真实源码）：

public E get(int index) {
    return elementAt(getArray(), index);    // 直接读 volatile 数组引用，不获取锁
}

每次写都 Arrays.copyOf 整个数组 → 写不阻塞读（读的是旧数组快照）。因为 array 是 volatile 引用，setArray 一写，所有读者立刻看到新数组；反过来读者拿到的是引用那一刻的旧数组，遍历期间绝不会被写者干扰。代价：写操作 O(n)，频繁写时大量 GC 压力。

想一想：读为什么能完全无锁，而写要 O(n) 复制整个数组？——因为 volatile 数组引用让读者总能读到某个完整一致的快照，写者用「copyOf 出新数组 + 原子替换引用」隔离修改，读者手里的旧数组永不被改写，所以读无需加锁；代价是每次写都复制全表，只能读多写少。

适用场景：读多写少（配置列表、白名单、监听器列表）。写操作很少（启动时加载一次，很少修改），读操作极多且不能阻塞。

章末提问

  1. ArrayList 为什么选 1.5 倍扩容而不是 2 倍？ —— 结论：为了在扩容频率与内存利用率之间折中。因为 2 倍时新容量会覆盖此前所有分配之和、空间浪费随规模线性放大；1.5 倍让均摊成本仍是 O(1)，同时减少内存碎片和浪费。

  2. fail-fast 为什么用 modCount 计数而不是加锁？ —— 结论：因为它只负责「尽早暴露」而非「保证安全」。加锁成本高且违背 ArrayList 非线程安全的前提；modCount 快照 + 每次 next 一次整数比较，零阻塞、近零开销，足以捕获遍历期间的修改。

  3. fail-fast 一定能检测到并发修改吗？ —— 结论：不能。因为多线程下 modCount 的写对迭代器线程不保证可见性，且检测只在 next() 时点发生，修改若「碰巧」落在两次检查之间且版本号相等就会漏掉，所以它只是「尽力而为」。

  4. CopyOnWriteArrayList 为什么读可以完全无锁？ —— 结论：因为读的是不可变快照。写操作 copyOf 出新数组、再原子替换 volatile 引用，读者持有的旧数组永不被修改，所以读无需加锁、写也不阻塞读。

  5. CopyOnWriteArrayList 的代价是什么、适合什么场景？ —— 结论：代价是写 O(n)（每次复制全表）和 GC 压力，只适合读多写少。比如配置列表、白名单、监听器列表这类「启动加载一次、之后极少改、读极频繁」的场景。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
ConcurrentHashMap——从JDK7分段锁到JDK8桶级锁
Next Post
注解原理——@Override背后有一个动态代理