Iterator, fail-fast và ConcurrentModificationException

TL;DR: Khi gọi list.remove() bên trong vòng lặp for-each, JVM sẽ ném ConcurrentModificationException (CME). Nguyên nhân nằm ở cơ chế fail-fast: mỗi thao tác thay đổi cấu trúc danh sách làm tăng biến đếm modCount, trong khi Iterator lưu bản chụp expectedModCount lúc khởi tạo. Khi next() phát hiện hai giá trị này lệch nhau, ngoại lệ sẽ lập tức được kích hoạt. Để xóa phần tử an toàn, giải pháp tối ưu nhất là sử dụng phương thức removeIf() của Java 8+.

1. Vì sao lệnh list.remove() trong vòng lặp for-each gây crash ứng dụng?

Xét kịch bản phổ biến trong hệ thống quản lý thư viện: kiểm tra và loại bỏ các ấn phẩm đã thanh lý hoặc hết hạn mượn khỏi danh mục:

public void purgeExpiredLoans(List<LoanRecord> loans) {
    for (LoanRecord loan : loans) {
        if (loan.isExpired()) {
            loans.remove(loan); // Direct removal on List
        }
    }
}

Khi đoạn mã này chạy trên môi trường thực tế với nhiều bản ghi hết hạn, JVM lập tức ném ra ngoại lệ:

Exception in thread "main" 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)

Tên gọi ConcurrentModificationException thường khiến lập trình viên lầm tưởng rằng có xung đột đa luồng xảy ra. Tuy nhiên, ngoại lệ này hoàn toàn có thể bùng nổ ngay trong một chương trình đơn luồng khi cấu trúc danh sách bị can thiệp trái phép trong lúc lặp.

2. Interface Iterator vận hành như thế nào bên dưới for-each?

Interface Iterator tách biệt logic duyệt phần tử khỏi cấu trúc lưu trữ nội bộ của tập hợp:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() { throw new UnsupportedOperationException(); }
}

Khi bạn viết vòng lặp for-each, trình biên dịch javac thực hiện chuyển đổi cú pháp (desugar) thành một vòng lặp while sử dụng Iterator:

// Equivalent desugared bytecode:
Iterator<LoanRecord> it = loans.iterator();
while (it.hasNext()) {
    LoanRecord loan = it.next();
    if (loan.isExpired()) {
        loans.remove(loan); // Modifies structure, desynchronizing counter!
    }
}

3. Biến đếm modCount và expectedModCount phối hợp ra sao?

Trong lớp cha AbstractList, Java duy trì một trường biến đếm:

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

Mỗi khi cấu trúc danh sách thay đổi (thêm phần tử, xóa phần tử, mở rộng mảng), modCount tự động tăng thêm 1 đơn vị. Trong khi đó, lớp nội bộ Itr của ArrayList lưu lại ảnh chụp của giá trị này tại thời điểm sinh ra:

private class Itr implements Iterator<E> {
    int cursor;                      // Index of next element to return
    int lastRet = -1;                // Index of last element returned
    int expectedModCount = modCount; // Snapshot taken at creation

