Iterator, fail-fast và ConcurrentModificationException — vì sao remove trong for-each crash

TL;DR: Khi bạn remove() một phần tử trong lúc đang lặp for-each qua collection, JVM ném ConcurrentModificationException (CME) chứ không phải IndexOutOfBoundsException. Lý do là cơ chế modCount bên trong ArrayList/HashMap: mỗi lần collection bị thay đổi cấu trúc, modCount++. Iterator lưu snapshot expectedModCount lúc tạo; mỗi lần next() hoặc hasNext() so sánh — khác là throw. Đây gọi là fail-fast — phát hiện bug sớm, KHÔNG phải thread-safety. Bài này giải thích cơ chế đến tận source JDK, 4 cách remove an toàn, và 2 bẫy production-grade khi lệch hiểu giữa "fail-fast" và "thread-safe".

Bài 8.5 nói về Map/Set internals. Bài này quay lại một góc bị đánh giá thấp: vòng lặp. Vòng lặp là lúc bug runtime hay xuất hiện nhất — vì code biên dịch sạch nhưng đến runtime mới crash. Nắm được mechanism modCount bạn sẽ hiểu vì sao 1 dòng list.remove(item) đang chạy bình thường suốt sprint dev, đến production bùng ConcurrentModificationException ngay request đầu tiên.

1. Scenario — production incident lúc 2h sáng

Một service Java trong production xử lý job queue. Code review trước khi deploy không ai phát hiện bug:

public void processOrders(List<Order> orders) {
    for (Order o : orders) {
        if (o.isExpired()) {
            orders.remove(o);                    // remove during iteration
            continue;
        }
        process(o);
    }
}

Trong staging, list có 3-5 order, mỗi lần test 0-1 expired → không gặp lỗi. Đến production, queue tích 1200 order, 47 expired. Ngay phần tử expired đầu tiên:

Exception in thread "scheduler-1" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996)
    at com.example.OrderProcessor.processOrders(OrderProcessor.java:14)

Để hiểu vì sao crash, không thể chỉ "biết" rằng "không được remove trong for-each". Phải hiểu cơ chế bên dưới: ai count được sửa đổi, ai check, throw lúc nào.

2. Iterator là gì?

Iterator (theo java.util.Iterator, JDK API spec) là interface định nghĩa cách duyệt qua các phần tử của một collection mà KHÔNG cần biết cấu trúc bên trong (array, linked list, tree, hash table). Đây là pattern Iterator Pattern trong Gang of Four — tách logic "duyệt" khỏi logic "chứa dữ liệu".

Interface chỉ có 3 method (Java 8 thêm forEachRemaining default):

public interface Iterator<E> {
    boolean hasNext();        // con phan tu khong?
    E next();                 // tra ve phan tu hien tai, advance
    default void remove() { throw new UnsupportedOperationException(); }
    default void forEachRemaining(Consumer<? super E> action) { ... }
}

2.1 Cách lấy Iterator — 2 đường

List<String> list = List.of("a", "b", "c");

// Cach 1: goi truc tiep
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// Cach 2: for-each enhanced (Java 5+)
for (String s : list) {
    System.out.println(s);
}

Cách 2 là syntactic sugar của cách 1. Compiler desugar (biến đổi) for-each thành Iterator. Sẽ thấy ở section 4.

3. Mechanism — modCount bên trong ArrayList

Mở source JDK 21 (AbstractList.java), thấy field modCount ở class cha của ArrayList:

public abstract class AbstractList<E> {
    protected transient int modCount = 0;
}

Mỗi lần collection bị structural modification (thêm/xoá phần tử, resize array), modCount++. Trong ArrayList:

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        for (; i < size; i++) {
            if (es[i].equals(o)) break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

private void fastRemove(Object[] es, int i) {
    modCount++;                              // <-- TANG MOD COUNT
    final int newSize;
    if ((newSize = size - 1) > i) {
        System.arraycopy(es, i + 1, es, i, newSize - i);
    }
    es[size = newSize] = null;
}

add(), clear(), removeAll() cũng tăng modCount. Còn set(i, value) thì KHÔNG (chỉ thay value, không structural).

3.1 Iterator chụp snapshot lúc tạo

Khi gọi list.iterator(), ArrayList trả về 1 inner class Itr:

private class Itr implements Iterator<E> {
    int cursor;                              // chi so phan tu ke tiep
    int lastRet = -1;                        // chi so phan tu vua tra ve
    int expectedModCount = modCount;         // <-- SNAPSHOT TAI THOI DIEM TAO

    public boolean hasNext() { return cursor != size; }

    public E next() {
        checkForComodification();            // <-- KIEM TRA TRUOC
        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();
        }
    }
}

