[Advanced Java] Class Collections trong Java: algorithm, wrapper và factory

java.util.Collections là một class có private constructor và bảy mươi mốt public static method, đếm bằng reflection trên JDK 21. Nó không final, nhưng private constructor khiến không ai khởi tạo hay kế thừa được: đây là một namespace, không phải một type. Gần như mọi tutorial đều trình bày nó dưới dạng một danh sách method xếp theo bảng chữ cái — đó là cách trình bày ít hữu ích nhất: danh sách quá dài để nhớ, và không hé lộ chút nào rằng các mục trong đó hành xử khác nhau hoàn toàn.

Trong class này chỉ có ba nhóm. Một số method là algorithm ghi đè lên chính list bạn truyền vào. Một số là wrapper trả về một object nhỏ đứng chắn trước collection của bạn. Một số là factory trả về một collection cố định của riêng nó. Việc một method thuộc nhóm nào quyết định nó sẽ mutate dữ liệu của bạn, alias dữ liệu của bạn, hay chẳng liên quan gì tới dữ liệu của bạn — và đó là cách phân loại duy nhất đáng mang theo.

Mọi chương trình, mọi dòng output và mọi exception dưới đây đều được compile và chạy thật trên OpenJDK 21.0.6 (arm64). Các đoạn Javadoc được trích nguyên văn từ src.zip đi kèm JDK đó.

Ba nhóm thật sự nằm trong java.util.Collections

Hàng gây bug thật sự là hàng thứ ba. Wrapper không phải bản copy và cũng không phải một collection mới; nó là một object nhỏ giữ đúng một reference tới collection của bạn và forward mọi lời gọi. Mọi thứ bất ngờ ở Collections đều suy ra từ việc hiểu câu đó theo nghĩa đen.

Algorithms: những method ghi đè lên list của bạn

Chúng nhận một List và không trả về gì. Không có kết quả để gán, vì kết quả chính là cái list bạn vừa truyền vào.

import java.util.*;

public class Algos {
    public static void main(String[] args) {
        List<Integer> l = new ArrayList<>(List.of(5, 3, 9, 1, 7, 4));
        System.out.println("start           " + l);
        Collections.sort(l);
        System.out.println("sort(l)         " + l);
        Collections.reverse(l);
        System.out.println("reverse(l)      " + l);
        Collections.rotate(l, 2);
        System.out.println("rotate(l, 2)    " + l);
        Collections.swap(l, 0, 5);
        System.out.println("swap(l, 0, 5)   " + l);
        Collections.shuffle(l, new Random(42));
        System.out.println("shuffle(l, r42) " + l);
        Collections.replaceAll(l, 9, 0);
        System.out.println("replaceAll 9->0 " + l);
        System.out.println("min / max       " + Collections.min(l) + " / " + Collections.max(l));

        List<String> words = new ArrayList<>(List.of("ant", "buffalo", "cow", "eel"));
        System.out.println("max by length   "
                + Collections.max(words, Comparator.comparingInt(String::length)));

        List<String> tags = new ArrayList<>(List.of("red", "blue", "red", "green", "red"));
        System.out.println("frequency red   " + Collections.frequency(tags, "red"));
        System.out.println("disjoint bw     " + Collections.disjoint(tags, List.of("black", "white")));
        System.out.println("disjoint br     " + Collections.disjoint(tags, List.of("black", "red")));

        List<String> sink = new ArrayList<>();
        Collections.addAll(sink, "x", "y", "z");
        System.out.println("addAll          " + sink);
        Collections.fill(sink, "-");
        System.out.println("fill            " + sink);
        System.out.println("nCopies(4, ab)  " + Collections.nCopies(4, "ab"));
    }
}

start           [5, 3, 9, 1, 7, 4]
sort(l)         [1, 3, 4, 5, 7, 9]
reverse(l)      [9, 7, 5, 4, 3, 1]
rotate(l, 2)    [3, 1, 9, 7, 5, 4]
swap(l, 0, 5)   [4, 1, 9, 7, 5, 3]
shuffle(l, r42) [1, 4, 5, 3, 7, 9]
replaceAll 9->0 [1, 4, 5, 3, 7, 0]
min / max       0 / 7
max by length   buffalo
frequency red   3
disjoint bw     true
disjoint br     false
addAll          [x, y, z]
fill            [-, -, -]
nCopies(4, ab)  [ab, ab, ab, ab]

