Iterator 与 fail-fast：集合遍历的安全边界

2024-03-15 02:17:33 ERROR OrderSyncService - sync failed
java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
    at java.util.ArrayList$Itr.next(ArrayList.java:965)
    at com.biz.service.OrderSyncService.processOrders(OrderSyncService.java:87)
    ...

public interface Iterator<E> {

    // 是否还有下一个元素
    boolean hasNext();

    // 返回下一个元素，并将游标后移
    E next();

    // 移除上一次 next() 返回的元素（default 方法抛 UnsupportedOperationException）
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    // Java 8 引入：对剩余元素执行 action
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

// 以下两段代码结构完全一致，尽管底层数据结构截然不同

List<String> list = new ArrayList<>(List.of("A", "B", "C"));
Set<String>  set  = new HashSet<>(List.of("A", "B", "C"));

// 遍历 ArrayList —— 底层是数组 + 索引
Iterator<String> it1 = list.iterator();
while (it1.hasNext()) {
    System.out.println(it1.next());
}

// 遍历 HashSet —— 底层是哈希表
Iterator<String> it2 = set.iterator();
while (it2.hasNext()) {
    System.out.println(it2.next());
}

public abstract class AbstractList<E> extends AbstractCollection<E>
    implements List<E> {

    // 结构性修改的计数：add, remove, clear 等操作每次 +1
    // 注意：它是 protected 的，子类可以直接访问
    protected transient int modCount = 0;
}

// add 方法 —— 每次成功添加都让 modCount +1
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 可能触发扩容，扩容也会 modCount++
    elementData[size++] = e;
    return true;
}

// remove 方法 —— 同样 modCount +1
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);
    elementData[--size] = null;
    return oldValue;
}

// ensureCapacityInternal → ensureExplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;       // ← 扩容也算结构性修改！
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private class Itr implements Iterator<E> {
    int cursor = 0;               // 下一个要返回的元素索引
    int lastRet = -1;             // 上一次 next()/previous() 返回的元素索引
    int expectedModCount = modCount; // 创建 Iterator 时拍快照

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

List<String> list = new ArrayList<>();
list.add("A");  // modCount = 1
list.add("B");  // modCount = 2
list.add("C");  // modCount = 3

Iterator<String> it = list.iterator();
// ↑ Iterator 创建，expectedModCount = 3（快照）

while (it.hasNext()) {
    String s = it.next();   // 第一次调用 next()，checkForComodification() 通过
    if ("B".equals(s)) {
        list.remove(s);     // ← 用 list 的 remove！modCount 变成 4
    }
    // 第二次调用 it.next()：
    //   checkForComodification() 发现 modCount(4) != expectedModCount(3)
    //   → 抛出 ConcurrentModificationException!
}

public class CopyOnWriteArrayList<E> {

    // 底层数组是 volatile 的，保证可见性
    private volatile transient Object[] array;

    // add 操作：加锁 → 复制整个数组 → 追加元素 → 替换引用
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1); // ← 复制！
            newElements[len] = e;
            setArray(newElements);  // 原子替换引用
            return true;
        } finally {
            lock.unlock();
        }
    }

    // Iterator 拿到的永远是创建时的数组快照——不需要 modCount
    public Iterator<E> iterator() {
        return new COWIterator<>(getArray(), 0);
    }
}

// ─── CopyOnWriteArrayList：看到的是快照 ───
CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();
cowList.addAll(List.of("A", "B", "C"));

Iterator<String> cowIt = cowList.iterator();
cowList.add("D");           // 写操作触发整个数组复制

while (cowIt.hasNext()) {
    System.out.print(cowIt.next() + " ");
}
// 输出: A B C  ← 看不到后来加的 "D"（快照语义）

// ─── ConcurrentHashMap：弱一致性 ───
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("A", 1); map.put("B", 2); map.put("C", 3);

Iterator<String> chmIt = map.keySet().iterator();
map.put("D", 4);           // 修改底层 table

while (chmIt.hasNext()) {
    System.out.print(chmIt.next() + " ");
}
// 输出: A B C D 或 A B C  ← 可能看到也可能看不到（弱一致）

// ❌ 错误：用 list.remove()，modCount 与 expectedModCount 不同步
for (String s : list) {
    if ("B".equals(s)) {
        list.remove(s);  // CME!
    }
}

// ✅ 正确：用 iterator.remove()，内部会同步 expectedModCount
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if ("B".equals(s)) {
        it.remove();  // 安全！remove() 内部执行 expectedModCount = modCount
    }
}

// ❌ foreach 中无法调用 iterator.remove()，因为 Iterator 引用不可见
for (String s : list) {
    if (s.startsWith("tmp_")) {
        // 这里没有 it.remove() 可以调！
    }
}

// ✅ Java 8+ 最优雅的解法：removeIf（底层使用 Iterator.remove()）
list.removeIf(s -> s.startsWith("tmp_"));

List<String> parent = new ArrayList<>(List.of("A", "B", "C", "D"));
List<String> sub = parent.subList(1, 3);  // [B, C] 视图，不是副本！

parent.add("E");  // 修改了父 list 的 modCount

System.out.println(sub.get(0));
// → 抛出 ConcurrentModificationException！
// subList 操作时会检查 parent 的 modCount 是否与创建时一致

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);

for (Map.Entry<String, Integer> e : map.entrySet()) {
    map.put("c", 3);  // ❌ CME! 新增 key 是结构性修改
}

// ✅ 正确：用 entrySet().iterator().remove()，或 ConcurrentHashMap
Map<String, Integer> concMap = new ConcurrentHashMap<>(map);
concMap.forEach((k, v) -> {
    concMap.put("c", 3);  // ✅ 弱一致，不抛异常
});

List<String> list = new ArrayList<>(List.of("A", "B", "C", "D"));

// ❌ 并行流中修改源集合——结果不可预测
list.parallelStream()
    .filter(s -> {
        list.add("X");  // 在 filter 中修改了源 list！
        return true;
    })
    .count();
// 可能抛 CME，也可能得到错误结果，也可能"看起来正常"

// ✅ 正确：Stream 应该是无副作用的，不要修改源集合
List<String> result = list.stream()
    .filter(s -> s.length() > 1)
    .collect(Collectors.toList());

// 单线程下最常见的 CME 场景：在 foreach 里删元素
List<String> list = new ArrayList<>(List.of("A", "B", "C"));

// 这不是多线程问题！这是用法错误！
for (String s : list) {
    if ("B".equals(s)) {
        list.remove(s);  // CME！单线程也会抛
    }
}

// 面试官问"fail-fast 和线程安全什么关系"时，核心答案：
// fail-fast 不是线程安全机制，它是检测"错误用法"的手段
// 单线程的错误用法同样会触发 CME