3 dòng quan trọng:

• Lúc tạo Iterator: expectedModCount = modCount (chụp giá trị hiện tại).
• Mỗi next()/remove() của Iterator: gọi checkForComodification().
• Nếu list bị sửa cấu trúc qua đường khác (list.remove(), list.add()) → modCount đã tăng nhưng expectedModCount không đổi → throw CME.

flowchart LR
    A[list.iterator] --> B[Itr created<br/>expectedModCount=5]
    B --> C[it.next]
    C --> D{modCount<br/>==<br/>expectedModCount?}
    D -- yes --> E[return element]
    D -- no --> F[throw CME]
    G[list.remove<br/>outside iterator] -.modCount=6.-> D

3.2 Iterator.remove() — đường an toàn duy nhất

Nếu remove qua chính iterator:

public void remove() {
    if (lastRet < 0) throw new IllegalStateException();
    checkForComodification();
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;        // <-- DONG BO LAI SAU REMOVE
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

Sau khi gọi ArrayList.this.remove(lastRet), modCount đã tăng. Iterator tự expectedModCount = modCount để giữ đồng bộ. Đây là lý do it.remove() không bị CME, còn list.remove() thì bị.

4. Vì sao for-each crash? Bytecode chứng minh

Compiler (javac) biến for-each thành Iterator pattern. Đoạn này:

for (Order o : orders) {
    if (o.isExpired()) orders.remove(o);
}

Sau khi desugar (đối chiếu bytecode dùng javap -c):

{
    Iterator<Order> it = orders.iterator();
    while (it.hasNext()) {
        Order o = it.next();                 // <-- check modCount o day
        if (o.isExpired()) orders.remove(o); // <-- structural mod, modCount++
    }
}

Vòng đầu tiên gặp o.isExpired() == true:

1. orders.remove(o) chạy → modCount từ 5 lên 6.
2. Vòng tiếp theo gọi it.hasNext() rồi it.next().
3. next() gọi checkForComodification() → modCount=6 != expectedModCount=5 → throw CME.

5. Fail-fast vs fail-safe — định nghĩa và so sánh

Fail-fast (theo Java Collections Framework spec): collection iterator throw ConcurrentModificationException khi phát hiện structural modification ngoài luồng iteration. Mục đích: giúp lập trình viên phát hiện bug sớm, không để dữ liệu silently corrupt.

Fail-safe (hay còn gọi weakly consistent): iterator hoạt động trên một snapshot hoặc bản copy của collection. Modification bên ngoài KHÔNG ảnh hưởng iterator (không throw, không thấy thay đổi).

5.1 CopyOnWriteArrayList — fail-safe điển hình

List<Integer> list = new CopyOnWriteArrayList<>(List.of(1, 2, 3, 4, 5));
for (Integer i : list) {
    if (i == 3) list.remove(Integer.valueOf(3));
    System.out.println(i);
}
// Output: 1 2 3 4 5  (KHONG throw, iterator dung snapshot)

Mỗi lần add/remove trên CopyOnWriteArrayList, JVM copy toàn bộ array bên dưới sang array mới. Iterator giữ tham chiếu array CŨ → modification không ảnh hưởng. Trade-off: write O(n), không phù hợp khi update nhiều, phù hợp khi read >> write (event listener list, observer pattern).

6. 4 cách remove an toàn

6.1 ❌ SAI — remove qua collection

for (Order o : orders) {
    if (o.isExpired()) orders.remove(o);     // CME khi co phan tu remove va con phan tu sau
}

6.2 ✅ Cách 1 — Iterator.remove() thủ công

Iterator<Order> it = orders.iterator();
while (it.hasNext()) {
    Order o = it.next();
    if (o.isExpired()) it.remove();          // SAFE
}

6.3 ✅ Cách 2 — removeIf (Java 8+, idiomatic)

orders.removeIf(o -> o.isExpired());

Bên trong removeIf cũng dùng Iterator + it.remove():

// java.util.Collection.removeIf default impl
default boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}

Code idiomatic hơn 1 dòng, ít bug hơn vì không tự viết loop.

6.4 ✅ Cách 3 — Stream filter (immutable, không sửa list cũ)

List<Order> active = orders.stream()
    .filter(o -> !o.isExpired())
    .toList();                                // Java 16+, immutable

