[Advanced Java] Iterator, ListIterator và fail-fast so với fail-safe trong Java

Gần như chắc chắn bạn đã gặp ConcurrentModificationException rồi: bạn xoá một phần tử ngay trong vòng lặp for nâng cao, chương trình nổ, và bạn học được rằng phải dùng Iterator.remove() hoặc removeIf. Đó là cách sửa đúng, và một khoá cơ bản thường dừng lại ở đó. Bài này nói về bộ máy nằm bên dưới nó.

Bộ máy đó đáng để hiểu, vì bản thân cái exception không phải chỗ thú vị. Chỗ thú vị là phép kiểm tra sinh ra nó được ghi rõ trong tài liệu là best-effort, và tồn tại một trường hợp nhỏ, hoàn toàn tất định, chỉ một thread, trong đó một vòng lặp sai lặng lẽ cho ra kết quả sai mà không ném gì cả. Trường hợp đó được minh hoạ bên dưới bằng output thật.

Mọi dòng output, stack trace, giá trị bộ đếm và đoạn disassembly bên dưới đều được tạo ra bằng cách compile và chạy code trên OpenJDK 21.0.6 (arm64). Không có thread nào được khởi động trong bài này; phần về collection concurrent nói rõ claim nào đến từ contract trong tài liệu chứ không phải từ một thí nghiệm.

Contract của Iterator thực sự gồm những gì

java.util.Iterator chỉ có bốn method, trong đó code hằng ngày chỉ gọi hai:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() { throw new UnsupportedOperationException("remove"); }
    default void forEachRemaining(Consumer<? super E> action) { ... }
}

remove và forEachRemaining trở thành method default từ Java 8, đó là lý do một iterator tự viết chỉ implement hasNext và next vẫn compile được.

Phần implementation chỉ là hai field int. Đây là java.util.ArrayList$Itr lấy nguyên từ source JDK 21, giữ nguyên cả comment của tác giả JDK:

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

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

cursor là index của phần tử sẽ được trả về tiếp theo, nghĩa là cursor không nằm trên một phần tử nào — nó nằm trong khoảng trống trước một phần tử. Ba phần tử vì thế có bốn vị trí cursor hợp lệ, từ 0 đến 3, và hasNext() không là gì khác ngoài cursor != size.

lastRet là nửa còn lại của contract. Nó ghi lại index mà next() vừa trả về, và đó chính là thứ remove() xoá. Nó khởi tạo bằng -1, và remove() đặt nó về -1 sau mỗi lần xoá thành công.

Ba exception mà contract này định nghĩa

Hai field đó sinh ra toàn bộ ba kiểu thất bại mà contract có thể tạo ra. Gọi remove() trước bất kỳ next() nào khiến lastRet vẫn còn là -1:

import java.util.*;

public class Traces {
    public static void main(String[] args) {
        List<String> l = new ArrayList<>(List.of("ada", "linus"));
        Iterator<String> it = l.iterator();
        it.remove();
    }
}

Exception in thread "main" java.lang.IllegalStateException
	at java.base/java.util.ArrayList$Itr.remove(ArrayList.java:1062)
	at Traces.main(Traces.java:6)

Gọi remove() hai lần liên tiếp cũng hỏng y hệt, và vì đúng cùng một lý do — lần gọi đầu đã đưa lastRet về -1:

Iterator<String> it = l.iterator();
it.next();
it.remove();
it.remove();

Exception in thread "main" java.lang.IllegalStateException
	at java.base/java.util.ArrayList$Itr.remove(ArrayList.java:1062)
	at Traces3.main(Traces3.java:8)

Chú ý là IllegalStateException không kèm message nào. Trong log bạn chẳng có gì để đọc ngoài cái frame nó phát ra, nên hãy nhớ hình dạng của nó.

Kiểu thất bại thứ ba là gọi next() khi cursor == size:

List<String> l = new ArrayList<>(List.of("ada"));
Iterator<String> it = l.iterator();
it.next();
it.next();

Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1052)
	at Traces2.main(Traces2.java:7)

hasNext() là thứ duy nhất đứng giữa vòng lặp và exception đó. Nó là một câu hỏi, không phải một hàng rào: không có gì bắt bạn phải gọi nó, và next() cũng không tự gọi nó giúp bạn.

Còn một chi tiết nữa trong source, vì nó quan trọng ở phần sau. remove() làm thế này:

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

Hai dòng trong đó đang làm việc âm thầm nhưng thiết yếu. cursor = lastRet kéo cursor lùi về đúng chỗ trống mà phép xoá để lại, đó là lý do xoá qua iterator không bao giờ bỏ sót phần tử liền sau. Và expectedModCount = modCount đồng bộ lại iterator với list, đó là toàn bộ lý do phép xoá này hợp lệ còn list.remove(...) trực tiếp thì không.

Vòng lặp for nâng cao chính là Iterator, và bytecode chứng minh điều đó

