Tổng quan Collections Framework

Hầu như chương trình nào cũng phải gom giữ và xử lý nhiều phần tử cùng loại: danh sách sinh viên, hàng chờ in, tập từ khoá đã gặp, bảng tra giá theo mã hàng. Mảng làm được việc này nhưng cứng nhắc: kích thước cố định, thiếu sẵn các thao tác thêm, xoá, tìm. Java cung cấp một bộ thư viện thống nhất gọi là Bộ khung tập hợp (Collections Framework), gồm các giao tiếp mô tả hành vi và nhiều lớp cài đặt với đặc tính hiệu năng khác nhau. Học chương này không phải để thuộc lòng tên lớp, mà để biết với mỗi tình huống thì chọn cấu trúc nào cho vừa đúng vừa nhanh.

Hãy hình dung một phần mềm quản lý thư viện. Ta cần giữ danh sách đầu sách theo thứ tự nhập kho, cần một tập mã thẻ độc giả không được trùng, cần hàng chờ mượn sách theo thứ tự đăng ký, và cần tra nhanh thông tin độc giả theo mã thẻ. Bốn nhu cầu này ứng với bốn nhóm cấu trúc khác nhau trong bộ khung. Chọn sai nhóm thì mã vẫn chạy nhưng chậm hoặc rối, còn chọn đúng nhóm thì thao tác gọn và nhanh. Vì thế phần còn lại của chương xoay quanh một câu hỏi duy nhất: dữ liệu của tôi cần thao tác gì nhiều nhất, rồi từ đó chọn lớp cài đặt hợp với thao tác đó.

Trước khi có bộ khung, mỗi thư viện tự dựng lấy một kiểu chứa riêng, tên phương thức mỗi nơi một khác, và mã của ta phải học lại từ đầu mỗi lần đổi thư viện. Bộ khung tập hợp giải quyết chuyện đó bằng cách tách bạch ba tầng. Tầng trên cùng là các giao tiếp mô tả hành vi, chỉ nói cấu trúc này làm được gì mà không nói làm bằng cách nào. Tầng giữa là các lớp cài đặt thực hiện hành vi ấy bằng một cấu trúc dữ liệu cụ thể, mỗi lớp có một hồ sơ hiệu năng riêng. Tầng dưới cùng là các thuật toán dùng chung, đặt trong lớp tiện ích Collections và trong các phương thức mặc định của giao tiếp, ví dụ sắp xếp, đảo ngược, tìm nhị phân. Nhờ ba tầng này, một thuật toán viết cho List chạy được với mọi lớp cài đặt List, kể cả lớp do ta tự viết sau này.

Có một điểm khác biệt nữa đáng nói ngay từ đầu, đó là mảng và tập hợp không thay thế lẫn nhau hoàn toàn. Mảng có kích thước cố định lúc tạo, biết kiểu phần tử ngay lúc chạy, và chứa được kiểu nguyên thuỷ mà không tốn chi phí đóng gói. Tập hợp thì co giãn được, mang sẵn hàng chục thao tác, nhưng chỉ chứa kiểu tham chiếu. Khi số phần tử biết trước và không đổi, lại toàn số nguyên thuỷ, mảng vẫn là lựa chọn hợp lý. Ngoài trường hợp đó, tập hợp gần như luôn thắng vì mã ngắn hơn, ít lỗi hơn và diễn đạt được ý định rõ hơn.

Quy ước về độ phức tạp

Trong các bài này độ phức tạp được viết bằng ký hiệu Big-O, ví dụ O(1), O(n), O(log n). Đó là chi phí trung bình của thao tác khi số phần tử tăng lên.

Thử ngay: xem một tập hợp được duyệt chạy từng bước

Chưa cần đọc hết lý thuyết, hãy bấm ▶ Chạy (hoặc kéo thanh trượt) để xem một danh sách được duyệt qua từng phần tử và thấy vòng lặp for-each thật ra làm gì bên dưới: nó xin một Iterator, rồi mỗi vòng gọi next() để lấy phần tử kế tiếp và đẩy con trỏ (cursor) tiến một bậc, cho tới khi hasNext() trả về false. Phần dưới sẽ giải thích chỗ đứng của Iterator trong bộ khung.

Iterator duyệt qua từng phần tử của một List java

1import java.util.ArrayList;
2import java.util.Iterator;
3import java.util.List;
4
5public class Demo {
6    public static void main(String[] args) {
7        List<String> ten = new ArrayList<>(List.of("An", "Binh", "Cuong"));
8        Iterator<String> it = ten.iterator();
9        while (it.hasNext()) {
10            String s = it.next();
11            System.out.println(s);
12        }
13    }
14}