Cách này không sửa orders — nó tạo list mới. Phù hợp khi bạn không muốn mutate input (functional style, dễ reasoning).

6.5 ✅ Cách 4 — Index loop ngược (rare, low-level)

for (int i = orders.size() - 1; i >= 0; i--) {
    if (orders.get(i).isExpired()) orders.remove(i);
}

Lặp ngược để khi remove index i, các index nhỏ hơn không dịch. Dùng remove(int index) (không phải remove(Object)). Dùng khi cần remove theo điều kiện phụ thuộc index, ít gặp.

7. Pitfall — structural modification ở entrySet, sublist

7.1 Map.entrySet() iterator cũng fail-fast

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

for (Map.Entry<String, Integer> e : map.entrySet()) {
    if (e.getValue() == 2) map.remove(e.getKey());     // CME!
}

Sửa đúng:

map.entrySet().removeIf(e -> e.getValue() == 2);

Hoặc:

Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getValue() == 2) it.remove();
}

7.2 List.subList() — view, không phải copy

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> view = list.subList(1, 4);          // [2, 3, 4]
list.add(99);                                      // structural mod tren list goc
view.size();                                       // CME!

subList() trả về view — share data với list gốc. Mọi structural modification trên list gốc làm view stale → next operation trên view throw CME.

Workaround: copy ra ArrayList mới nếu cần dùng độc lập:

List<Integer> copy = new ArrayList<>(list.subList(1, 4));
list.add(99);
copy.size();                                       // OK, copy doc lap

8. Pitfall — fail-fast KHÔNG phải thread-safety

Đây là hiểu lầm phổ biến nhất. Đọc Javadoc ArrayList:

The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis.

3 điểm chính:

1. Fail-fast là single-thread debug aid, không phải thread-safety mechanism.
2. Trong multi-thread, CME có thể KHÔNG được throw — race condition giữa modCount++ và checkForComodification() có thể trượt detection.
3. Có thể throw CME thậm chí khi code single-thread đúng — bug dạng equals() nested gọi modify, hoặc listener trigger modify.

8.1 Multi-thread — KHÔNG dùng ArrayList với Iterator

// THREAD A:
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
new Thread(() -> {
    for (Integer i : list) {
        Thread.sleep(10);
        System.out.println(i);
    }
}).start();

// THREAD B (cung luc):
list.add(4);

3 outcome có thể xảy ra:

• Thread A throw CME (lucky — fail-fast detected).
• Thread A in ra 1, 2, 3, 4 hoặc 1, 2, 4 (silent corruption — index dịch sau add).
• Thread A ArrayIndexOutOfBoundsException (race lúc resize).

Đúng cho multi-thread:

• Read >> write: CopyOnWriteArrayList.
• Đọc-ghi cân bằng: Collections.synchronizedList(list) + sync block khi iterate. Lưu ý: synchronizedList vẫn fail-fast khi iterate không trong sync block.

List<Integer> sync = Collections.synchronizedList(new ArrayList<>(List.of(1, 2, 3)));
synchronized (sync) {                            // <-- BAT BUOC luc iterate
    for (Integer i : sync) System.out.println(i);
}

9. 📚 Deep Dive — JDK source và spec

• AbstractList.modCount Javadoc — docs.oracle.com/.../AbstractList.html#modCount — quote chính thức về cơ chế modCount và best-effort fail-fast.
• ArrayList source JDK 21 — github.com/openjdk/jdk/blob/jdk-21+35/src/java.base/share/classes/java/util/ArrayList.java — đọc class Itr (line ~1000) để thấy expectedModCount snapshot và checkForComodification.
• JEP 312: Thread-Local Handshakes — không liên quan trực tiếp CME nhưng giải thích vì sao JVM khó cung cấp hard guarantee với unsynchronized state.
• Javadoc Collection.removeIf — docs.oracle.com/.../Collection.html#removeIf-java.util.function.Predicate- — default impl chính là pattern Iterator + it.remove().
• Effective Java item 78 (Joshua Bloch) — "Synchronize access to shared mutable data" — giải thích vì sao synchronizedList + sync block là cần thiết.

10. Self-check

Câu 1. Vì sao list.remove(o) trong for-each throw CME còn it.remove() thì không?

list.remove(o) đi đường ngoài → modCount++ mà expectedModCount của Iterator không đổi → lần next() tiếp theo checkForComodification thấy lệch → throw. Còn it.remove() sau khi xoá thực hiện expectedModCount = modCount để đồng bộ lại → không lệch ở vòng kế. Hiểu sâu hơn: Iterator phải biết khi nào structural mod đến từ chính nó để cập nhật snapshot — đây là lý do remove qua iterator là đường an toàn duy nhất khi muốn vừa duyệt vừa xoá.