shuffle(l, new Random(42)) là overload hai tham số. Bản một tham số dùng một nguồn ngẫu nhiên dùng chung bên trong nên không lặp lại được; truyền vào một Random có seed chính là thứ khiến một ví dụ shuffle có thể kiểm chứng.

Chi phí của từng method là số phép toán trên phần tử, không phải con số đồng hồ bấm giây, và những con số này đọc thẳng ra từ implementation:

Hai method trong bảng khó đoán hơn vẻ ngoài. rotate trên list truy cập theo index không phải là ba lần reverse; rotate1 đi theo các chu trình hoán vị và dừng khi nMoved bằng size, nên mỗi phần tử được ghi đúng một lần. Còn disjoint tự chọn bên nào để duyệt: nếu một trong hai tham số là Set thì nó gọi contains trên Set đó, còn nếu cả hai đều không phải, nó duyệt collection nhỏ hơn. Truyền collection lớn vào trước không phải là lỗi, vì method tự sắp xếp lại phần việc.

sort, min, max và binarySearch đều có overload thứ hai nhận Comparator — đó là lý do Collections.max(words, Comparator.comparingInt(String::length)) trả về buffalo ở trên. Cách dựng comparator là chủ đề của bài trước trong khoá này; ở đây chúng chỉ là tham số.

binarySearch trả về insertion point khi không tìm thấy key

Đa số người viết if (index >= 0) rồi vứt hết phần còn lại. Javadoc nói rất rõ rằng nhánh âm cũng mang thông tin:

@return the index of the search key, if it is contained in the list;
        otherwise, (-(insertion point) - 1).  The
        insertion point is defined as the point at which the
        key would be inserted into the list: the index of the first
        element greater than the key, or list.size() if all
        elements in the list are less than the specified key.  Note
        that this guarantees that the return value will be >= 0 if
        and only if the key is found.

Chạy thử trên một list đã sorted là đọc ra ngay cách mã hoá:

List<String> sorted = new ArrayList<>(List.of("ant", "bee", "cow", "eel"));
System.out.println("list " + sorted);
for (String probe : List.of("ant", "eel", "dog", "aardvark", "zebra")) {
    int r = Collections.binarySearch(sorted, probe);
    System.out.println("binarySearch(\"" + probe + "\") = " + r + "   "
            + (r >= 0 ? "found at index " + r
                      : "absent, insertion point " + (-r - 1)));
}

list [ant, bee, cow, eel]
binarySearch("ant") = 0   found at index 0
binarySearch("eel") = 3   found at index 3
binarySearch("dog") = -4   absent, insertion point 3
binarySearch("aardvark") = -1   absent, insertion point 0
binarySearch("zebra") = -5   absent, insertion point 4

-1 chính là lý do cách mã hoá không đơn giản là -insertionPoint: nếu vậy thì index 0 và "sẽ nằm vào index 0" đều ra số không. Việc lệch đi một đơn vị mua được đúng lời bảo đảm ở câu cuối của Javadoc.

Con số đó đáng giữ lại, vì nó đúng bằng tham số cho add. Từ đó rơi ra hai tiện ích, mỗi cái ba dòng:

/** Inserts value and keeps the list sorted. Returns false if it was already there. */
static <T extends Comparable<? super T>> boolean insertSorted(List<T> list, T value) {
    int i = Collections.binarySearch(list, value);
    if (i >= 0) return false;
    list.add(-i - 1, value);
    return true;
}

/** Number of elements strictly less than key, for a list sorted ascending. */
static <T extends Comparable<? super T>> int countBelow(List<T> list, T key) {
    int i = Collections.binarySearch(list, key);
    return i >= 0 ? i : -i - 1;
}