Ngăn xếp stack

main()

ten→ #1

Bộ nhớ động heap

#1ArrayList

[0]An

[1]Binh

[2]Cuong

Tạo một danh sách ba tên. Đối tượng ArrayList nằm trên bộ nhớ động, mỗi ô mang một chỉ số.

1/9

Hai nhánh lớn của bộ khung

Toàn bộ khung chia thành hai nhánh lớn không cùng gốc.

Nhánh thứ nhất bắt đầu từ giao tiếp Collection, mô tả một nhóm phần tử đơn lẻ. List, Set và Queue đều thừa kế từ đây.
Nhánh thứ hai là Map, mô tả ánh xạ từ khoá sang giá trị. Map không thừa kế Collection vì bản chất của nó là cặp khoá-giá trị chứ không phải phần tử đơn.

Đây là điểm hay nhầm: ta nói Map thuộc Bộ khung tập hợp nhưng nó không phải là một Collection. Nhờ tách giao tiếp khỏi cài đặt, ta lập trình theo giao tiếp và có thể thay lớp cài đặt mà ít phải sửa mã.

Đọc cây phân cấp cho kỹ

Đỉnh của nhánh thứ nhất không phải Collection mà là Iterable. Giao tiếp này bé tới mức gần như chỉ có một phương thức, đó là iterator(). Nó nói lên một điều duy nhất và rất khiêm tốn: thứ này duyệt qua được từng phần tử. Đặt nó lên đỉnh là một quyết định thiết kế có chủ ý, vì nhờ vậy vòng lặp for-each không cần biết gì về Collection cả, nó chỉ cần đối tượng bên phải dấu hai chấm là một Iterable. Đó là lý do mảng và mọi tập hợp đều for-each được, còn một lớp do ta tự viết cũng lập tức for-each được nếu ta cho nó cài Iterable.

Xuống một bậc là Collection, nơi bổ sung những gì thực sự làm nên một nhóm phần tử: add, remove, contains, size, isEmpty, clear, cùng các phép toán trên cả tập như addAll và removeAll. Mọi cấu trúc chứa phần tử đơn trong bộ khung đều nằm dưới giao tiếp này, nên một phương thức nhận tham số kiểu Collection<String> sẽ nhận được cả ArrayList, cả HashSet, cả ArrayDeque mà không phải viết ba phiên bản.

Xuống một bậc nữa là ba giao tiếp con, mỗi giao tiếp thêm vào một lời hứa mới. List hứa có thứ tự và chỉ số, nên nó thêm get(i), set(i, e), indexOf, và cho phép phần tử trùng. Set hứa không trùng, nên nó không thêm phương thức nào đáng kể mà lại siết chặt hợp đồng của add: thêm một phần tử đã có thì tập không đổi và add trả về false. Queue hứa một trình tự lấy ra, thường là vào trước ra trước, nên nó thêm offer, poll, peek. Deque mở rộng Queue cho phép thêm và lấy ở cả hai đầu, nhờ đó một ArrayDeque vừa làm được hàng đợi vừa làm được ngăn xếp.

Có một chi tiết dễ bỏ sót ở đây: không phải lớp cài đặt nào cũng hỗ trợ mọi phương thức của giao tiếp. Bộ khung cho phép một số thao tác là tuỳ chọn, và lớp không hỗ trợ thì ném UnsupportedOperationException. Danh sách trả về từ List.of(...) là ví dụ rõ nhất: nó là một List đầy đủ về mặt kiểu, nhưng gọi add trên nó sẽ ném ngoại lệ ngay lúc chạy vì nó bất biến. Thiết kế này là một đánh đổi có ý thức, đổi lấy việc mọi tập hợp đều dùng chung một bộ giao tiếp gọn thay vì tách ra hàng chục giao tiếp con chỉ khác nhau vài phương thức.

Lặp với `Iterable` và `Iterator`

Mọi Collection đều cài Iterable, nghĩa là duyệt được bằng vòng lặp for-each. Cơ chế bên dưới là Iterator: một đối tượng có hasNext() để hỏi còn phần tử không, next() để lấy phần tử kế tiếp, và remove() để xoá an toàn ngay trong lúc duyệt. Câu lệnh for-each chỉ là cú pháp đẹp gọi ngầm iterator().

List<String> ten = new ArrayList<>(List.of("An", "Binh", "Cuong"));

for (String s : ten) {            // for-each, calls iterator() under the hood
    System.out.println(s);
}

Iterator<String> it = ten.iterator();    // explicit iterator
while (it.hasNext()) {
    String s = it.next();
    if (s.startsWith("B")) it.remove();  // safe removal during iteration
}

Đừng xoá trong for-each