Vòng lặp for nâng cao trên một Collection không phải là một tính năng ngôn ngữ có hỗ trợ riêng ở runtime. Compiler viết lại nó thành các lời gọi iterator, và javap -c cho thấy chính xác cách viết lại đó:

import java.util.List;

public class ForEach {
    static int sum(List<Integer> xs) {
        int total = 0;
        for (int x : xs) {
            total += x;
        }
        return total;
    }
}

javac ForEach.java && javap -c -p ForEach.class

  static int sum(java.util.List<java.lang.Integer>);
    Code:
       0: iconst_0
       1: istore_1
       2: aload_0
       3: invokeinterface #7,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
       8: astore_2
       9: aload_2
      10: invokeinterface #13,  1           // InterfaceMethod java/util/Iterator.hasNext:()Z
      15: ifeq          38
      18: aload_2
      19: invokeinterface #19,  1           // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
      24: checkcast     #23                 // class java/lang/Integer
      27: invokevirtual #25                 // Method java/lang/Integer.intValue:()I
      30: istore_3
      31: iload_1
      32: iload_3
      33: iadd
      34: istore_1
      35: goto          9
      38: iload_1
      39: ireturn

(Constructor mặc định đã được lược bỏ; mọi thứ còn lại là nguyên văn.)

Đọc bốn lệnh quan trọng theo thứ tự. List.iterator() được gọi đúng một lần và kết quả lưu vào slot 2. Iterator.hasNext() chạy ở đầu mỗi vòng và ifeq nhảy ra khi nó trả về false. Iterator.next() cho ra một Object, checkcast ép nó về Integer — đó là type erasure lộ ra — và goto 9 khép vòng lặp lại.

Hai hệ quả rơi thẳng ra từ đoạn listing đó:

• Iterator nằm ở local slot 2 và code của bạn không có tên nào cho nó. Đó chính là lý do bạn không thể gọi remove() an toàn từ bên trong vòng lặp for nâng cao: object cho phép bạn làm việc đó có tồn tại, nhưng ngôn ngữ giấu nó đi. Viết tay dạng for (Iterator<String> it = list.iterator(); it.hasNext(); ) không phải là một bước lùi về phong cách — đó là cách duy nhất để có reference tới object đó.
• hasNext() được gọi trước mỗi next(), và next() mới là chỗ đặt phép kiểm tra comodification. Hãy nhớ điều này; cả phần sau xoay quanh nó.

Duyệt array được biên dịch thành một thứ hoàn toàn khác

Cùng cú pháp đó nhưng trên một array thì không sinh ra iterator nào cả:

static int sum(int[] xs) {
    int total = 0;
    for (int x : xs) total += x;
    return total;
}

       3: astore_2
       4: aload_2
       5: arraylength
       6: istore_3
       7: iconst_0
       8: istore        4
      10: iload         4
      12: iload_3
      13: if_icmpge     33
      16: aload_2
      17: iload         4
      19: iaload
      20: istore        5
      ...
      27: iinc          4, 1
      30: goto          10

arraylength, một index ở slot 4, iaload, iinc. Đó là một vòng lặp đếm bình thường. Một array không thể bị structural modification, nên ở đây không có gì để phát hiện và không thể có ConcurrentModificationException — cũng là lý do cùng một cú pháp trên List và trên array lại hành xử khác nhau đến vậy khi có thứ gì đó thay đổi bên dưới.

ListIterator: iterator hai chiều, có vị trí, chỉ List mới có

Iterator là mẫu số chung nhỏ nhất: chỉ đi tới, không có vị trí, và remove là phép biến đổi duy nhất. List cung cấp một thứ lớn hơn qua listIterator(), và nó là interface duy nhất trong collections framework làm vậy — Set và các view của Map chỉ có iterator() chứ không có bản có vị trí, vì chúng không có index nào để nói tới.

nextIndex() và previousIndex() chỉ là cursor và cursor - 1 được phơi ra thành method, nhờ vậy mô hình "nằm giữa các phần tử" nhìn thấy được từ bên ngoài:

List<String> words = new ArrayList<>(List.of("ada", "linus", "grace"));
ListIterator<String> it = words.listIterator();
System.out.println("start            nextIndex=" + it.nextIndex() + " previousIndex=" + it.previousIndex());
System.out.println("next() -> " + it.next() + "   nextIndex=" + it.nextIndex() + " previousIndex=" + it.previousIndex());
System.out.println("next() -> " + it.next() + " nextIndex=" + it.nextIndex() + " previousIndex=" + it.previousIndex());
System.out.println("previous() -> " + it.previous() + " nextIndex=" + it.nextIndex() + " previousIndex=" + it.previousIndex());

start            nextIndex=0 previousIndex=-1
next() -> ada   nextIndex=1 previousIndex=0
next() -> linus nextIndex=2 previousIndex=1
previous() -> linus nextIndex=1 previousIndex=0