public static void main(String[] args) {
    List<String> log = new ArrayList<>(List.of("09:00", "10:30", "13:15"));
    for (String t : List.of("11:45", "08:15", "23:59", "10:30")) {
        System.out.println("insert " + t + " -> " + insertSorted(log, t) + "  " + log);
    }
    System.out.println("entries before 11:00 : " + countBelow(log, "11:00"));
    System.out.println("entries before 09:00 : " + countBelow(log, "09:00"));
}

insert 11:45 -> true  [09:00, 10:30, 11:45, 13:15]
insert 08:15 -> true  [08:15, 09:00, 10:30, 11:45, 13:15]
insert 23:59 -> true  [08:15, 09:00, 10:30, 11:45, 13:15, 23:59]
insert 10:30 -> false  [08:15, 09:00, 10:30, 11:45, 13:15, 23:59]
entries before 11:00 : 3
entries before 09:00 : 1

insertSorted giữ list luôn sorted với log2(n) lần so sánh cộng một lần dịch phần tử cho mỗi lần chèn, thay vì cứ nối vào cuối rồi sort lại toàn bộ. countBelow trả lời một câu hỏi dạng khoảng mà không cần vòng lặp nào. Cả hai chỉ là một dòng số học trên cái giá trị trả về mà phần lớn code ném đi.

Algorithm nào chạy phụ thuộc vào RandomAccess

Nhiều method trong số này có một phép kiểm tra instanceof RandomAccess để chọn giữa implementation chạy theo index và implementation chạy theo iterator, mỗi cái kèm một ngưỡng kích thước mà dưới ngưỡng đó nhánh index vẫn được chọn. Một bài trước trong khoá này đã đo thẳng nhánh rẽ đó: bọc cùng một tập phần tử vào hai delegating list có thân class giống hệt nhau, chỉ khác đúng marker interface, rồi đếm số lần JDK gọi get, set và listIterator trên từng cái. Hai đường đi hoá ra là hai algorithm thật sự khác nhau, không phải một tối ưu vặt.

Hệ quả cho bài này thì nhỏ nhưng cần nói ra: các con số trong bảng ở trên mô tả nhánh index. Đưa cho Collections.shuffle một LinkedList đủ lớn để vượt ngưỡng, JDK sẽ copy nó ra array, shuffle trên array rồi ghi ngược lại qua ListIterator, đúng để khỏi phải đi bộ trên linked list mười nghìn lần. Bạn không phải làm gì để có hành vi đó; bạn chỉ cần biết là method được phép làm vậy.

nCopies trả về một object lặp n lần, không phải n object

Javadoc nói rõ nó trả về gì, và cái ngoặc đơn mới là toàn bộ câu chuyện:

Returns an immutable list consisting of n copies of the
specified object.  The newly allocated data object is tiny (it contains
a single reference to the data object).  This method is useful in
combination with the List.addAll method to grow lists.

"A single reference to the data object" nghĩa là list đó không có n phần tử. Nó có một phần tử, được báo cáo n lần. So sánh identity là xong:

List<StringBuilder> four = Collections.nCopies(4, new StringBuilder("row"));
System.out.println("list              " + four);
System.out.println("size              " + four.size());
System.out.println("class             " + four.getClass().getName());
System.out.println("get(0) == get(1)  " + (four.get(0) == four.get(1)));
System.out.println("get(0) == get(3)  " + (four.get(0) == four.get(3)));

four.get(0).append("!");
System.out.println("after append      " + four);

List<StringBuilder> real = new ArrayList<>();
for (int i = 0; i < 4; i++) real.add(new StringBuilder("row"));
System.out.println("real get(0)==(1)  " + (real.get(0) == real.get(1)));

List<String> padded = new ArrayList<>(List.of("a"));
padded.addAll(Collections.nCopies(3, ""));
System.out.println("padded            " + padded + "  size " + padded.size());

list              [row, row, row, row]
size              4
class             java.util.Collections$CopiesList
get(0) == get(1)  true
get(0) == get(3)  true
after append      [row!, row!, row!, row!]
real get(0)==(1)  false
padded            [a, , , ]  size 4