Không được xoá phần tử bằng list.remove(...) ngay trong vòng for-each. Tập hợp sẽ phát hiện thay đổi cấu trúc và ném ConcurrentModificationException. Muốn vừa duyệt vừa xoá, hãy dùng Iterator.remove() như ví dụ trên.

Cơ chế phát hiện sửa đổi hoạt động ra sao

Nhiều bạn học thuộc lòng câu "không được xoá trong for-each" mà không hiểu vì sao, nên tới lúc gặp biến thể khác của lỗi thì lại chịu. Hãy nhìn vào bên trong. Mỗi tập hợp giữ một bộ đếm nội bộ ghi số lần cấu trúc của nó bị thay đổi, tức số lần có phần tử được thêm vào hoặc gỡ ra. Khi ta gọi iterator(), trình lặp chụp lại giá trị bộ đếm ấy vào một biến riêng của mình. Sau đó, mỗi lần ta gọi next(), trình lặp đối chiếu bộ đếm hiện tại của tập hợp với bản chụp nó đang giữ. Hai số khớp nhau nghĩa là tập hợp không đổi kể từ lúc trình lặp ra đời, mọi thứ bình thường. Hai số lệch nhau nghĩa là ai đó đã sửa tập hợp sau lưng trình lặp, và trình lặp lập tức ném ConcurrentModificationException.

Hiểu tới đây thì mọi thứ sáng ra. Gọi list.remove(...) trong vòng for-each làm tăng bộ đếm của tập hợp mà không hề báo cho trình lặp, nên lần next() kế tiếp phát hiện lệch số và ném ngoại lệ. Trong khi đó Iterator.remove() xoá phần tử thông qua chính trình lặp, nên nó vừa tăng bộ đếm của tập hợp vừa cập nhật lại bản chụp của mình, hai số vẫn khớp và không có ngoại lệ nào. Đây cũng là lý do cái tên ConcurrentModificationException gây hiểu nhầm: nó không hề đòi hỏi phải có nhiều luồng. Chỉ một luồng, chỉ một vòng lặp, vẫn đủ để gặp nó.

Cơ chế này gọi là thất bại sớm (fail-fast), và triết lý đằng sau nó đáng để suy nghĩ. Java hoàn toàn có thể chọn cách im lặng bỏ qua, để vòng lặp chạy tiếp với dữ liệu đã lệch. Kết quả là chương trình vẫn chạy nhưng bỏ sót hoặc lặp lại phần tử, và ta chỉ phát hiện ra vài tuần sau, khi số liệu ở đâu đó không khớp. Ném ngoại lệ ngay tại dòng lỗi khó chịu hơn nhiều nhưng rẻ hơn nhiều, vì nó chỉ thẳng vào chỗ sai. Trong hai lựa chọn, hỏng ồn ào bao giờ cũng tốt hơn hỏng lặng lẽ.

Ngoài Iterator.remove(), còn hai cách nữa để vừa duyệt vừa loại phần tử một cách an toàn. Cách thứ nhất là removeIf, một phương thức mặc định của Collection nhận vào một điều kiện và tự lo phần trình lặp bên trong. Cách thứ hai là dựng một tập hợp mới chứa các phần tử cần giữ rồi thay thế tập cũ, hợp khi ta không muốn động vào tập gốc.

List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));

a.removeIf(x -> x % 2 == 0);      // shortest safe way, no explicit iterator
System.out.println(a);            // [1, 3, 5]

// Or build a new list and keep the original untouched
List<Integer> goc = List.of(1, 2, 3, 4, 5, 6);
List<Integer> le = new ArrayList<>();
for (int x : goc) {
    if (x % 2 != 0) le.add(x);    // reads goc, writes le: no conflict
}

Lập trình theo giao tiếp

Hãy khai báo biến kiểu List, Set, Map thay vì kiểu lớp cụ thể. Như vậy đổi từ ArrayList sang LinkedList chỉ cần sửa một dòng khởi tạo.

Bản đồ các giao tiếp chính

Nhánh Collection có ba giao tiếp con tiêu biểu, mỗi giao tiếp lại có vài lớp cài đặt quen thuộc.

List cho tập hợp có thứ tự, có chỉ số: ArrayList, LinkedList.
Set cho tập hợp không trùng: HashSet, LinkedHashSet, TreeSet.
Queue và Deque cho hàng đợi: ArrayDeque, PriorityQueue.

Nhánh Map đứng riêng với HashMap, LinkedHashMap, TreeMap. Các bài tiếp theo đi lần lượt qua từng nhóm, rồi khép lại bằng một bài so sánh hiệu năng để biết khi nào nên chọn cái nào.

Từ giao tiếp gốc xuống lớp cài đặt