Nhìn dòng cuối. previous() trả về linus — đúng phần tử mà next() vừa trả về. Cursor lùi lại qua nó chứ không nhảy quá nó, vì một cursor nằm trong khoảng trống thì có thể vượt qua theo cả hai hướng. Gọi xen kẽ next() và previous() sẽ trả về mãi cùng một phần tử, và đó là hành vi đúng chứ không phải bug.

Muốn duyệt list theo chiều ngược, hãy đặt cursor ở đầu bên kia:

List<String> back = new ArrayList<>(List.of("a", "b", "c"));
ListIterator<String> r = back.listIterator(back.size());
while (r.hasPrevious()) System.out.print(r.previous() + " ");

c b a

set thay thế đúng phần tử next() vừa trả về

set là method không có bản tương đương bên Iterator và cũng là thứ người ta cần nhiều nhất. Nó ghi đè phần tử tại lastRet mà không đụng tới size, nên nó không phải structural modification và không làm xáo trộn trạng thái cursor nào khác:

List<String> up = new ArrayList<>(List.of("ada", "linus", "grace"));
for (ListIterator<String> j = up.listIterator(); j.hasNext(); ) {
    String s = j.next();
    if (s.length() > 3) j.set(s.toUpperCase());
}
System.out.println(up);

[ada, LINUS, GRACE]

Lựa chọn thay thế là vòng lặp theo index với list.set(i, ...), chạy tốt trên ArrayList nhưng bậc hai trên LinkedList vì mỗi set(i, ...) lại phải đi lại từ đầu chuỗi node. ListIterator.set có sẵn tính vị trí mà không tốn gì: nó vốn đã biết mình đang ở đâu.

set có cùng điều kiện tiên quyết với remove — nó cần lastRet >= 0 — nên gọi nó trước lần next() đầu tiên sẽ ném IllegalStateException.

add chèn trước cursor, và cursor nhảy qua phần tử mới

add là method tinh tế nhất. Javadoc nói phần tử được chèn ngay trước vị trí cursor ngầm định, còn source JDK cho thấy điều đó khiến cursor phải trả giá gì:

public void add(E e) {
    checkForComodification();
    try {
        int i = cursor;
        ArrayList.this.add(i, e);
        cursor = i + 1;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

Ba tác dụng, đều kiểm chứng được. Cursor nhảy qua phần tử mới, nên lần next() kế tiếp bỏ qua nó và vòng lặp không thể tự chèn thành vòng lặp vô hạn. lastRet quay về -1, nên set và remove ngay sau một add là bất hợp lệ. Và expectedModCount được đồng bộ lại, nên phép chèn không làm hỏng chính iterator vừa thực hiện nó.

List<String> ins = new ArrayList<>(List.of("a", "b", "c"));
ListIterator<String> k = ins.listIterator();
while (k.hasNext()) {
    String s = k.next();
    if (s.equals("b")) {
        k.add("B2");
        System.out.println("after add(\"B2\") nextIndex=" + k.nextIndex()
                + " previousIndex=" + k.previousIndex() + " list=" + ins);
    }
}
System.out.println("after the loop " + ins);

after add("B2") nextIndex=3 previousIndex=2 list=[a, b, B2, c]
after the loop [a, b, B2, c]

nextIndex đi từ 2 lên 3 qua phép chèn: cursor ở lại phía bên kia của B2, vòng lặp đi tiếp tới c, và B2 không bao giờ được next() trả về. Nếu bạn thật sự muốn nhìn thấy phần tử vừa chèn thì previous() trả về nó — và tác dụng thứ ba cũng tự chứng minh:

List<String> l = new ArrayList<>(List.of("a", "b"));
ListIterator<String> it = l.listIterator();
it.next();
it.add("x");
try { it.set("y"); } catch (IllegalStateException e) {
    System.out.println("set() after add() -> " + e.getClass().getName());
}
try { it.remove(); } catch (IllegalStateException e) {
    System.out.println("remove() after add() -> " + e.getClass().getName());
}
System.out.println("list = " + l);
System.out.println("previous() -> " + it.previous());

set() after add() -> java.lang.IllegalStateException
remove() after add() -> java.lang.IllegalStateException
list = [a, x, b]
previous() -> x

Fail-fast hoạt động ra sao: modCount và expectedModCount

Cơ chế chỉ là hai số nguyên, và cả hai đều đọc được từ một JVM đang chạy.

AbstractList khai báo số thứ nhất. Javadoc trong source JDK định nghĩa nó rất chính xác: "The number of times this list has been structurally modified. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results."

Mỗi iterator copy giá trị đó vào expectedModCount của riêng nó lúc được tạo, và checkForComodification so hai giá trị:

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

Reflection làm cho hai bộ đếm trở nên cụ thể. modCount là protected trên AbstractList còn expectedModCount là package-private trên ArrayList$Itr, nên muốn đọc chúng phải mở module trên dòng lệnh:

import java.lang.reflect.Field;
import java.util.*;

public class ModCount {
    static Field mod, expected;

    static String state(List<?> list, Iterator<?> it) throws Exception {
        return String.format("modCount=%d expectedModCount=%d", mod.getInt(list), expected.getInt(it));
    }

    public static void main(String[] args) throws Exception {
        mod = java.util.AbstractList.class.getDeclaredField("modCount");
        mod.setAccessible(true);

        List<String> list = new ArrayList<>(List.of("ada", "linus", "grace"));
        Iterator<String> it = list.iterator();

        expected = it.getClass().getDeclaredField("expectedModCount");
        expected.setAccessible(true);

        System.out.println("iterator class            " + it.getClass().getName());
        System.out.println("after iterator()          " + state(list, it));
        System.out.println("after next() -> " + it.next() + "     " + state(list, it));
        list.add("ken");
        System.out.println("after list.add(\"ken\")     " + state(list, it));
        try {
            it.next();
        } catch (ConcurrentModificationException e) {
            System.out.println("next() threw              " + e.getClass().getName());
        }
    }
}

javac ModCount.java && java --add-opens java.base/java.util=ALL-UNNAMED ModCount

iterator class            java.util.ArrayList$Itr
after iterator()          modCount=0 expectedModCount=0
after next() -> ada     modCount=0 expectedModCount=0
after list.add("ken")     modCount=1 expectedModCount=0
next() threw              java.util.ConcurrentModificationException

Vẫn chương trình đó nhưng thay list.add(...) bằng it.remove() thì hai bộ đếm đi cùng nhịp, vì xoá qua iterator ghi expectedModCount = modCount trước khi thoát:

after iterator()          modCount=0 expectedModCount=0
after next() -> ada     modCount=0 expectedModCount=0
after it.remove()         modCount=1 expectedModCount=1
after next() -> linus   modCount=1 expectedModCount=1
list = [linus, grace]

Toàn bộ cơ chế chỉ có vậy. Không thread, không lock, không monitor. Chỉ là một bộ đếm đem so với một bản chụp của chính nó.

Thế nào là một structural modification

Định nghĩa nói "thay đổi size, hoặc xáo trộn nó theo cách khác" — và vế thứ hai không phải câu trang trí. Dò từng thao tác bằng đúng kiểu reflection đó cho thấy thao tác nào làm tăng modCount:

Hai dòng đáng chú ý. sort và replaceAll không đổi size chút nào mà vẫn là structural, bởi vì sắp xếp lại một list dưới một cursor đang sống sẽ khiến vòng duyệt trả về sai phần tử — đúng vế "perturb" trong Javadoc. Sort một list đang duyệt thì ném exception:

List<String> l = new ArrayList<>(List.of("b", "a", "c"));
Iterator<String> it = l.iterator();
System.out.println("next() -> " + it.next());
l.sort(null);
System.out.println("size unchanged: " + l.size() + ", list = " + l);
it.next();

next() -> b
size unchanged: 3, list = [a, b, c]
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)
	at SortDuring.main(SortDuring.java:9)

Còn removeIf(s -> false) không làm tăng bộ đếm, vì ArrayList.removeIf chỉ chạm vào modCount khi nó thật sự xoá cái gì đó. Một removeIf không khớp phần tử nào sẽ để mọi iterator đang sống nguyên vẹn.

Fail-fast là best-effort, không phải bảo đảm

Đây là đoạn trong Javadoc của ArrayList mà hầu như không tutorial nào trích:

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. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Người ta thường đọc đoạn này như một lời rào đón về thread. Không chỉ về thread đâu. Phép kiểm tra nằm bên trong next() và không nằm trong method nào khác — đặc biệt là không nằm trong hasNext(), vốn chỉ là return cursor != size; chứ không có gì thêm. Vậy nên một structural modification làm cho hasNext() trả về false sẽ kết thúc vòng lặp trước khi next() kịp lên tiếng.

Xoá phần tử áp chót của một list ngay trong vòng lặp for nâng cao làm đúng chuyện đó:

import java.util.*;

public class Quiet {
    public static void main(String[] args) {
        List<String> a = new ArrayList<>(List.of("a", "b", "c", "d"));
        int seen = 0;
        for (String s : a) {
            seen++;
            System.out.println("visited " + s);
            if (s.equals("c")) a.remove(s);
        }
        System.out.println("no exception, list = " + a + ", visited " + seen + " of 4");
    }
}

visited a
visited b
visited c
no exception, list = [a, b, d], visited 3 of 4

Ba phần tử được duyệt trên tổng số bốn. d không hề được nhìn tới, vòng lặp thoát bình thường, và không có gì được ném ra. Hãy lần theo bộ đếm: sau khi next() trả về c thì cursor là 3 và size là 4; a.remove("c") kéo size xuống 3 và đẩy modCount lên 1; vòng lặp hỏi hasNext(), nó tính 3 != 3 và trả về false. Phép so sánh lẽ ra bắt được sự lệch pha thì không bao giờ được chạm tới.

Trong ví dụ trên, list còn lại tình cờ đúng. Đổi dữ liệu đi một phần tử là nó sai ngay:

List<String> tags = new ArrayList<>(List.of("keep", "keep", "drop", "drop"));
for (String t : tags) {
    if (t.equals("drop")) tags.remove(t);
}
System.out.println("for-each remove  -> " + tags);

List<String> ok = new ArrayList<>(List.of("keep", "keep", "drop", "drop"));
ok.removeIf(t -> t.equals("drop"));
System.out.println("removeIf         -> " + ok);

for-each remove  -> [keep, keep, drop]
removeIf         -> [keep, keep]

Một bộ lọc lẽ ra phải xoá mọi drop lại bỏ sót một cái, im lặng, không exception và không cảnh báo. Đó là cái giá thực tế của "best-effort", và cũng là điều quan trọng nhất trong bài này: ConcurrentModificationException là một máy dò bug nhưng đôi khi nó dò trượt. LinkedList hành xử y hệt — ListItr.hasNext() của nó là nextIndex < size, nên cùng phép xoá đó cũng cho ra [a, b, d].

⚠️ Đừng bao giờ coi một lần chạy sạch sẽ là bằng chứng rằng vòng lặp không sửa thứ nó đang duyệt. Fail-fast là cái chuông báo khói, không phải một type system.

HashMap cũng có đúng lỗ hổng đó

Iterator của HashMap có hasNext() khác — nó là next != null, đi theo bảng bucket chứ không đếm index — nhưng hình dạng của lỗ hổng thì giống hệt. Xoá đúng mapping nằm cuối theo thứ tự duyệt sẽ kết thúc vòng duyệt mà không kêu ca gì:

Map<String, Integer> m = new LinkedHashMap<>();
m.put("a", 1); m.put("b", 2); m.put("c", 3);
List<String> order = new ArrayList<>(m.keySet());
System.out.println("iteration order " + order);
for (String k : m.keySet()) {
    if (k.equals(order.get(order.size() - 1))) m.remove(k);
}
System.out.println("removing the last key in iteration order -> no exception, map = " + m);

iteration order [a, b, c]
removing the last key in iteration order -> no exception, map = {a=1, b=2}

Xoá bất kỳ key nào sớm hơn thì ném exception, đúng như mong đợi. LinkedHashMap được dùng ở đây chỉ để thứ tự duyệt cố định và minh hoạ lặp lại được; một HashMap thường cũng có đúng lỗ hổng đó tại phần tử nào tình cờ đứng cuối.

Cũng nên để ý thứ không ném exception: ghi đè value của một key đã tồn tại không phải structural modification, vì hình dạng của bảng không đổi.

Map<String, Integer> hm2 = new HashMap<>();
hm2.put("a", 1); hm2.put("b", 2);
Iterator<String> h2 = hm2.keySet().iterator();
h2.next();
hm2.put("a", 7);
System.out.println("value-only put -> next() = " + h2.next());

value-only put -> next() = b

Fail-safe iterator, và tên gọi thật sự trong JDK

"Fail-safe iterator" là từ vựng phỏng vấn, không phải từ vựng của JDK. Chuỗi fail-safe không xuất hiện ở bất kỳ đâu trong source java.util hay java.util.concurrent của JDK 21. Thứ mà Javadoc thật sự phân biệt là hai hành vi được ghi rõ: iterator kiểu snapshot và iterator weakly consistent. Chúng không phải một, và khác biệt đó nhìn thấy được ngay trong một chương trình chỉ có một thread.

Thí nghiệm bên dưới giống nhau cho cả ba: dựng một collection ba phần tử, gọi next() một lần, thêm "d", rồi duyệt nốt.

CopyOnWriteArrayList duyệt trên một snapshot

Javadoc của CopyOnWriteArrayList nói thẳng một cách hiếm thấy: "The 'snapshot' style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created."

CopyOnWriteArrayList<String> cw = new CopyOnWriteArrayList<>(List.of("a", "b", "c"));
Iterator<String> i2 = cw.iterator();
System.out.println("  next() -> " + i2.next());
cw.add("d");
while (i2.hasNext()) System.out.println("  next() -> " + i2.next());
System.out.println("  list = " + cw);

  next() -> a
  next() -> b
  next() -> c
  list = [a, b, c, d]

List kết thúc với bốn phần tử còn iterator trả về ba. Lần ghi đó không bị bỏ sót, không bị hoãn, cũng không bị mất — nó đi vào một array khác, còn iterator vẫn đang giữ array cũ. Để ý là "không bao giờ ném" không đồng nghĩa với "thấy đúng sự thật": iterator này lạc hậu một cách chắc chắn và vĩnh viễn ngay khi có ai đó ghi.

Vì array nó giữ là một bản copy đông cứng mà list không còn sở hữu nữa, các method biến đổi hoàn toàn không thể hoạt động:

Iterator<String> it2 = cw.iterator();
it2.next();
it2.remove();

Exception in thread "main" java.lang.UnsupportedOperationException
	at java.base/java.util.concurrent.CopyOnWriteArrayList$COWIterator.remove(CopyOnWriteArrayList.java:1208)
	at CowRemove.main(CowRemove.java:8)

remove, set và add trên một COWIterator đều ném exception đó, với message null. Đây là một giới hạn API thật chứ không phải chi tiết vụn: code viết dựa trên Iterator.remove() sẽ không sống sót khi bị đưa cho một CopyOnWriteArrayList.

Cái giá của snapshot, đếm bằng số lần copy

Cái tên đã nói rõ giá phải trả. Mỗi lời gọi biến đổi đều cấp phát nguyên một array mới và copy nội dung cũ sang. Reflect vào field private array rồi theo dõi identity của nó thay đổi sẽ đếm chính xác số lần copy (chương trình này cần thêm --add-opens java.base/java.util.concurrent=ALL-UNNAMED bên cạnh cái java.base/java.util):

Field arr = CopyOnWriteArrayList.class.getDeclaredField("array");
arr.setAccessible(true);
CopyOnWriteArrayList<Integer> cow = new CopyOnWriteArrayList<>();
Object previous = arr.get(cow);
int newArrays = 0;
long elementsCopied = 0;
for (int i = 0; i < 1000; i++) {
    int before = ((Object[]) arr.get(cow)).length;
    cow.add(i);
    Object now = arr.get(cow);
    if (now != previous) { newArrays++; elementsCopied += before; previous = now; }
}

CopyOnWriteArrayList: 1000 add() calls
  new backing arrays allocated 1000
  element slots copied         499500
ArrayList: 1000 add() calls
  new backing arrays allocated 13
  element slots copied         2456

Một nghìn lần append, một nghìn lần cấp phát array, và 499.500 ô phần tử bị copy — đúng tổng 0 + 1 + ... + 999, tức bậc hai theo số lần ghi. ArrayList chỉ cấp phát 13 array cho cùng một nghìn lần append vì nó lớn theo cấp số nhân và phân bổ đều chi phí. Các con số ở đây là số lần cấp phát chứ không phải thời gian; chúng chính xác và lặp lại được, và chúng là lý do CopyOnWriteArrayList được tài liệu mô tả cho những collection đọc liên tục và ghi rất hiếm, chẳng hạn một danh sách listener.

ConcurrentHashMap là weakly consistent, không phải snapshot

Iterator của ConcurrentHashMap không copy gì cả. Nó đi trên bảng đang sống, và bảo đảm nó đưa ra là bảo đảm được định nghĩa trong tài liệu package java.util.concurrent:

• they may proceed concurrently with other operations
• they will never throw ConcurrentModificationException
• they are guaranteed to traverse elements as they existed upon construction exactly once, and may (but are not guaranteed to) reflect any modifications subsequent to construction.

Gạch đầu dòng thứ ba mới là chỗ quan trọng, và "may but are not guaranteed to" nghĩa là hành vi thật sự không được đặc tả. Chạy lại đúng thí nghiệm đó:

ConcurrentHashMap<String, Integer> ch = new ConcurrentHashMap<>();
ch.put("a", 1); ch.put("b", 2); ch.put("c", 3);
Iterator<Map.Entry<String, Integer>> i3 = ch.entrySet().iterator();
System.out.println("  next() -> " + i3.next());
ch.put("d", 4);
while (i3.hasNext()) System.out.println("  next() -> " + i3.next());

  next() -> a=1
  next() -> b=2
  next() -> c=3
  next() -> d=4

d được thêm sau khi iterator đã tạo mà iterator vẫn trả về nó. Đó là kết quả ngược hẳn với CopyOnWriteArrayList trên cùng các bước, và cả hai đều đúng — chúng implement hai contract khác nhau. Chạy lại nhiều lần đều cho cùng output, nhưng tính lặp lại ở đây là đặc tính của một map nhỏ trên một JVM cụ thể chứ không phải một bảo đảm; một kích thước bảng khác, một key khác, hoặc một thread thứ hai thật sự đều có thể đổi kết quả, và đặc tả cho phép tất cả những khả năng đó.

Thêm hai điều nữa, đều lấy từ contract chứ không phải từ một cuộc đua. Iterator.remove() chạy được trên các view của ConcurrentHashMap và xoá thật khỏi map, khác với CopyOnWriteArrayList. Và không điều nào trong đây làm cho một thao tác ghép trở thành atomic: if (!map.containsKey(k)) map.put(k, v) vẫn là hai thao tác, và đó là lý do putIfAbsent cùng compute tồn tại.

Không có gì trong phần này được kiểm bằng race. Một race không lặp lại được theo yêu cầu, nên rút ra kết luận về concurrency từ một lần chạy là không trung thực. Mọi phát biểu ở trên về hành vi concurrent đều đến từ contract trong tài liệu; các output được trình bày là chương trình một thread tự sửa collection giữa các lời gọi trên chính iterator của nó, và như vậy đã đủ để lộ ra khác biệt về semantics.

Tự viết một Iterable

Contract nhỏ đến mức implement nó chẳng có gì đáng kể. Một class implement Iterable sẽ chạy được trong vòng lặp for nâng cao, vì đó đúng là tất cả những gì compiler yêu cầu trong đoạn bytecode ở trên:

import java.util.*;

class Countdown implements Iterable<Integer> {
    private final int from;

    Countdown(int from) { this.from = from; }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            private int n = from;

            @Override
            public boolean hasNext() { return n > 0; }

            @Override
            public Integer next() {
                if (!hasNext()) throw new NoSuchElementException("countdown finished");
                return n--;
            }
        };
    }
}