    public E next() {
        checkForComodification();    // Validate sync state before moving forward
        int i = cursor;
        if (i >= size) throw new NoSuchElementException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

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

Khi bạn gọi loans.remove(loan), phương thức này của ArrayList làm tăng modCount. Ở vòng lặp kế tiếp, khi it.next() được gọi, hàm checkForComodification() phát hiện modCount != expectedModCount và lập tức ném ra ngoại lệ ConcurrentModificationException.

Ngược lại, nếu bạn gọi phương thức xóa của chính iterator (it.remove()), iterator sẽ đồng bộ lại trạng thái:

public void remove() {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
    expectedModCount = modCount; // Re-synchronize snapshot
}

4. Vì sao xóa phần tử kế cuối lại không gây crash?

Có một hiện tượng phản trực quan nổi tiếng: Nếu phần tử bạn xóa tình cờ là phần tử kế cuối (second-to-last) trong danh sách, chương trình sẽ thoát ra an toàn mà không ném ngoại lệ!

Giả sử danh sách có 3 phần tử ["A", "B", "C"] (size = 3):

1. Vòng lặp 1: Đọc "A", cursor = 1.
2. Vòng lặp 2: Đọc "B" (phần tử kế cuối), cursor = 2.
3. Trong vòng lặp 2, ta gọi list.remove("B") -> size giảm từ 3 xuống còn 2, modCount tăng lên.
4. Đầu vòng lặp kế tiếp, hasNext() kiểm tra điều kiện: return cursor != size;.
5. Lúc này cursor == 2 và size == 2, phép so sánh 2 != 2 trả về false!
6. Vòng lặp dừng lại ngay lập tức mà không gọi it.next(). Vì next() không được gọi, hàm kiểm tra checkForComodification() bị bỏ qua hoàn toàn.

[!WARNING] Đây là một lỗi nguy hiểm tiềm ẩn: mã nguồn có bug nhưng test unit có thể vượt qua nếu dữ liệu mẫu vô tình có phần tử cần xóa nằm ở vị trí kế cuối. Khi lên production với tập dữ liệu lớn, ứng dụng sẽ sụp đổ khi xóa phần tử ở các vị trí khác.

5. Fail-fast và Fail-safe khác nhau ở những điểm cốt lõi nào?

6. Bốn phương pháp xóa phần tử an toàn trong danh sách là gì?

Cách 1: Sử dụng removeIf (Khuyên dùng từ Java 8+)

// Idiomatic, declarative, optimal O(n)
loans.removeIf(LoanRecord::isExpired);

Trong OpenJDK, ArrayList ghi đè removeIf() bằng thuật toán 2 luồng duyệt (2-phase scan) kết hợp với BitSet:

1. Quét mảng và đánh dấu các vị trí cần xóa vào BitSet ($O(n)$ không biến đổi mảng, thân thiện với CPU cache).
2. Dồn các phần tử được giữ lại về phía trước chỉ trong một lần dịch chuyển duy nhất và xóa các tham chiếu đuôi thừa. Toàn bộ thao tác chỉ tốn $O(n)$ thay vì $O(n^2)$ của việc lặp it.remove().

Cách 2: Sử dụng Iterator.remove() thủ công

Iterator<LoanRecord> it = loans.iterator();
while (it.hasNext()) {
    LoanRecord loan = it.next();
    if (loan.isExpired()) {
        it.remove(); // Safe because iterator updates expectedModCount
    }
}

Cách 3: Sử dụng Stream Filter (Không thay đổi danh sách gốc)

List<LoanRecord> activeLoans = loans.stream()
    .filter(loan -> !loan.isExpired())
    .toList(); // Java 16+ unmodifiable list

Cách 4: Duyệt chỉ số ngược từ cuối mảng (Reverse Loop)

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

Khi xóa lùi từ cuối, các phần tử phía trước không bị thay đổi chỉ số, tránh được lỗi nhảy cóc phần tử.

7. Đâu là những cạm bẫy thường gặp với fail-fast?

❌ Cạm bẫy 1: Sửa đổi danh sách gốc khi đang dùng subList view

List<String> list = new ArrayList<>(List.of("A", "B", "C", "D"));
List<String> sub = list.subList(1, 3);
list.add("E"); // Structural modification on original list
System.out.println(sub.size()); // Throws ConcurrentModificationException!

subList() chỉ là một góc nhìn (view) trỏ vào mảng gốc. Mọi thay đổi cấu trúc trên danh sách gốc sẽ làm vô hiệu hóa view ngay lập tức.

❌ Cạm bẫy 2: Tin tưởng fail-fast để bảo đảm an toàn đa luồng Tài liệu JDK nêu rõ: cơ chế fail-fast chỉ hoạt động trên nguyên tắc nỗ lực tối đa (best-effort). Trong môi trường đa luồng không đồng bộ, hiện tượng Race Condition có thể khiến luồng đọc nhìn thấy giá trị modCount cũ từ CPU cache, dẫn đến sai lệch dữ liệu mà không hề ném ra ngoại lệ nào.

8. Đọc thêm từ tài liệu Oracle và các liên kết liên quan

9. Tóm tắt các điểm mấu chốt

• ConcurrentModificationException xuất hiện khi danh sách bị thay đổi cấu trúc ngoài tầm kiểm soát của iterator đang hoạt động.
• Biến modCount đếm số lần sửa đổi cấu trúc, được đối chiếu với expectedModCount mỗi khi gọi next().
• Hiện tượng xóa phần tử kế cuối không crash là kẽ hở ngẫu nhiên do hasNext() trả về false sớm.
• ArrayList.removeIf() là giải pháp xóa phần tử hiện đại và tối ưu nhất, đạt thời gian $O(n)$ nhờ thuật toán dồn mảng BitSet.
• Fail-fast là công cụ hỗ trợ gỡ lỗi đơn luồng, không phải giải pháp thay thế cho đồng bộ hóa đa luồng.

10. Câu hỏi tự kiểm tra

Bài tiếp theo: Comparator và Comparable — thứ tự sắp xếp và hợp đồng so sánh