1Iterablegiao tiếp gốc

cho phép duyệt bằng for-each qua Iterator

2Collectionnhóm phần tử đơn

gốc chung của List, Set và Queue

3List, Set, Queueba giao tiếp con

có thứ tự và chỉ số, tập không trùng, hàng đợi

4ArrayList, HashSet, ArrayDequecác lớp cài đặt

chọn theo thao tác chiếm đa số và đặc tính hiệu năng

Map đứng riêng vì lưu cặp khoá-giá trị, không thừa kế Collection.

Khi nào dùng nhóm nào

Ba giao tiếp con của Collection và giao tiếp Map giải quyết bốn kiểu nhu cầu khác nhau. Nắm được khác biệt này giúp ta chọn nhóm chỉ trong một câu hỏi.

Dùng List khi cần giữ thứ tự chèn và cho phép trùng lặp, đồng thời muốn lấy phần tử theo chỉ số. Ví dụ danh sách thao tác đã thực hiện để hoàn tác lần lượt, hay danh sách dòng trong một tệp.
Dùng Set khi chỉ quan tâm phần tử có mặt hay không và muốn loại trùng tự động. Ví dụ tập từ khoá đã gặp, tập id đã xử lý. HashSet nhanh nhất nhưng không có thứ tự, LinkedHashSet giữ thứ tự chèn, TreeSet giữ phần tử luôn được sắp.
Dùng Queue hoặc Deque khi xử lý phần tử theo trình tự ra vào, thường là vào trước ra trước, hoặc khi cần thêm và lấy ở hai đầu. Ví dụ hàng chờ tác vụ, hay ngăn xếp cho thuật toán duyệt.
Dùng Map khi cần tra cứu giá trị theo khoá. Ví dụ bảng giá theo mã hàng, số lần xuất hiện của mỗi từ. Khoá không được trùng, mỗi khoá ứng với đúng một giá trị.

Một cách nhớ nhanh: List trả lời câu hỏi phần tử thứ mấy, Set trả lời câu hỏi có chứa hay không, Queue trả lời câu hỏi ai ra trước, còn Map trả lời câu hỏi khoá này ánh xạ tới giá trị nào.

Generic trong tập hợp

Từ Java 5 mọi tập hợp đều nhận tham số kiểu trong cặp ngoặc nhọn, ví dụ List<String> là danh sách chỉ chứa String. Nhờ đó trình biên dịch kiểm tra kiểu ngay lúc dịch, ta không thể vô tình bỏ một Integer vào danh sách chuỗi, và khi lấy ra không phải ép kiểu thủ công. Trước Java 5 tập hợp chứa Object nên lỗi kiểu chỉ lộ ra lúc chạy dưới dạng ClassCastException.

List<String> ten = new ArrayList<>();   // toán tử kim cương suy ra kiểu ở vế phải
ten.add("An");
// ten.add(42);                          // lỗi ngay lúc biên dịch, không phải lúc chạy
String s = ten.get(0);                  // không cần ép kiểu, đã biết là String

List raw = new ArrayList();             // kiểu thô, nên tránh
raw.add("An");
raw.add(42);                            // biên dịch được nhưng ẩn hoạ lúc chạy

Tập hợp chỉ chứa được kiểu tham chiếu, không chứa trực tiếp kiểu nguyên thuỷ như int hay double. Ta dùng lớp bao tương ứng Integer, Double, và Java tự động đóng gói qua lại, gọi là autoboxing. Điều này tiện nhưng có chi phí, nên với dữ liệu số rất lớn và nhạy hiệu năng thì mảng nguyên thuỷ vẫn đáng cân nhắc.

Vì sao kiểu thô là một cái bẫy

Kiểu thô, tức viết List trần không kèm tham số kiểu, vẫn biên dịch được. Java giữ nó lại chỉ vì lý do tương thích ngược với mã viết trước Java 5, chứ hoàn toàn không phải để ta dùng trong mã mới. Vấn đề của nó không nằm ở chỗ nó xấu, mà ở chỗ nó dời lỗi từ lúc dịch sang lúc chạy, và dời luôn cả vị trí báo lỗi đi rất xa nơi gây ra lỗi.

Hãy theo dõi một kịch bản cụ thể. Ở dòng thứ nhất, ai đó bỏ nhầm một Integer vào một danh sách mà mọi người vẫn coi là danh sách chuỗi. Trình biên dịch không nói gì, vì với kiểu thô thì mọi phần tử đều là Object và Object thì nhận tất. Chương trình chạy êm ru. Vài trăm dòng sau, ở một phương thức khác, có thể do một người khác viết, đoạn mã lấy phần tử ra và ép về String. Tới lúc ấy ClassCastException mới nổ. Người đọc dấu vết lỗi sẽ nhìn thấy dòng ép kiểu và tưởng lỗi ở đó, trong khi thủ phạm thật nằm ở cái add từ đời nào. Kiểu generic tồn tại chính là để cắt đứt chuỗi này ngay từ mắt xích đầu tiên.