for (int n : new Countdown(4)) System.out.print(n + " ");
System.out.println();
new Countdown(3).forEach(n -> System.out.print("forEach " + n + "  "));

4 3 2 1
forEach 3  forEach 2  forEach 1

Hai method, không remove, không bộ đếm, và nó chạy được với cả for lẫn Iterable.forEach. Có ba việc đáng làm một cách có chủ ý:

• Ném NoSuchElementException từ next() khi đã hết, kèm message. Contract bắt buộc kiểu exception; message là của bạn.
• Trả về một iterator mới ở mỗi lần gọi iterator(). Trả về this từ một object cũng đang giữ cursor nghĩa là vòng lặp thứ hai trên cùng object đó sẽ thấy nó đã cạn.
• Đừng override remove trừ khi bạn thật sự muốn. Bản default kế thừa ném UnsupportedOperationException("remove"), và đó là câu trả lời trung thực cho một chuỗi được tính toán ra.

Iterator<Integer> r = new Countdown(3).iterator();
r.next();
r.remove();

Exception in thread "main" java.lang.UnsupportedOperationException: remove
	at java.base/java.util.Iterator.remove(Iterator.java:102)
	at CountdownRemove.main(CountdownRemove.java:33)

Nếu class của bạn bọc một collection có thể thay đổi và bạn muốn hành vi fail-fast, công thức chính là thứ AbstractList mô tả: giữ một field modCount, tăng nó trong mọi thao tác structural, chụp lại nó trong iterator, và so sánh trong next().