Sửa "một" phần tử làm cả bốn đổi theo, vì chỉ có đúng một phần tử. Với phần tử immutable — String, Integer, một giá trị đánh dấu rỗng — đó là ưu điểm, và list.addAll(Collections.nCopies(3, "")) chèn ba ô trống mà không cấp phát gì cho từng ô. Với phần tử mutable thì đó là một bug chia sẻ state, chỉ chờ bị phát hiện ở một chỗ hoàn toàn khác.

⚠️ Collections.nCopies(n, new StringBuilder()) không cho bạn n builder. Nó cho bạn một builder, n lần. Nếu phần tử là mutable, hãy dựng list bằng vòng lặp.

Wrapper là view, không phải bản copy

unmodifiableXxx, synchronizedXxx và checkedXxx là cùng một kiến trúc lặp lại ba lần: một object nhỏ giữ đúng một reference tới collection của bạn, chặn đường ghi và forward mọi thứ còn lại.

Một lần ghi qua reference gốc là đủ chứng minh, vì cả ba đều báo cáo lại nó:

List<String> backing = new ArrayList<>(List.of("a", "b"));
List<String> unmod = Collections.unmodifiableList(backing);
List<String> sync  = Collections.synchronizedList(backing);
List<String> chk   = Collections.checkedList(backing, String.class);

System.out.println("before  backing=" + backing + "  unmodifiable=" + unmod
        + "  synchronized=" + sync + "  checked=" + chk);
backing.add("c");
System.out.println("after   backing=" + backing + "  unmodifiable=" + unmod
        + "  synchronized=" + sync + "  checked=" + chk);
System.out.println("unmodifiable class    " + unmod.getClass().getName());
System.out.println("synchronized class    " + sync.getClass().getName());
System.out.println("checked class         " + chk.getClass().getName());
System.out.println("synchronized.iterator " + sync.iterator().getClass().getName());

before  backing=[a, b]  unmodifiable=[a, b]  synchronized=[a, b]  checked=[a, b]
after   backing=[a, b, c]  unmodifiable=[a, b, c]  synchronized=[a, b, c]  checked=[a, b, c]
unmodifiable class    java.util.Collections$UnmodifiableRandomAccessList
synchronized class    java.util.Collections$SynchronizedRandomAccessList
checked class         java.util.Collections$CheckedRandomAccessList
synchronized.iterator java.util.ArrayList$Itr

Ba inner class, một list. Để ý dòng cuối trước khi đi tiếp — nó là toàn bộ nội dung của mục sau nữa.

unmodifiableList chặn caller, không chặn owner

Bài 1 của khoá này đã chứng minh hệ quả trong bối cảnh encapsulation: Collections.unmodifiableList trả về một live view luôn bám theo mọi lần ghi của owner, còn List.copyOf trả về một snapshot thì không. Dòng after ở trên là đúng sự thật đó nhìn từ phía ngược lại — không ai đụng vào unmod, mà unmod vẫn đổi.

Điều đáng bổ sung ở đây là wrapper này idempotent trên JDK hiện đại, chỗ mà nhiều bài viết cũ nói sai. Javadoc có một @implNote ghi "This method may return its argument if the argument is already unmodifiable", và thân method mở đầu đúng bằng một phép kiểm tra class — có mặt trong cả source JDK 17 lẫn JDK 21 cài trên máy này. synchronizedList không có phép kiểm tra đó. Chạy cả hai thì xác nhận:

unmodifiable.add("d") threw java.lang.UnsupportedOperationException
unmodifiableList(unmodifiable) == unmodifiable  true
synchronizedList(synchronized) == synchronized  false

Vậy bọc một list vốn đã unmodifiable thêm lần nữa thì không tốn gì, còn bọc một synchronized list thêm lần nữa thì thật sự cấp phát một wrapper thứ hai khoá trên một object khác với cái đầu. Hãy bọc đúng một lần, ngay tại biên.

synchronizedList không bao vòng lặp của bạn

Mọi method trên một synchronizedList đều được canh khoá. Vòng lặp thì không phải là một method. Javadoc nói thẳng bất thường:

It is imperative that the user manually synchronize on the returned
list when traversing it via Iterator, Spliterator or Stream:

 List list = Collections.synchronizedList(new ArrayList());
     ...
 synchronized (list) {
     Iterator i = list.iterator(); // Must be in synchronized block
     while (i.hasNext())
         foo(i.next());
 }

Failure to follow this advice may result in non-deterministic behavior.

Lý do nằm ngay trong output ở trên: sync.iterator() trả về java.util.ArrayList$Itr, tức iterator của chính list bên dưới, bên trong không có một chỗ khoá nào. iterator() thì synchronized; cái object nó trả ra thì không. Hai thread, một bên nối thêm và một bên duyệt, biến khác biệt đó thành một con số đếm được:

List<Integer> list = Collections.synchronizedList(new ArrayList<>());
for (int i = 0; i < 500; i++) list.add(i);

Thread writer = new Thread(() -> { for (int i = 0; i < 2000; i++) list.add(i); });
Thread reader = new Thread(() -> {
    long s = 0;
    for (int v : list) s += v;        // every call locks; the loop does not
});

Chạy cặp thread đó 200 lượt, rồi chạy lại cũng cặp đó nhưng bọc vòng lặp của reader trong synchronized (list):

rounds                               200
for (int v : list)      failures     158
synchronized (list) { ... } failures 0

Con số đáng chú ý là con số thứ hai. Con số thứ nhất thay đổi giữa các lần chạy vì phụ thuộc vào cách hai thread đan nhau; con số thứ hai bằng không vì khối lệnh biến cả lượt duyệt thành một critical section. Khoá theo từng lời gọi không bao giờ bao được một chuỗi lời gọi — cũng chính là lý do một synchronizedMap không diễn đạt nổi thao tác "get, nếu chưa có thì put" một cách an toàn.

checkedList làm heap pollution nổ ngay tại chỗ insert

Đây là wrapper ít được dùng nhất và cũng là cái có lợi ích rõ nhất. Generic bị erase, nên một unchecked cast hoặc một raw type có thể thả một Integer vào List<String> mà compiler chỉ cảnh báo:

warning: [unchecked] unchecked call to add(E) as a member of the raw type List
        raw.add(value);
               ^

Nếu bạn bỏ qua cảnh báo đó thì chẳng có gì xảy ra — cho tới khi có chỗ nào đó đọc phần tử ra và cast do compiler chèn vào bị fail, ở một nơi cách xa tuỳ ý so với chỗ insert. Javadoc của checkedCollection gọi tên đúng kịch bản này:

Another use of dynamically typesafe views is debugging.  Suppose a
program fails with a ClassCastException, indicating that an
incorrectly typed element was put into a parameterized collection.
Unfortunately, the exception can occur at any time after the erroneous
element is inserted, so it typically provides little or no information
as to the real source of the problem.  If the problem is reproducible,
one can quickly determine its source by temporarily modifying the
program to wrap the collection with a dynamically typesafe view.

Cùng một thao tác insert, một lần vào list thường và một lần vào checked list:

@SuppressWarnings({"unchecked", "rawtypes"})
static void pollute(List raw, Object value) {
    raw.add(value);                       // unchecked call, compiles with a warning
}

public static void main(String[] args) {
    List<String> plain = new ArrayList<>();
    plain.add("ok");
    pollute(plain, 42);                   // an Integer into a List<String>
    System.out.println("plain list accepted it : " + plain);
    try {
        String s = plain.get(1);          // the failure lands here, far from the cause
        System.out.println(s);
    } catch (ClassCastException e) {
        System.out.println("reading it threw       : " + e.getMessage());
    }

    List<String> checked = Collections.checkedList(new ArrayList<>(), String.class);
    checked.add("ok");
    try {
        pollute(checked, 42);
    } catch (ClassCastException e) {
        System.out.println("checked add threw      : " + e.getMessage());
    }
    System.out.println("checked list unchanged : " + checked);
}