Một hệ quả tinh vi hơn của kiểu thô là nó tắt luôn cả kiểm tra generic ở những chỗ không liên quan. Khi ta gán một List thô cho một biến, trình biên dịch coi toàn bộ các phương thức generic của đối tượng đó như không có tham số kiểu nữa, kể cả những phương thức lẽ ra vẫn kiểm tra được. Nói cách khác, một chỗ dùng kiểu thô đủ để làm mất an toàn kiểu ở cả một vùng mã xung quanh. Cảnh báo unchecked mà trình biên dịch phát ra chính là nó đang nói rằng nó buông tay, kể từ đây ta tự chịu trách nhiệm.

import java.util.ArrayList;
import java.util.List;

public class KieuTho {
    @SuppressWarnings({"rawtypes", "unchecked"})
    public static void main(String[] args) {
        List tho = new ArrayList();   // raw type: the compiler stops checking
        tho.add("An");
        tho.add(42);                  // no compile error, the bug is planted here

        List<String> ten = tho;       // unchecked warning, still compiles
        String s = ten.get(1);        // ClassCastException explodes here, far away
        System.out.println(s);
    }
}

Kết luận thực hành rất ngắn: trong mã mới, không bao giờ viết kiểu thô. Nếu thật sự cần một tập hợp chứa được mọi thứ, hãy viết rõ ràng List<Object>, vì lúc đó ta tuyên bố ý định một cách tường minh và trình biên dịch vẫn tiếp tục làm việc cho ta.

Tập hợp bất biến

Từ Java 9, các giao tiếp List, Set, Map có sẵn các phương thức tĩnh tạo nhanh một tập hợp: List.of(...), Set.of(...), Map.of(k, v, ...). Chúng gọn hơn hẳn việc tạo một ArrayList rỗng rồi add từng phần tử, nhưng có một tính chất phải nắm cho chắc: kết quả trả về là tập hợp bất biến. Không thêm được, không xoá được, không sửa được. Mọi lời gọi làm thay đổi nội dung đều ném UnsupportedOperationException lúc chạy.

Thoạt nghe điều này giống một hạn chế, nhưng thật ra nó là một món quà. Một tập hợp bất biến là thứ ta có thể yên tâm chia sẻ, trả ra từ một phương thức, hay dùng làm hằng số ở cấp lớp, mà không sợ người gọi lén sửa nội dung bên trong đối tượng của ta. Nó cũng an toàn tuyệt đối khi nhiều luồng cùng đọc, vì không có gì để mà tranh chấp. Quy tắc thực dụng là: cái gì không cần thay đổi thì hãy làm cho nó không thay đổi được, và để trình biên dịch cùng thời gian chạy canh giúp.

import java.util.ArrayList;
import java.util.List;

public class BatBien {
    private static final List<String> NGAY =
            List.of("Hai", "Ba", "Tu");        // immutable constant, safe to share

    public static void main(String[] args) {
        // NGAY.add("Nam");                    // throws UnsupportedOperationException

        List<String> sua = new ArrayList<>(NGAY);  // copy it to get a mutable list
        sua.add("Nam");                            // fine, this is our own copy
        System.out.println(sua);                   // [Hai, Ba, Tu, Nam]
        System.out.println(NGAY);                  // [Hai, Ba, Tu], untouched
    }
}

Ba cái bẫy của List.of và Arrays.asList

Thứ nhất, List.of(...) không nhận null, truyền null vào là nhận NullPointerException ngay lúc tạo. Đây là cố ý, vì một hằng số chứa null gần như luôn là dấu hiệu của lỗi.

Thứ hai, Arrays.asList(...) không giống List.of(...). Nó trả về một khung nhìn có kích thước cố định gắn với mảng gốc: add và remove đều ném ngoại lệ, nhưng set(i, e) lại chạy được và sửa thẳng vào mảng gốc. Nửa vời như vậy nên trong mã mới hãy ưu tiên List.of.

Thứ ba, muốn có một danh sách sửa được từ một danh sách bất biến, phải sao chép: new ArrayList<>(List.of(...)). Rất nhiều người viết List<String> a = List.of("x") rồi mấy dòng sau gọi a.add(...) và ngơ ngác vì ngoại lệ, dù mã biên dịch sạch. Kiểu tĩnh là List nên biên dịch không thể biết; chỉ lúc chạy mới lộ.