Quy tắc thực dụng

• Nghĩ tới removeIf trước tiên. Một lời gọi, diễn đạt đúng ý định, không thể bỏ sót phần tử, và chỉ chạm vào modCount một lần thay vì một lần cho mỗi phép xoá — removeIf trên list bốn phần tử đưa modCount từ 0 lên 1, trong khi hai lời gọi Iterator.remove() đưa nó lên 2.
• Nếu buộc phải dùng vòng lặp, hãy lấy iterator ra một cách tường minh. for (Iterator<String> it = list.iterator(); it.hasNext(); ) là dạng duy nhất cho bạn một cái tên để gọi object mà vòng lặp for nâng cao giấu đi.
• Không bao giờ structural modification một collection bạn đang duyệt, trừ khi thông qua chính iterator đó. Không add, không remove, không clear, và — ít rõ ràng hơn — không sort hay replaceAll.
• Dùng ListIterator khi cần thay thế hoặc chèn giữa vòng duyệt. set là công cụ đúng để cập nhật tại chỗ và nó thậm chí không phải structural modification.
• Đừng dựa vào ConcurrentModificationException để tìm những bug kiểu này. Theo đặc tả nó là best-effort, nó không nổ khi phép xoá làm hasNext() thành false, và cái vòng lặp thoát được đó đã lặng lẽ tạo ra một list sai.
• Chọn collection concurrent theo hình dạng đọc/ghi, đừng chọn vì nó tránh được exception. CopyOnWriteArrayList copy nguyên array mỗi lần ghi; đó là đánh đổi tốt cho một danh sách listener và tệ hại cho một hàng đợi.
• Ưu tiên stream hoặc removeIf thay cho vòng lặp biến đổi khi có thể. list.stream().filter(...).toList() tạo ra list mới và không hề chạm vào list gốc, tức là né hẳn toàn bộ câu chuyện này.