Câu 2. Trong list 5 phần tử, bạn xoá phần tử cuối qua list.remove(o) trong for-each. Vì sao có thể KHÔNG throw CME?

Vì sau remove, cursor của iterator đã vượt size mới (4) — it.hasNext() trả false, vòng lặp thoát mà chưa kịp gọi next() lần nữa. Không gọi next() thì không có chỗ check modCount. Đây là lý do bug "ẩn" — test với 1 phần tử expired ở vị trí cuối thì pass, đến production list lớn với expired ở giữa thì crash.

Câu 3. CopyOnWriteArrayList không bao giờ throw CME — vậy có nên dùng cho mọi trường hợp để tránh bug?

Không. CopyOnWriteArrayList copy toàn bộ array mỗi lần ghi → write O(n), memory spike. Phù hợp khi read >> write (listener list, config snapshot ít thay đổi). Với workload write-heavy, hiệu năng tệ hơn ArrayList rất nhiều. Quan trọng hơn: fail-fast của ArrayList là tính năng debug — giúp phát hiện bug structural mod sớm. Dùng CopyOnWriteArrayList chỉ vì "không muốn CME" là che bug, không phải sửa bug.

Câu 4. Đoạn code sau crash hay không, vì sao?

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
for (Integer i : list) {
    list.set(0, 99);
}

KHÔNG crash. set(int, value) chỉ ghi đè giá trị tại index, không structural modification (size không đổi, không shift element) → modCount KHÔNG tăng → checkForComodification không phát hiện gì. Đây là điểm tinh tế: structural mod = thay đổi size hoặc thứ tự (add/remove/clear/sort), còn replace giá trị thì không. Hiểu đúng định nghĩa structural giúp tránh hiểu nhầm "mọi sửa đổi đều bị fail-fast".

Câu 5. Vì sao Javadoc gọi fail-fast là "best-effort", không phải "guaranteed"?

Vì trong môi trường multi-thread không sync, race giữa modCount++ của thread A và checkForComodification của thread B có thể trượt detection (thread B đọc modCount cache cũ, không thấy thay đổi). JVM không thể đảm bảo phát hiện 100% mà không synchronize — mà sync thì performance tệ. Chọn best-effort: detect được phần lớn case → giúp dev sớm, nhưng không thay thế được proper synchronization. Hệ quả: production multi-thread phải dùng concurrent collection chứ KHÔNG dựa vào CME để biết có race.

Câu 6. Bạn cần xoá tất cả entry có value > 100 trong Map<String, Integer>. Viết bằng removeIf đúng cách.

map.entrySet().removeIf(e -> e.getValue() > 100); Bốn điểm cần đúng: (1) gọi entrySet() rồi mới removeIf — vì Map không có removeIf trực tiếp; (2) lambda nhận Map.Entry<String, Integer>, không phải value đơn lẻ; (3) entrySet() trả về view nên modify nó modify map gốc; (4) removeIf an toàn vì internal dùng Iterator + it.remove(). Sai thường gặp: dùng keySet().removeIf(k -> map.get(k) > 100) — vẫn đúng nhưng phải gọi map.get(k) thêm O(1) lookup mỗi entry, kém hiệu năng hơn iterate entrySet() trực tiếp.

Câu 7. Fail-fast và fail-safe khác nhau ở điểm gì về memory?

Fail-fast (ArrayList, HashMap) chỉ giữ 1 biến modCount int + iterator giữ expectedModCount int — overhead gần như zero. Fail-safe (CopyOnWriteArrayList) phải copy toàn bộ array mỗi lần ghi, iterator giữ tham chiếu snapshot — nếu list dài 10k phần tử và có 100 iterator song song, mỗi snapshot là 10k references → memory blow-up. ConcurrentHashMap không full copy mà chỉ snapshot bucket array tại thời điểm đọc, weakly consistent — cân bằng giữa overhead và safety.

Bài tiếp theo

Bài 8.7 sẽ đi sâu Comparator và Comparable — vì sao 2 interface này tồn tại song song, transitivity contract khi sort, NaN edge case, và bug compareTo ngầm phổ biến nhất khi viết entity. Sau đó 8.8 nói immutable collections (List.of, Map.copyOf) — khi nào dùng, vì sao nó không phải Collections.unmodifiableList.