Tạo và duyệt: ví dụ tổng hợp

Ví dụ dưới tạo một đại diện của mỗi nhóm rồi duyệt qua. Chú ý cách duyệt Map phải đi qua entrySet() vì bản thân Map không phải Collection.

// List: có thứ tự, có chỉ số, cho trùng
List<String> ds = new ArrayList<>(List.of("An", "Binh", "An"));
for (int i = 0; i < ds.size(); i++) {
    System.out.println(i + ": " + ds.get(i));   // duyệt theo chỉ số
}

// Set: loại trùng, không hứa thứ tự
Set<String> tap = new HashSet<>(ds);
System.out.println(tap.size());                 // 2 vì "An" chỉ còn một

// Map: tra giá trị theo khoá
Map<String, Integer> tuoi = new HashMap<>();
tuoi.put("An", 20);
tuoi.put("Binh", 21);
for (Map.Entry<String, Integer> e : tuoi.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());  // duyệt cặp khoá-giá trị
}

Ba lỗi hay gặp khi mới học tập hợp

Thứ nhất, dùng kiểu thô như List thay vì List<String> làm mất kiểm tra kiểu, lỗi dồn sang lúc chạy. Thứ hai, giả định HashSet hay HashMap giữ thứ tự chèn, thực ra thứ tự duyệt của chúng không xác định; cần thứ tự thì dùng bản Linked.... Thứ ba, sửa cấu trúc tập hợp ngay trong for-each, việc này ném ConcurrentModificationException như đã nói ở phần Iterator.

Chọn cấu trúc theo thao tác chiếm đa số

Tới đây ta có thể phát biểu nguyên tắc chọn cấu trúc một cách rành mạch. Đừng hỏi "dữ liệu của tôi trông giống cái gì", vì câu hỏi đó dẫn tới việc chọn theo thói quen. Hãy hỏi "trong suốt vòng đời của dữ liệu này, thao tác nào bị gọi nhiều nhất". Cấu trúc dữ liệu nào cũng làm được mọi việc, chỉ khác nhau ở chỗ việc nào rẻ và việc nào đắt. Chọn đúng nghĩa là đặt cái rẻ vào chỗ chạy nhiều, và chấp nhận cái đắt ở chỗ chạy hiếm.

Ba con số sau đủ để quyết định trong phần lớn tình huống. ArrayList lấy phần tử theo chỉ số mất O(1) nhưng tìm một giá trị bất kỳ mất O(n) vì phải quét. HashSet và HashMap kiểm tra tồn tại hay tra theo khoá chỉ mất O(1) trung bình, đổi lại không giữ thứ tự nào. TreeSet và TreeMap mất O(log n) cho mọi thao tác nhưng cho ta dữ liệu luôn ở trạng thái đã sắp, kèm các truy vấn theo khoảng.

Ví dụ kinh điển hay bị làm sai là kiểm tra trùng. Có n mục cần lọc trùng, người mới học thường giữ một ArrayList rồi mỗi lần thêm lại gọi contains để xem đã có chưa. Mỗi lần contains quét cả danh sách, tốn O(n), mà ta gọi nó n lần, thành O(n²). Với một nghìn mục thì không ai thấy gì, với một triệu mục thì chương trình đứng hình. Thay ArrayList bằng HashSet, mỗi lần kiểm tra chỉ còn O(1) trung bình, tổng chi phí xuống O(n). Đoạn mã dài ngang nhau, chỉ khác đúng một cái tên lớp, nhưng khác nhau một trời một vực về thời gian chạy. Đây chính là điều mà cả chương này muốn dạy.

Thao tác chiếm đa số	Cấu trúc nên chọn	Chi phí trung bình
Lấy phần tử theo chỉ số	`ArrayList`	`O(1)`
Thêm hoặc xoá ở cuối danh sách	`ArrayList`	`O(1)` khấu trừ
Thêm hoặc xoá ở hai đầu	`ArrayDeque`	`O(1)`
Kiểm tra một phần tử đã có chưa	`HashSet`	`O(1)`
Tra giá trị theo khoá	`HashMap`	`O(1)`
Giữ dữ liệu luôn ở trạng thái đã sắp	`TreeSet` hoặc `TreeMap`	`O(log n)`
Lấy ra phần tử ưu tiên cao nhất	`PriorityQueue`	`O(log n)`
Duyệt lại đúng thứ tự đã thêm	`LinkedHashSet` hoặc `LinkedHashMap`	`O(1)`

Bảng này không phải để học thuộc. Cách dùng nó là: viết ra vòng lặp nóng của chương trình, xem trong vòng lặp đó tập hợp bị gọi phương thức gì, rồi tra ngược lên cột đầu. Nếu thao tác nóng nhất của ta lại rơi vào ô đắt của cấu trúc đang dùng, đó là dấu hiệu chọn sai.