FAQ

Fail-fast và fail-safe iterator trong Java khác nhau thế nào?

Một fail-fast iterator đọc trên collection đang sống và ném ConcurrentModificationException khi nó phát hiện collection bị structural modification sau lưng mình — các collection trong java.util đều hoạt động như vậy. Một iterator "fail-safe" không bao giờ ném, vì nó không đọc cấu trúc đang sống theo cùng cách đó: CopyOnWriteArrayList duyệt trên một snapshot chụp lúc iterator được tạo, còn ConcurrentHashMap duyệt trên bảng đang sống với một bảo đảm yếu hơn. "Fail-safe" chỉ là tên gọi dân gian; Javadoc của JDK dùng "snapshot" và "weakly consistent", và chuỗi fail-safe không xuất hiện ở đâu trong source java.util hay java.util.concurrent.

Vì sao ConcurrentModificationException nhắc tới concurrency khi chỉ có một thread?

Vì "concurrent" ở đây nghĩa là "cùng lúc với một vòng duyệt đang diễn ra", chứ không phải "trên một thread khác". Một vòng lặp một thread xoá phần tử khỏi chính list nó đang duyệt là có hai thứ đụng vào list cùng lúc — iterator của vòng lặp và thân vòng lặp — và đó đúng là thứ phép kiểm tra này phát hiện. Stack trace nói rõ điều đó: frame ném ra là ArrayList$Itr.checkForComodification, được gọi từ ArrayList$Itr.next.

