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 trước — Map và Set 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 & siêu tối ưu)

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

Nếu một Collection thông thường sử dụng cơ chế mặc định của Collection.removeIf (dùng Iterator lặp qua rồi gọi it.remove()), độ phức tạp thời gian khi áp dụng lên ArrayList sẽ là O(n²) vì mỗi lần xóa một phần tử, mảng sẽ phải dịch chuyển các phần tử phía sau qua System.arraycopy.

Tuy nhiên, ArrayList trong OpenJDK đã override (ghi đè) phương thức removeIf bằng một thuật toán tối ưu hóa đạt đến mức tuyệt hảo, đưa độ phức tạp về O(n) tuyệt đối!

🚀 Kỳ quan tối ưu: Cách ArrayList.removeIf hoạt động bên trong OpenJDK

Thay vì vừa duyệt vừa xóa và dịch chuyển mảng liên tục, mã nguồn ArrayList.removeIf của OpenJDK sử dụng chiến lược 2 luồng duyệt (2-phase scan) kết hợp với cấu trúc BitSet vô cùng thông minh:

1. Luồng duyệt 1 (Tìm kiếm & Đánh dấu bằng BitSet):

   • JVM duyệt qua mảng elementData từ đầu đến cuối (0 đến size - 1).
   • Với mỗi phần tử, nó thực hiện kiểm tra điều kiện (Predicate filter).
   • Nếu phần tử cần bị xóa, JVM sẽ đánh dấu chỉ số (index) của phần tử đó vào một BitSet (một mảng bit cực kỳ nhỏ gọn và hiệu năng cao).
   • Ưu điểm: Giai đoạn này chỉ đọc dữ liệu, hoàn toàn không làm thay đổi mảng, cực kỳ thân thiện với bộ đệm CPU cache và pipeline thực thi của vi xử lý.

2. Luồng duyệt 2 (Dồn dịch mảng 1 lần duy nhất):

   • Nếu không có phần tử nào bị đánh dấu xóa, hàm kết thúc ngay lập tức.
   • Nếu có phần tử cần xóa, JVM sẽ thực hiện luồng duyệt thứ hai để dồn các phần tử được giữ lại lên phía trước.
   • Nó duy trì một con trỏ ghi (writeIndex) bắt đầu từ phần tử đầu tiên bị xóa. JVM quét mảng từ vị trí đó đến cuối: những phần tử nào không bị đánh dấu trong BitSet (tức là phần tử cần giữ lại) sẽ được copy đè lên vị trí writeIndex, sau đó writeIndex++.
   • Toàn bộ quá trình dịch chuyển dồn mảng này chỉ diễn ra đúng 1 lần duy nhất trong một vòng quét tuyến tính, thay vì phải gọi System.arraycopy dịch mảng lặp đi lặp lại nhiều lần.
   • Cuối cùng, các slot thừa ở đuôi mảng sẽ được gán bằng null để tránh rò rỉ bộ nhớ (memory leak / loitering) giúp GC dọn dẹp, rồi cập nhật lại size và modCount đúng 1 lần.

📊 Bảng so sánh hiệu năng thực tế khi xóa k phần tử trong mảng n phần tử:

• Dùng Iterator thủ công (it.remove()): Phải thực hiện dịch mảng k lần → Độ phức tạp O(k × n), tiệm cận O(n²) nếu số lượng phần tử cần xóa lớn.
• Dùng ArrayList.removeIf: Luôn chạy trong O(n) thời gian, mỗi phần tử được kiểm tra đúng 1 lần và dịch chuyển tối đa đúng 1 lần.

💡 Khuyên dùng: Hãy luôn luôn ưu tiên sử dụng removeIf khi làm việc với ArrayList! Nó vừa giúp code ngắn gọn, mang phong cách lập trình khai báo (declarative) hiện đại, vừa tận dụng được sự tối ưu hóa phần cứng tuyệt vời từ các kỹ sư phát triển JDK.

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ử kế cuối (second-to-last) qua list.remove(o) trong for-each. Vì sao chương trình lại KHÔNG throw CME mà kết thúc hoàn toàn êm đẹp?

Vì sau khi xóa phần tử kế cuối ở vòng lặp thứ 4, size của danh sách giảm đi 1 (từ 5 xuống còn 4). Trong khi đó, cursor của iterator đã được tăng lên 4 ở cuối vòng lặp thứ 4. Ở đầu vòng lặp tiếp theo, Java kiểm tra điều kiện lặp bằng cách gọi hasNext(). Hàm này so sánh cursor != size (tức là 4 != 4), trả về false và vòng lặp thoát ngay lập tức mà không gọi hàm next(). Do next() không được chạy, hàm kiểm tra checkForComodification() hoàn toàn không được kích hoạt, giúp lọt lưới kiểm tra một cách ngẫu nhiên. Đây là một bug ẩn cực kỳ nguy hiểm, vì nó chạy trơn tru trong test với phần tử kế cuối nhưng sẽ crash dữ dội trên production với các vị trí khác!

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 tiếp theo — Comparator và Comparable đi sâu 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 đó, bài Immutable collections nói về List.of, Map.copyOf — khi nào dùng, vì sao nó không phải Collections.unmodifiableList.