Bài tập thực hành

Bài tập 1: vì sao `Map` đứng riêng

Giải thích vì sao Map không kế thừa Collection. Cho một lý do về mặt mô hình dữ liệu và một hệ quả thực tế khi lập trình.

Lời giải chi tiết

Về mô hình dữ liệu: Collection mô tả một nhóm phần tử đơn, còn Map lưu cặp khoá-giá trị, là một mô hình khác hẳn. Gộp chung vào một cây kế thừa sẽ ép Map phải có những phương thức không có nghĩa, ví dụ add(phần_tử_đơn).

Hệ quả thực tế: ta không thể for-each trực tiếp trên một Map. Muốn duyệt phải qua keySet(), values() hoặc entrySet(), vì chỉ các view này mới là Collection thực sự.

Bài tập 2: duyệt và xoá an toàn

Cho List<Integer> a. Viết đoạn mã xoá mọi số chẵn khỏi a ngay trong lúc duyệt, sao cho không ném ConcurrentModificationException.

Lời giải chi tiết

Dùng Iterator tường minh và gọi it.remove(), tuyệt đối không gọi a.remove(...) trong vòng lặp.

Iterator<Integer> it = a.iterator();
while (it.hasNext()) {
    int x = it.next();
    if (x % 2 == 0) it.remove();   // safe structural change via the iterator
}

Ý chính: chỉ Iterator.remove() mới báo cho tập hợp biết thay đổi này là hợp lệ, nên không kích hoạt cơ chế phát hiện sửa đổi đồng thời.

Bài tập 3: chọn nhóm cho từng nhu cầu

Với mỗi nhu cầu sau, hãy chọn nhóm phù hợp trong bốn nhóm List, Set, Queue, Map và nói ngắn gọn vì sao: (a) đếm số lần xuất hiện của mỗi từ trong một đoạn văn; (b) lưu lịch sử các trang đã mở để bấm quay lại; (c) khử trùng danh sách email trước khi gửi.

Lời giải chi tiết

(a) Dùng Map<String, Integer>: khoá là từ, giá trị là số đếm, tra và cập nhật theo khoá đều nhanh. (b) Dùng Deque làm ngăn xếp: trang mở sau nằm trên đỉnh, bấm quay lại thì pop ra trang gần nhất, đúng nguyên tắc vào sau ra trước. (c) Dùng Set: đưa toàn bộ email vào một HashSet là trùng lặp tự biến mất, sau đó gửi theo tập đã khử trùng.

Bài tập 4: hạ độ phức tạp từ bình phương xuống tuyến tính

Đoạn mã dưới lọc trùng bằng ArrayList và contains, chạy đúng nhưng tốn O(n²). Hãy chỉ ra chính xác dòng nào gây ra chi phí bình phương, rồi viết lại để tổng chi phí xuống O(n) mà vẫn giữ nguyên thứ tự xuất hiện lần đầu của mỗi phần tử.

static List<String> locTrung(List<String> nguon) {
    List<String> ketQua = new ArrayList<>();
    for (String s : nguon) {
        if (!ketQua.contains(s)) ketQua.add(s);   // which line is the culprit?
    }
    return ketQua;
}

Lời giải chi tiết

Thủ phạm là lời gọi ketQua.contains(s). ArrayList không có cách nào tìm nhanh một giá trị, nó buộc phải quét tuần tự từ đầu tới khi gặp hoặc hết danh sách, nên mỗi lần gọi tốn O(n). Vòng lặp ngoài chạy n lần, mỗi lần lại quét O(n), tổng thành O(n²). Chú ý là add không có lỗi gì ở đây, nó chỉ tốn O(1) khấu trừ.

Cách chữa là tách hai vai trò ra hai cấu trúc, mỗi cấu trúc làm đúng việc nó giỏi. Một HashSet lo việc trả lời câu hỏi "đã gặp chưa" với chi phí O(1) trung bình, còn một ArrayList lo việc ghi lại thứ tự xuất hiện. Chi phí mỗi phần tử xuống O(1), tổng thành O(n).

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LocTrung {
    static List<String> locTrung(List<String> nguon) {
        Set<String> daGap = new HashSet<>();   // membership test in O(1)
        List<String> ketQua = new ArrayList<>();
        for (String s : nguon) {
            if (daGap.add(s)) ketQua.add(s);   // add() returns false if already present
        }
        return ketQua;
    }

    public static void main(String[] args) {
        System.out.println(locTrung(List.of("a", "b", "a", "c", "b")));  // [a, b, c]
    }
}