ConcurrentModificationException có thể bị bỏ sót không?

Có, và đây mới là phần quan trọng. Phép kiểm tra chỉ chạy bên trong next(). Nếu một structural modification làm hasNext() trả về false thì vòng lặp kết thúc trước khi phép kiểm tra kịp chạy. Xoá phần tử áp chót của một ArrayList trong vòng lặp for nâng cao trên ["a", "b", "c", "d"] sẽ duyệt ba phần tử, không ném gì, và bỏ qua hẳn "d". Javadoc ghi rằng hành vi fail-fast được cung cấp "on a best-effort basis" và chỉ nên dùng "only to detect bugs".

Structural modification là gì?

Bất cứ thứ gì làm đổi size của collection, hoặc sắp xếp lại và định hình lại nó theo cách khiến một vòng duyệt đang diễn ra trả về sai phần tử. add, remove, clear và addAll là structural; get và set(index, value) thì không. Ít rõ ràng hơn, sort và replaceAll là structural trên một ArrayList dù size không đổi, và cả hai đều làm một iterator đang sống ném exception.

Iterator và ListIterator khác nhau ở đâu?

Iterator chỉ đi tới và chỉ xoá được phần tử vừa trả về. ListIterator mở rộng thêm hasPrevious()/previous() để đi lui, nextIndex()/previousIndex() để biết vị trí, set(E) để thay phần tử vừa trả về, và add(E) để chèn tại cursor. ListIterator chỉ có trên List, vì đó là interface collection duy nhất có index mang ý nghĩa.

Sau ListIterator.add thì cursor nằm ở đâu?

Ngay sau phần tử bạn vừa chèn. Source JDK đặt cursor = i + 1, nên next() kế tiếp trả về phần tử vốn đứng sau điểm chèn chứ không phải phần tử mới — chính điều này ngăn một vòng lặp vừa duyệt vừa chèn chạy mãi không dừng. Cùng lời gọi đó đặt lastRet = -1, nên set và remove ngay sau một add đều ném IllegalStateException, và previous() mới là thứ trả về phần tử bạn vừa thêm.

CopyOnWriteArrayList có chậm hơn ArrayList không?

Với thao tác ghi thì đúng vậy về mặt cấu trúc: mỗi lời gọi biến đổi đều cấp phát một backing array mới và copy các phần tử hiện có sang. Một nghìn lần append tạo ra một nghìn array mới và 499.500 ô phần tử được copy, so với 13 array và 2.456 ô của ArrayList. Thao tác đọc thì không cần lock và không copy gì cả. Hình dạng đó — đọc concurrent rẻ, trả giá bằng ghi đắt — là lý do nó hợp với thứ như danh sách listener và không hợp với bất cứ thứ gì ghi nhiều.

Duyệt ConcurrentHashMap có thấy thay đổi xảy ra trong lúc duyệt không?

Có thể, và đặc tả từ chối hứa theo cả hai chiều. Bảo đảm được ghi trong tài liệu là iterator không bao giờ ném ConcurrentModificationException, duyệt đúng một lần mọi phần tử có mặt lúc nó được tạo, và "may (but is not guaranteed to) reflect any modifications subsequent to construction". Trong lần chạy một thread ở trên, một entry thêm vào sau khi iterator được tạo đã xuất hiện. Đừng xây logic dựa trên điều đó; nếu cần một view nhất quán thì hãy tự chụp lấy một cái.

Kết luận

Iteration trong Java là một cursor nằm giữa hai phần tử, cộng thêm hai field int ghi lại nó đang ở đâu và vừa trả về cái gì. Mọi thứ còn lại rơi ra từ đó: hasNext() là một phép so với size, remove() hợp lệ đúng khi lastRet khác -1, và vòng lặp for nâng cao chính là những lời gọi đó với iterator giấu trong một local slot mà bạn không gọi tên được. Fail-fast là một bộ đếm đem so với bản copy của chính nó, điều đó khiến nó rẻ, hữu ích, và — như trường hợp phần tử áp chót cho thấy trong ba dòng output thật — có thể trượt thật sự. Hãy coi nó là máy dò bug đôi khi dò trượt, dùng removeIf hoặc iterator tường minh, và chọn collection concurrent theo cách nó được ghi vào chứ không theo cái exception mà nó từ chối ném.

Bài 12 chuyển từ chuyện duyệt một collection sang chuyện sắp xếp nó: Comparable so với Comparator, "natural order" thật ra bắt một class phải hứa những gì, vì sao một comparator không nhất quán có thể làm sort ném exception, và cách xây custom sorting có thể ghép nối lại với nhau.