plain list accepted it : [ok, 42]
reading it threw       : class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
checked add threw      : Attempt to insert class java.lang.Integer element into collection with element type class java.lang.String
checked list unchanged : [ok]

So hai thông báo với nhau. Cái đầu nêu tên hai class cùng một class loader và không nói gì về nguồn gốc của giá trị sai; stack trace chỉ vào chỗ đọc. Cái sau nêu đúng phần tử phạm lỗi, nêu element type của collection, và ném ngay tại frame add — tức dòng thật sự sai. Checked list cũng giữ nguyên sạch sẽ, nên chương trình chạy tiếp được.

Cái giá phải trả là một lần isInstance cho mỗi lần insert. Rẻ đủ để bật vĩnh viễn cho một collection bạn đưa cho code bạn không kiểm soát, và rẻ đủ để bật tạm khi một ClassCastException xuất hiện ở nơi không thể nào sinh ra nó.

Immutable factory và unmodifiable wrapper khác nhau ở đâu?

Collections có sẵn các factory tạo collection cố định từ trước List.of hai thập kỷ. Chúng vẫn còn đó, hành xử khác nhau, và khác biệt lộ ra ngay bằng ==.

System.out.println("emptyList() == emptyList()      " + (Collections.emptyList() == Collections.emptyList()));
System.out.println("List.of()   == List.of()        " + (List.of() == List.of()));
System.out.println("emptyList() == List.of()        " + (Collections.emptyList() == List.of()));
System.out.println("emptyList class                 " + Collections.emptyList().getClass().getName());
System.out.println("List.of()  class                " + List.of().getClass().getName());
System.out.println("singletonList class             " + Collections.singletonList("a").getClass().getName());
System.out.println("List.of(\"a\") class              " + List.of("a").getClass().getName());
System.out.println("singletonList == singletonList  "
        + (Collections.singletonList("a") == Collections.singletonList("a")));

List<String> viaArrays = Arrays.asList("a", null, "c");
System.out.println("Arrays.asList with null         " + viaArrays);
try {
    List.of("a", null, "c");
} catch (NullPointerException e) {
    System.out.println("List.of with null threw         " + e.getClass().getName());
}
System.out.println("new ArrayList<>().contains(null) " + new ArrayList<>(viaArrays).contains(null));
try {
    System.out.println(List.of("a").contains(null));
} catch (NullPointerException e) {
    System.out.println("List.of(\"a\").contains(null) threw " + e.getClass().getName());
}

List<String> mutable   = new ArrayList<>(List.of("a", "b"));
List<String> immutable = List.of("a", "b");
List<String> unmodView = Collections.unmodifiableList(mutable);
System.out.println("copyOf(ArrayList)  == source    " + (List.copyOf(mutable) == mutable));
System.out.println("copyOf(List.of)    == source    " + (List.copyOf(immutable) == immutable));
System.out.println("copyOf(unmod view) == source    " + (List.copyOf(unmodView) == unmodView));

List<String> snap = List.copyOf(mutable);
mutable.add("c");
System.out.println("owner mutated: view=" + unmodView + "  copyOf snapshot=" + snap);

emptyList là singleton, singletonList thì không

emptyList() == emptyList()      true
List.of()   == List.of()        true
emptyList() == List.of()        false
emptyList class                 java.util.Collections$EmptyList
List.of()  class                java.util.ImmutableCollections$ListN
singletonList class             java.util.Collections$SingletonList
List.of("a") class              java.util.ImmutableCollections$List12
singletonList == singletonList  false

Collections.emptyList() trả về cùng một instance ở mọi lời gọi — trong JVM chỉ có một EmptyList và nó được phát cho tất cả mọi người, an toàn chính vì nó không bao giờ đổi được. List.of() cũng làm y hệt nhưng với một singleton khác, nên hai cái bằng nhau theo equals và khác nhau theo ==. Đừng bao giờ viết == giữa hai collection trong code thật; ở đây nó chỉ dùng để lộ ra identity.

singletonList cấp phát một object mới mỗi lần gọi. Nó nhỏ hơn List.of("a") về ý định chứ không về identity, tức là không có cache nào ở đây cả.