Có một mẹo nhỏ đáng học ở dòng if (daGap.add(s)). Hợp đồng của Set.add nói rằng nó trả về true khi tập hợp thực sự thay đổi, tức phần tử chưa từng có, và trả về false khi phần tử đã có sẵn. Nhờ vậy ta gộp được hai việc kiểm tra và thêm vào một lời gọi duy nhất, thay vì gọi contains rồi add thành hai lần băm.

Nếu bài toán không đòi hỏi giữ thứ tự xuất hiện, lời giải còn ngắn hơn nữa: chỉ cần new LinkedHashSet<>(nguon) là xong, hoặc new HashSet<>(nguon) nếu thứ tự cũng không quan trọng. Đây là minh hoạ trực tiếp cho nguyên tắc chọn cấu trúc theo thao tác chiếm đa số.

Câu hỏi tự kiểm

Kiểm tra nhanh: tổng quan Collections Framework0/4 đúngchưa trả lời

1Giao tiếp nào nằm ở đỉnh nhánh Collection, khiến mọi tập hợp đều duyệt được bằng for-each?
2ConcurrentModificationException có bắt buộc phải có nhiều luồng mới xảy ra không?
3Dùng kiểu thô (raw type) như List thay vì List<String> có hại gì?
4List.of("a", "b") trả về loại danh sách nào?

Tóm tắt và ghi nhớ

Bộ khung chia làm hai nhánh: nhánh Collection gồm List, Set, Queue, và nhánh Map đứng riêng vì lưu cặp khoá-giá trị.
Mọi Collection đều là Iterable nên duyệt được bằng for-each; muốn vừa duyệt vừa xoá thì dùng Iterator.remove().
Chọn nhóm theo thao tác nhiều nhất: chỉ số dùng List, kiểm tra tồn tại dùng Set, trình tự ra vào dùng Queue, tra theo khoá dùng Map.
Luôn khai báo biến theo giao tiếp và đặt tham số kiểu generic để trình biên dịch bắt lỗi sớm.
ConcurrentModificationException sinh ra từ cơ chế thất bại sớm, dựa trên một bộ đếm số lần sửa cấu trúc; nó không đòi hỏi phải có nhiều luồng.
Kiểu thô làm mất kiểm tra kiểu và đẩy lỗi sang lúc chạy ở một nơi rất xa chỗ gây lỗi, nên trong mã mới tuyệt đối không dùng.
List.of và các anh em của nó tạo tập hợp bất biến, an toàn để chia sẻ, nhưng sửa vào là ném UnsupportedOperationException; muốn sửa thì sao chép sang một tập hợp mới.
Nguyên tắc chọn cấu trúc gói gọn trong một câu: đặt thao tác rẻ vào chỗ chạy nhiều nhất.

Thử ngay: xem một tập hợp được duyệt chạy từng bước​

Hai nhánh lớn của bộ khung​

Đọc cây phân cấp cho kỹ​

Lặp với Iterable và Iterator​

Cơ chế phát hiện sửa đổi hoạt động ra sao​

Bản đồ các giao tiếp chính​

Khi nào dùng nhóm nào​

Generic trong tập hợp​

Vì sao kiểu thô là một cái bẫy​

Tập hợp bất biến​

Tạo và duyệt: ví dụ tổng hợp​

Chọn cấu trúc theo thao tác chiếm đa số​

Bài tập thực hành​

Bài tập 1: vì sao Map đứng riêng​

Bài tập 2: duyệt và xoá an toàn​

Bài tập 3: chọn nhóm cho từng nhu cầu​

Bài tập 4: hạ độ phức tạp từ bình phương xuống tuyến tính​

Câu hỏi tự kiểm​

Tóm tắt và ghi nhớ​

Thử ngay: xem một tập hợp được duyệt chạy từng bước

Hai nhánh lớn của bộ khung

Đọc cây phân cấp cho kỹ

Lặp với `Iterable` và `Iterator`

Cơ chế phát hiện sửa đổi hoạt động ra sao

Bản đồ các giao tiếp chính

Khi nào dùng nhóm nào

Generic trong tập hợp

Vì sao kiểu thô là một cái bẫy

Tập hợp bất biến

Tạo và duyệt: ví dụ tổng hợp

Chọn cấu trúc theo thao tác chiếm đa số

Bài tập thực hành

Bài tập 1: vì sao `Map` đứng riêng

Bài tập 2: duyệt và xoá an toàn

Bài tập 3: chọn nhóm cho từng nhu cầu

Bài tập 4: hạ độ phức tạp từ bình phương xuống tuyến tính

Câu hỏi tự kiểm

Tóm tắt và ghi nhớ