List.of từ chối null còn Arrays.asList thì nhận

Arrays.asList with null         [a, null, c]
List.of with null threw         java.lang.NullPointerException
new ArrayList<>().contains(null) true
List.of("a").contains(null) threw java.lang.NullPointerException

Bộ immutable collection ra mắt ở Java 9 được thiết kế để bài trừ null, và sự bài trừ đó không dừng ở lúc khởi tạo. Arrays.asList vui vẻ dựng một list có null ở giữa, và một ArrayList copy từ nó trả lời contains(null) là true. List.of từ chối ngay lúc dựng, còn List.of("a").contains(null) không trả lời false — nó ném exception. Code chuyển từ Arrays.asList sang List.of mà lỡ dò bằng một giá trị có thể null sẽ nhận NullPointerException từ một truy vấn chỉ đọc, một chỗ rất bất ngờ để gặp nó.

List.copyOf có thể không copy gì cả

copyOf(ArrayList)  == source    false
copyOf(List.of)    == source    true
copyOf(unmod view) == source    false
owner mutated: view=[a, b, c]  copyOf snapshot=[a, b]

List.copyOf của một ArrayList thì copy thật. List.copyOf của một list vốn đã là một trong các implementation immutable từ Java 9 thì trả về đúng object đó, vì copy một thứ không thể đổi là lãng phí thuần tuý. List.copyOf của một wrapper Collections.unmodifiableList thì có copy, và buộc phải copy: wrapper là unmodifiable qua cái handle đó, nhưng list nằm sau nó thì không — điều mà dòng cuối cho thấy trong cùng một lần chạy.

Dòng cuối đó chính là tóm tắt của cả mục này. View và snapshot được lấy tại cùng một thời điểm; chỉ một trong hai xê dịch.

Cái gì đã lỗi thời, và cái gì vẫn đáng dùng

Vài method ở đây già hơn thứ thay thế chúng và ở lại chỉ vì tương thích ngược. Collections.sort là trường hợp rõ nhất — từ Java 8 nó chỉ là một dòng chuyển tiếp:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

Đó là toàn bộ thân method trong JDK 21. Override sort trên một list subclass là thấy ngay việc chuyển tiếp diễn ra lúc runtime:

static class Loud<E> extends ArrayList<E> {
    Loud(Collection<? extends E> c) { super(c); }
    @Override public void sort(Comparator<? super E> c) {
        System.out.println("  Loud.sort(" + (c == null ? "null" : "comparator") + ") called");
        super.sort(c);
    }
}

Collections.sort(list):
  Loud.sort(null) called
  result [1, 2, 3]

Arrays.asList là cái còn lại mà nhiều người dùng theo thói quen. Nó là một view kích thước cố định trên chính array bạn truyền vào, không phải một list của riêng nó:

List<String> fixed = Arrays.asList("a", "b", "c");
System.out.println("Arrays.asList class    " + fixed.getClass().getName());
fixed.set(0, "z");
System.out.println("set(0, \"z\") ok         " + fixed);
try {
    fixed.add("d");
} catch (UnsupportedOperationException e) {
    System.out.println("add threw              " + e.getClass().getName());
}

String[] src = { "a", "b" };
List<String> viewOfArray = Arrays.asList(src);
viewOfArray.set(1, "CHANGED");
System.out.println("array after set        " + Arrays.toString(src));

Arrays.asList class    java.util.Arrays$ArrayList
set(0, "z") ok         [z, b, c]
add threw              java.lang.UnsupportedOperationException
array after set        [a, CHANGED]

set ghi xuyên qua vào array gốc. add ném exception vì array không nở ra được. Nó là một wrapper mang cái tên của một factory.

Những cái đáng giữ thì dễ gọi tên. binarySearch trên một List đã sorted, vì chưa có gì thay thế. nCopies, frequency và disjoint, vì viết tay ra thì dài hơn mà chẳng rõ hơn. unmodifiableXxx khi một live view đúng là điều API muốn nói. checkedXxx, vừa như một công cụ debug vừa như một chốt chặn cho collection đi qua ranh giới tin cậy. Và emptyList, vì nó không cấp phát gì.

Những cái tôi sẽ không viết lại là Collections.sort khi list.sort nằm ngay đó, synchronizedMap khi đã có ConcurrentHashMap, và unmodifiableList(new ArrayList<>(x)) khi List.copyOf(x) nói cùng một điều bằng một object và một lời gọi.

Câu hỏi thường gặp

Collections có phải là Collection không?

Không, và cái tên gần trùng nhau này khá phiền. java.util.Collection là interface gốc mà List, Set và Queue implement. java.util.Collections là một utility class không khởi tạo được, chỉ chứa các static method thao tác trên chúng. Một bên là type bạn implement, bên kia là hộp đồ nghề bạn gọi.

Vì sao các algorithm trả về void thay vì một list mới?

Chúng được thiết kế từ Java 2 để mutate tại chỗ, khi ngôn ngữ chưa có gì tốt hơn. Thứ tương đương hiện đại thì trả về collection mới và nằm ở chỗ khác: list.sort vẫn mutate, nhưng một stream pipeline collect ra list mới thì không đụng tới nguồn. Nếu cần giữ nguyên bản gốc, hãy copy trước rồi sort trên bản copy.

Collections.unmodifiableList có làm list của tôi thread-safe không?

Không. Nó chỉ chặn việc ghi qua đúng cái handle đó. Owner vẫn có thể mutate list bên dưới từ một thread khác, và người đọc đang duyệt view sẽ nhận ConcurrentModificationException vì một lần ghi không phải của mình. Unmodifiable nói về quyền, không nói về memory visibility hay tính nguyên tử.

Khi nào nên dùng checkedList thay vì đi sửa cảnh báo?

Sửa cảnh báo khi bạn nhìn thấy nó. checkedList dành cho những trường hợp bạn không nhìn thấy: một collection được đưa cho library, một codebase mà unchecked cast nằm trong code bạn không sở hữu, hoặc một ClassCastException trên production có stack trace chỉ vào chỗ đọc chứ không phải chỗ insert đã gây ra nó. Bọc collection lại là biến trường hợp thứ hai thành trường hợp thứ ba.

binarySearch có nhanh hơn contains trên list nhỏ không?

Không hẳn, và so như vậy là so sai chỗ. binarySearch đòi list phải sorted, mà giữ cho nó sorted thì tốn chi phí ở mỗi lần chèn. Trên một list vốn đã sorted vì lý do khác, đó là log2(n) lần so sánh so với n. Trên một list mà bạn phải sort trước, contains thắng cho tới khi bạn tìm nhiều lần cho mỗi lần sort.

Kết luận

java.util.Collections thôi là một danh sách tên method ngay khi bạn xếp nội dung của nó vào ba nhóm: algorithm ghi đè dữ liệu của bạn, wrapper alias dữ liệu của bạn, và factory thay thế dữ liệu của bạn. Các algorithm trả về void vì kết quả chính là tham số. Wrapper là một object giữ một reference, và đó là lý do một unmodifiable view vẫn đổi liên tục còn một synchronized list vẫn cần khối lệnh của chính bạn bao quanh vòng lặp. Factory trả về một thứ cố định, và List.of cùng List.copyOf đã lặng lẽ làm phân nửa số factory cũ trở nên thừa. Hai chi tiết đáng mang theo nguyên vẹn là insertion point của binarySearch, thứ biến một số âm bị vứt đi thành một lần chèn giữ sorted, và checkedList, thứ dời ClassCastException từ chỗ đọc phải hứng chịu về đúng chỗ insert đã gây ra nó.

Đến đây là hết Phần 2 của khoá này. Phần 1 và Phần 2 đã đi qua ngôn ngữ và collections framework — những hình hài mà dữ liệu của bạn nằm trong đó, cùng bộ công cụ thao tác trên chúng. Phần 3 mở đầu bằng Stream API, thứ lấy chính những collection đó và thay vòng lặp bằng một pipeline: filter, map, reduce, tính lười, và thời điểm một stream thật sự chạy.