Tổng quan Collections Framework

Tình huống mở đầu

Thứ Sáu, màn hình bếp quán Cà Phê Chú Tư nhận tới 300 đơn trong một buổi sáng. Bạn đang dùng một ArrayList cho mọi việc: xếp hàng đơn, kiểm tra mã đơn đã nhận chưa, và tìm đơn của khách số 7. Với 300 đơn, mọi thứ vẫn mượt. Tới đợt khuyến mại, danh sách có 200000 mã đơn và mỗi đơn mới phải hỏi "mã này có chưa" trước khi nhận. Mỗi lần hỏi, máy đi qua từng mã từ đầu đến cuối.

Code không có lỗi, không có dòng chữ đỏ nào, nhưng màn hình đứng hình. Bạn chưa đổi thuật toán nào, chỉ đổi kiểu của một biến thì mọi thứ lại mượt. Vậy chọn đúng loại cấu trúc dữ liệu nghĩa là gì? Giữ câu hỏi này, cuối bài bạn sẽ đo được nó bằng số.

Ôn nhanh bài trước: để một phương thức đọc được cả List<Integer> lẫn List<Double>, bạn khai báo tham số kiểu gì?

Đáp án: List<? extends Number>. Dấu ? kèm extends nghĩa là "danh sách của một kiểu con nào đó của Number", nên đọc được nhưng không thêm tuỳ tiện được.

Mục tiêu bài học

Sau bài này, bạn có thể:

• Vẽ được họ Collection gồm List, Set, Queue và chỉ ra Map đứng riêng.
• Chọn được List, Set hay Map cho một việc của màn hình bếp dựa vào câu hỏi mà việc đó hay hỏi.
• Giải thích được vì sao contains trên ArrayList phải đi qua từng phần tử, còn trên HashSet thì nhảy tới đúng ngăn chứa.
• Phân biệt được List.of, List.copyOf và Collections.unmodifiableList khi dữ liệu gốc thay đổi.

Bài này đo được bằng năm câu trong phần Tự kiểm tra, mỗi câu ghi rõ nó kiểm tra mục tiêu nào.

Hãy xem video dưới đây để có cái nhìn đầu tiên, sau đó mình đi chậm hơn từng bước ở các phần sau.

Bức tranh lớn (Big Picture)

Bài này là bản đồ của cả chương Collections. Trước khi học từng lớp, hãy xem màn hình bếp hỏi những câu gì.

Cách đọc hình: ba cột, mỗi cột đọc từ trên xuống. Hàng trên là câu hỏi của bếp: ai là người kế tiếp, đơn này đã có chưa, khách số 7 gọi gì. Hàng giữa là loại cấu trúc trả lời câu hỏi đó: List, Set, Map. Hàng dưới là lớp thường chọn: ArrayList, HashSet, HashMap. Màu chỉ là tín hiệu phụ, mỗi ô đều có chữ.

Chương này có bốn bài, và cả bốn dùng chung một dự án: màn hình bếp quán Cà Phê Chú Tư. Bài 41 dựng danh sách đơn, bài 42 thêm việc chặn đơn trùng và tra đơn theo khách, bài 43 sắp xếp các đơn. Bài hôm nay là bản đồ để bạn biết mình sẽ đi đâu.

Ẩn dụ xuyên suốt là những ngăn kéo trong quầy: mỗi ngăn được tổ chức để trả lời nhanh một kiểu câu hỏi. Có chỗ ẩn dụ không còn đúng: ngăn kéo thật không tự đổi cách xếp đồ, còn cấu trúc dữ liệu thì có thể đổi cách làm phía sau mà tên ngăn kéo (interface) vẫn giữ nguyên.

Khái niệm cốt lõi

Bài này có bốn khái niệm, mỗi khái niệm đi kèm một hình.

Khái niệm 1: họ Collection và Map đứng riêng

Collection là hợp đồng chung của mọi nhóm phần tử: thêm, bớt, đếm, kiểm tra có mặt. Ba nhánh con là List (có thứ tự và chỉ số), Set (không trùng) và Queue (xếp hàng, lấy từ đầu). Iterable đứng trên cùng, là thứ làm cho vòng for-each dùng được. Trong quầy, Collection là cái nhãn "ngăn kéo đựng nhiều món".

Cách đọc hình: đi từ trên xuống. Iterable mở rộng thành Collection, rồi Collection chia ba thành List, Set, Queue. Ô Map ở bên phải không có đường nối nào tới Collection. Dòng ghi chú dưới hình nói lý do: Map giữ cặp khoá và giá trị nên add(x) một tham số không hợp với nó.

Map lưu từng cặp gồm khoá (key) và giá trị (value). Bạn đưa khoá thì nhận lại giá trị. Muốn duyệt Map, bạn đi qua tập khoá hoặc tập các cặp, không duyệt trực tiếp như List.

Concept Check 1. Câu nào đúng về Map?

• A. Map là con của Collection nên gọi được map.add(x) như List.
• B. Map đứng riêng vì lưu cặp khoá và giá trị, nên không có add một tham số mà có put(key, value).
• C. Map là con của List, nên khoá chính là chỉ số của phần tử.
• D. Map là con của Set, nên dùng map.contains(x) để hỏi có khoá x không.

Đáp án: B. A sai vì Map không kế thừa Collection nên không có add. C sai vì khoá của Map có thể là chuỗi, số bất kỳ, không phải chỉ số xếp từ 0, và Map không phải List. D nhầm vì khoá của Map đúng là không trùng nhau, nhưng Map không phải Set và câu hỏi "có khoá x không" dùng containsKey(x).

Khái niệm 2: cùng interface, khác lớp, khác thứ tự duyệt

Một interface có thể có nhiều lớp cài đặt, và chúng khác nhau ở thứ tự duyệt. Với Set: HashSet không hứa thứ tự nào, LinkedHashSet giữ thứ tự thêm vào, TreeSet luôn sắp xếp. Ẩn dụ: cùng một ngăn kéo "không trùng", nhưng ngăn thì xếp tuỳ ý, ngăn thì xếp theo lúc bỏ vào, ngăn thì xếp theo abc.

Đoạn code dưới đây đưa cùng năm đơn vào ba loại tập:

List<String> orders = new ArrayList<>(List.of("Tea", "Latte", "Tea", "Mocha", "Latte"));
System.out.println("LinkedHashSet " + new LinkedHashSet<>(orders));  // giữ thứ tự lần đầu gặp
System.out.println("TreeSet       " + new TreeSet<>(orders));       // sắp theo abc
System.out.println("HashSet size  " + new HashSet<>(orders).size());  // chỉ in size vì thứ tự không được hứa

Kết quả [Đã chạy, JDK 17.0.15]:

LinkedHashSet [Tea, Latte, Mocha]
TreeSet       [Latte, Mocha, Tea]
HashSet size  3

Thứ tự in của chính HashSet [Có thể khác nhau] giữa các phiên bản Java và giữa các dữ liệu, nên bài này không in nó ra.

Cách đọc hình: ô bên trái là dữ liệu vào với hai đơn trùng. Ba ô bên phải là ba lớp tập. LinkedHashSet và TreeSet ghi rõ thứ tự ra, ô HashSet ghi "order not promised". Cả ba đều chỉ còn ba đơn khác nhau.

Khái niệm 3: chi phí tìm kiếm

Chi phí tìm là số việc máy phải làm để trả lời "phần tử này có trong nhóm không". Với ArrayList, máy đi qua từng ghế và so sánh bằng equals cho tới khi gặp. Với HashSet, máy tính hashCode (mã băm, một con số suy ra từ nội dung khoá) để biết ngăn nào có thể chứa khoá, rồi chỉ nhìn ngăn đó. Ẩn dụ: tìm một cuốn sách bằng cách lật từng cuốn trên kệ, so với tra số kệ ghi sẵn trong sổ rồi đi thẳng tới đó.

Chương trình LookupCost đo việc này bằng cách đếm số lần equals bị gọi. Đây là phần cốt lõi của nó:

// Bộ đếm số lần equals bị gọi
static int calls = 0;

static class Key {
    final int id;
    Key(int id) { this.id = id; }

    @Override
    public boolean equals(Object o) {
        calls++;  // mỗi lần so sánh được tính một lần
        return o instanceof Key && ((Key) o).id == id;
    }

    @Override
    public int hashCode() { return id; }  // mỗi khoá một mã băm riêng
}

Phần đo, sau khi nạp 100000 khoá vào cả list lẫn set:

calls = 0;  // xoá bộ đếm để không tính lẫn lúc nạp dữ liệu
list.contains(new Key(99999));  // khoá cuối: trường hợp xấu nhất
System.out.println("list equals calls: " + calls);
calls = 0;
set.contains(new Key(99999));
System.out.println("set equals calls: " + calls);

Kết quả [Đã chạy, JDK 17.0.15]:

list equals calls: 100000
set equals calls: 1

Hình dưới đây vẽ lại hai con số này:

Cách đọc hình: ô bên trái là câu hỏi contains cho khoá cuối. Nhánh trên đi qua ArrayList tới ô đỏ ghi 100000 lần equals. Nhánh dưới đi qua HashSet tới ô lục ghi 1 lần equals. Màu chỉ là tín hiệu phụ, con số mới là điều cần đọc.

Hãy xem từng bước máy thực hiện:

Bản chữ tương đương của animation:

Điều kiện để tập băm nhanh: hai khoá bằng nhau phải có cùng mã băm, và mã băm phải phân bố đều. Bài 42 sẽ đi sâu vào hợp đồng equals và hashCode.

Khái niệm 4: sửa được, chỉ đọc, và khung nhìn

Một danh sách chia sẻ cho màn hình hiển thị thường không được phép sửa. Java có ba cách, và chúng khác nhau ở điều xảy ra khi dữ liệu gốc đổi. List.of tạo danh sách bất biến ngay từ đầu. List.copyOf chép dữ liệu hiện có sang một danh sách bất biến mới. Collections.unmodifiableList chỉ bọc dữ liệu gốc bằng một khung nhìn (view) chặn việc sửa qua nó. Ẩn dụ: bức ảnh chụp quầy, so với cửa sổ kính nhìn thẳng vào quầy.

List<String> source = new ArrayList<>(List.of("Latte", "Mocha"));
List<String> view = Collections.unmodifiableList(source);  // khung nhìn, không chép dữ liệu
List<String> copy = List.copyOf(source);                   // chụp dữ liệu lúc này
source.add("Tea");  // chỉ source và view thấy Tea
System.out.println("source " + source + ", view " + view + ", copy " + copy);

Kết quả [Đã chạy, JDK 17.0.15]:

source [Latte, Mocha, Tea], view [Latte, Mocha, Tea], copy [Latte, Mocha]

Cách đọc hình: ô bên trái là danh sách gốc, vừa có thêm Tea. Ô trên cùng là khung nhìn, nối nét đứt với gốc nên thấy cả Tea. Ô giữa là bản sao, nối một lần nên vẫn giữ Latte và Mocha. Ô dưới cùng là List.of, không nối với gì cả. Cả ba đều ném lỗi khi bạn gọi add qua chúng.

Concept Check 2. Màn hình hiển thị nhận Collections.unmodifiableList(orders). Sau đó bếp gọi orders.add("Tea"). Màn hình hiển thị thấy gì?

• A. Thấy cả Tea, vì khung nhìn đọc thẳng dữ liệu của danh sách gốc.
• B. Không thấy Tea, vì khung nhìn đã chụp lại dữ liệu lúc được tạo.
• C. Gặp UnsupportedOperationException, vì danh sách gốc cũng bị khoá.
• D. Gặp NullPointerException, vì khung nhìn mất liên kết với gốc.

Đáp án: A. B nhầm khung nhìn với bản sao: chụp lại dữ liệu là việc của List.copyOf. C sai vì chỉ việc sửa qua khung nhìn bị chặn, danh sách gốc vẫn sửa bình thường. D sai vì khung nhìn giữ liên kết tới gốc, không bao giờ tự mất.

Ví dụ đầu tiên (Worked Example) và "Xem từng bước"

Đây là chương trình đầu tiên của dự án: cùng ba đơn đi vào ba loại cấu trúc.

KitchenOverview.java

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

public class KitchenOverview {
    public static void main(String[] args) {
        // Biến kiểu List trỏ tới một ArrayList: ba đơn, Latte xuất hiện hai lần
        List<String> orders = new ArrayList<>();
        orders.add("Latte");
        orders.add("Mocha");
        orders.add("Latte");
        System.out.println("list: " + orders + " size " + orders.size());

        // Chép sang Set: Latte trùng bị bỏ nên chỉ còn 2 phần tử
        Set<String> menu = new HashSet<>(orders);
        System.out.println("set size " + menu.size() + ", has Mocha " + menu.contains("Mocha"));

        // Map lưu cặp khoá và giá trị: số khách và đồ họ gọi
        Map<Integer, String> byCustomer = new HashMap<>();
        byCustomer.put(7, "Latte");
        byCustomer.put(8, "Mocha");
        // Khoá 9 không có nên get trả về null, không báo lỗi
        System.out.println("customer 7: " + byCustomer.get(7) + ", customer 9: " + byCustomer.get(9));
    }
}

Predict: hãy dừng lại, lấy giấy nháp và đoán ba dòng in ra là gì. Đặc biệt: tập menu có mấy phần tử, và byCustomer.get(9) cho gì? Đoán xong rồi hãy đọc tiếp.

Kết quả mong đợi [Đã chạy, JDK 17.0.15]:

list: [Latte, Mocha, Latte] size 3
set size 2, has Mocha true
customer 7: Latte, customer 9: null

Đọc code từng dòng:

Bây giờ xem từng bước. Mỗi bước nêu dòng code đang chạy, trạng thái ba cấu trúc và lý do:

Bảng trace (bản chữ tương đương của animation, [Suy luận] bằng cách đi từng dòng và khớp với kết quả chạy thật):

Bạn vừa làm được: đọc một chương trình dùng ba loại cấu trúc và nói đúng mỗi cấu trúc giữ gì sau từng dòng.

Concept Check xen kẽ

Chọn đáp án của bạn trước, rồi đọc phần đáp án ngay bên dưới.

Concept Check 3. HashSet đang chứa 1 triệu khoá và hashCode của khoá phân bố đều. Gọi contains(k) thì equals được gọi khoảng bao nhiêu lần?

• A. Khoảng 1 triệu lần, vì tập hợp vẫn phải xem lần lượt từng khoá.
• B. Khoảng 500 nghìn lần, vì khoá thường nằm ở giữa tập hợp.
• C. Khoảng 20 lần, vì tập hợp chia đôi tập khoá sau mỗi lần so sánh.
• D. Khoảng 1 lần, vì mã băm đưa thẳng tới ngăn chứa và equals chỉ xác nhận.

Đáp án: D. A và B mô tả cách làm của danh sách, không phải của tập băm. C là cách tìm nhị phân trên dữ liệu đã sắp xếp, không phải cách HashSet làm. Con số 1 là kết quả đo ở phần Khái niệm 3, và nó chỉ đúng khi mã băm phân bố đều.

Concept Check 4. Cần một danh sách đơn không trùng, và khi in ra phải đúng thứ tự khách đã đặt. Chọn lớp nào?

• A. HashSet, vì nó bỏ trùng nên đủ, còn thứ tự thì Java tự lo cho đúng.
• B. TreeSet, vì nó bỏ trùng và giữ nguyên thứ tự khách đặt vào.
• C. LinkedHashSet, vì nó bỏ trùng và nhớ thứ tự lần đầu mỗi phần tử được thêm.
• D. ArrayList, vì danh sách tự bỏ phần tử trùng ngay khi bạn gọi add.

Đáp án: C. LinkedHashSet nối cổng bỏ trùng của Set với việc nhớ thứ tự thêm vào. A sai vì HashSet không hứa thứ tự nào. B sai vì TreeSet sắp theo abc chứ không theo lúc đặt. D sai vì ArrayList giữ cả phần tử trùng.

Làm cùng mình (Guided Practice)

Bạn sẽ dựng dần class Kitchen qua năm bước nhỏ. Hỗ trợ giảm dần: bước 1 gần như làm sẵn, bước 5 chỉ còn đề. Gõ code vào file Kitchen.java rồi chạy bằng java Kitchen.java.

Bước 1: danh sách đơn.

import java.util.*;

public class Kitchen {
    public static void main(String[] args) {
        List<String> queue = new ArrayList<>();
        queue.add("Latte");
        // TODO 1: thêm "Mocha", rồi thêm "Latte"
        System.out.println("step 1: " + queue);
    }
}

Chạy xong bạn sẽ thấy: step 1: [Latte, Mocha, Latte].

Bước 2: các loại đồ uống khác nhau. Thêm dưới dòng in của bước 1:

        Set<String> menu = new HashSet<>();
        // TODO 2: nạp mọi đơn trong queue vào menu
        System.out.println("step 2: " + menu.size());

Chạy xong bạn sẽ thấy: step 2: 2. Gợi ý: Set có một phương thức nhận cả một nhóm phần tử, hoặc bạn đưa queue thẳng vào hàm tạo.

Bước 3: tra đơn theo khách.

        Map<Integer, String> byCustomer = new HashMap<>();
        // TODO 3: khách 7 gọi Latte, khách 8 gọi Mocha, khách 9 gọi Latte
        System.out.println("step 3: " + byCustomer.get(8) + " " + byCustomer.get(10));

Chạy xong bạn sẽ thấy: step 3: Mocha null.

Vẽ ra giấy: kẻ hai cột "khoá" và "giá trị", điền ba cặp bạn vừa thêm, rồi tự tra khoá 8 và khoá 10. Đối chiếu: khoá 8 ra Mocha, khoá 10 không có trong bảng nên là null. Số cặp bằng 3 dù Latte xuất hiện hai lần ở cột giá trị, vì Map chỉ không cho trùng khoá, giá trị thì trùng thoải mái.

Bước 4: chặn mã đơn trùng. Bạn tự quyết cách viết.

        Set<String> seen = new HashSet<>();
        boolean first = false;
        boolean again = false;
        // TODO 4: thêm mã đơn "A100" vào seen hai lần, ghi kết quả hai lần thêm vào first và again
        System.out.println("step 4: " + first + " " + again);

Chạy xong bạn sẽ thấy: step 4: true false. Gợi ý: Set.add trả về boolean cho biết tập có thay đổi không.

Bước 5: bản sao chỉ đọc cho màn hình hiển thị.

        // TODO 5: tạo bản sao chỉ đọc của queue tên board, rồi thêm "Tea" vào queue
        System.out.println("step 5: " + queue.size() + " " + board.size());

Chạy xong bạn sẽ thấy: step 5: 4 3. Gợi ý: bản sao phải chụp lại dữ liệu hiện có, không đi theo queue về sau. Lời giải đầy đủ nằm ở cuối bài.

Bạn vừa làm được: dựng một chương trình dùng đủ List, Set, Map và bản sao chỉ đọc. Toàn bộ mã nguồn của bài nằm trong thư mục 12-collections/01-tong-quan của kho GitHub, nhưng bạn không cần mở nó để học.

Thử phá nó đi (Lỗi thường gặp)

Bốn lỗi dưới đây là những lỗi người mới gặp nhiều nhất khi bắt đầu dùng Collections. Mỗi dòng đã được chạy thật [Đã chạy, JDK 17.0.15; thông báo lỗi có thể khác chữ ở phiên bản Java khác].

Hiểu lầm lớn nhất không có thông báo lỗi: dùng List cho mọi thứ vì quen tay. Hình dưới đây đặt hai mô hình cạnh nhau.

Cách đọc hình: hàng trên màu đỏ là mô hình sai: coi mọi thứ là List nên mỗi lần kiểm tra trùng phải quét tới 200000 mã. Hàng dưới màu lục là mô hình đúng: việc kiểm tra trùng giao cho Set, chỉ cần khoảng 1 lần kiểm tra cho mỗi đơn mới. Hai hàng viết gần giống nhau, chỉ khác kiểu của một biến.

Bạn vừa làm được: đọc bốn lỗi phổ biến của Collections, và nhận ra lỗi không có thông báo là chọn sai cấu trúc.

Tự tay làm (Bài tập)

Làm lần lượt từng mức. Mỗi bài có đề, dữ liệu vào, kết quả mong đợi, tiêu chí nghiệm thu và gợi ý. Lời giải nằm riêng ở cuối bài, hãy thử trước rồi mới so.

Mức Cơ bản

Bài 1. Vẽ trạng thái. Dữ liệu vào là đoạn code sau, chạy theo từng dòng:

List<String> a = new ArrayList<>(List.of("Latte", "Mocha", "Latte"));
Set<String> b = new HashSet<>(a);
Map<Integer, String> c = new HashMap<>();
c.put(1, a.get(0));
c.put(2, a.get(1));
c.put(1, "Tea");   // khoá 1 đã có nên chỉ thay giá trị
b.add("Mocha");   // Mocha đã có trong tập

Điền bảng gồm năm cột: dòng vừa chạy, a.size(), b.size(), c.size(), c.get(1). Kết quả mong đợi: bảng bảy dòng. Tiêu chí nghiệm thu: dòng cuối trùng với kết quả chạy thật, và bạn nói được dòng nào không làm size đổi. Gợi ý: put với khoá đã có thì thay giá trị chứ không thêm cặp mới.

Bài 2. Chọn cấu trúc. Dữ liệu vào là bốn việc. Với mỗi việc, ghi lớp bạn chọn và một câu lý do: (a) hàng chờ pha chế theo thứ tự đến, có thể trùng đồ uống; (b) tập mã đơn đã xử lý, hỏi "có chưa"; (c) tên khách và đơn của họ, tra theo tên; (d) thực đơn in ra theo thứ tự abc, không trùng. Kết quả mong đợi: bốn lớp khác nhau. Tiêu chí nghiệm thu: mỗi lý do nêu được câu hỏi mà việc đó hay hỏi. Gợi ý: nhìn vào hình "Which collection for which job".

Bài 3. Sửa lỗi bất biến. Dữ liệu vào:

List<String> menu = List.of("Latte", "Mocha");
menu.add("Tea");

Sửa để thêm được Tea và in ra [Latte, Mocha, Tea]. Tiêu chí nghiệm thu: không còn ngoại lệ, và bạn giải thích được vì sao List.of không cho thêm. Gợi ý: bọc vào một danh sách sửa được.

Mức Vận dụng

Bài 4. Làm sạch đơn của bếp. Dữ liệu vào: danh sách Tea, Latte, Tea, Mocha, Latte. Viết chương trình tạo ba thứ từ danh sách này: danh sách không trùng giữ thứ tự khách đặt, danh sách không trùng sắp theo abc, và bản sao chỉ đọc của danh sách đầu tiên để gửi cho màn hình hiển thị. Kết quả mong đợi:

unique [Tea, Latte, Mocha]
sorted [Latte, Mocha, Tea]
frozen add: UnsupportedOperationException

Tiêu chí nghiệm thu: ba dòng in ra khớp từng ký tự, và bản sao chỉ đọc thật sự ném ngoại lệ khi gọi add. Gợi ý: một Set chuyên giữ thứ tự thêm vào và một Set chuyên sắp xếp, rồi đưa chúng về List.

Mức Thử thách (tuỳ chọn)

Bài 5. Đo chi phí theo kích thước. Dựa vào LookupCost, chạy phép đo với 1000, 10000 và 100000 khoá. Kết quả mong đợi: số lần equals của danh sách bằng đúng kích thước, của tập băm luôn là 1. Tiêu chí nghiệm thu: bảng ba dòng, và 2 đến 3 câu giải thích vì sao đường cong của hai cấu trúc khác nhau. Gợi ý: đưa phần nạp và đo vào một hàm nhận n.

Tự kiểm tra (Retrieval Practice)

Trả lời bằng trí nhớ, không xem lại bài. Mỗi câu ghi rõ nó kiểm tra mục tiêu nào trong bốn mục tiêu ở đầu bài.

Câu 1 (nhớ lại, mục tiêu 1). Kể tên ba nhánh con của Collection, và nói vì sao Map không nằm trong đó.

Câu 2 (dự đoán kết quả code, mục tiêu 2). Đoạn sau in ra gì?

Set<String> s = new LinkedHashSet<>();
System.out.println(s.add("Tea") + " " + s.add("Latte") + " " + s.add("Tea") + " " + s);

Câu 3 (dự đoán trạng thái sau nhiều bước, mục tiêu 4). Sau các dòng sau, view và copy đang chứa gì?

List<String> src = new ArrayList<>(List.of("A", "B"));
List<String> view = Collections.unmodifiableList(src);
List<String> copy = List.copyOf(src);
src.add("C");
src.remove("A");

Câu 4 (tìm lỗi, mục tiêu 2 và 3). Vòng lặp dưới đây nhận 50000 mã đơn mới vào danh sách đã có 200000 mã, và chạy rất chậm. Chỉ ra chỗ chậm, giải thích bằng số lần equals, và sửa.

List<String> ids = new ArrayList<>(existingIds);
for (String incoming : newIds) {
    if (!ids.contains(incoming)) {
        ids.add(incoming);
    }
}

Câu 5 (giải thích cho bạn chưa học, mục tiêu 3). Bạn của bạn hỏi: "Vì sao tìm trong HashSet gần như tức thì còn tìm trong ArrayList thì lâu?" Giải thích bằng hình ảnh tìm sách trên kệ.

Điều cần nhớ

• Collection có ba nhánh List, Set, Queue, còn Map đứng riêng vì lưu cặp khoá và giá trị (mục tiêu 1).
• Chọn cấu trúc theo câu hỏi hay hỏi nhất: vị trí thì List, có chưa thì Set, tra theo khoá thì Map (mục tiêu 2).
• ArrayList.contains đi qua từng phần tử, HashSet.contains nhảy tới một ngăn nhờ mã băm: đo được 100000 lần so với 1 lần (mục tiêu 3).
• List.of và List.copyOf không đổi theo dữ liệu gốc, còn unmodifiableList chỉ là khung nhìn nên vẫn đổi theo (mục tiêu 4).

Cheat sheet một trang.

Cách đọc hình: mỗi hàng là một việc bên trái và công cụ nên chọn bên phải. Đọc theo hàng ngang. Dòng ghi chú cuối hình nhắc: không chắc thì cứ bắt đầu bằng ArrayList, HashSet hoặc HashMap, rồi chỉ đổi khi một câu hỏi buộc bạn đổi.

Câu hỏi để dành cho ngày mai: nếu HashSet tìm nhanh nhờ mã băm, chuyện gì xảy ra khi hai đơn có nội dung giống hệt nhau mà hashCode lại khác nhau? Hãy nghĩ trước khi sang bài sau.

Đào sâu

Phần này dành cho bạn tò mò. Bỏ qua cũng không thiếu gì ở trên.

Bên trong. OpenJDK cài HashSet bằng một HashMap bên trong: mỗi phần tử của tập là một khoá, còn giá trị chỉ là một đối tượng đánh dấu dùng chung. Đây là chi tiết cài đặt, không nằm trong hợp đồng của Set, nên đừng viết code phụ thuộc vào nó. Nhờ vậy, mọi điều bạn học về mã băm ở Set đều đúng cho khoá của Map.

So với lựa chọn khác. TreeSet và TreeMap không dùng mã băm mà dùng thứ tự so sánh, nên số lần so sánh tăng chậm theo kích thước chứ không phẳng như tập băm. Đổi lại, chúng cho bạn thứ tự và các câu hỏi lân cận (phần tử nhỏ nhất, phần tử gần nhất). Bài 43 sẽ nói về thứ tự này.

Hiểu lầm nâng cao. Nhiều người thấy new HashSet<>(List.of(3, 1, 2)) in ra [1, 2, 3] rồi kết luận HashSet tự sắp xếp. Kết quả đó đúng với JDK 17.0.15 [Đã chạy], nhưng chỉ vì số nguyên nhỏ có mã băm bằng chính nó và rơi vào các ngăn liền nhau. Với chuỗi hay số lớn, thứ tự trông ngẫu nhiên [Có thể khác nhau], và Java không hứa bất cứ điều gì.

Giới hạn của bài. Bài này chưa nói về PriorityQueue, ArrayDeque, các tập hợp dùng chung giữa nhiều luồng (ConcurrentHashMap), và cách HashMap xử lý khi nhiều khoá dồn vào một ngăn. Số liệu trong bài thuộc JDK 17.0.15.

Đọc thêm (tài liệu chính thống, Java SE 17):

• The Java Tutorials: Collections Introduction
• Javadoc: java.util.Collection
• Javadoc: java.util.Map
• Javadoc: java.util.Collections

Bài tiếp theo

Bài 41 đi sâu vào List: ArrayList và LinkedList, và vì sao chèn hoặc xoá ở giữa làm các ghế dồn ô. Sau đó, bài 42 quay lại hai câu hỏi mà List làm chậm là "đơn này đã có chưa" và "khách số 7 gọi gì".

Mini-dự án nối tiếp: ở bài 41, màn hình bếp có class OrderBoard bọc một ArrayList. Hãy nhớ lại các lệnh Kitchen bạn vừa viết, vì bài 42 sẽ thêm Set để chặn đơn trùng và Map để tra đơn theo khách vào chính OrderBoard đó.

Lời giải và đáp án

Hãy thử xong rồi mới đọc phần này.

Lời giải Làm cùng mình. Thay các dòng // TODO bằng những dòng dưới đây, ghép lại chạy ra đúng năm dòng step [Đã chạy, JDK 17.0.15]:

queue.add("Mocha");
queue.add("Latte");

menu.addAll(queue);  // Latte trùng nên menu chỉ có 2 phần tử

byCustomer.put(7, "Latte");
byCustomer.put(8, "Mocha");
byCustomer.put(9, "Latte");  // giá trị trùng thì được, khoá trùng thì không

first = seen.add("A100");  // lần đầu: true
again = seen.add("A100");  // đã có: false

List<String> board = List.copyOf(queue);  // bản sao chỉ đọc
queue.add("Tea");                         // queue thành 4, board vẫn 3

Lời giải Bài 1. [Suy luận, khớp với kết quả chạy thật]

Dòng c.put(1, "Tea") thay giá trị của khoá có sẵn nên c.size() không đổi. Dòng b.add("Mocha") trả về false vì Mocha đã có, nên b.size() không đổi.

Lời giải Bài 2. (a) ArrayList: cần thứ tự và cho phép trùng. (b) HashSet: câu hỏi chính là "có chưa". (c) HashMap: tra giá trị theo khoá là tên khách. (d) TreeSet: không trùng và luôn xếp theo abc.

Lời giải Bài 3. [Đã chạy, in ra [Latte, Mocha, Tea]]

List<String> menu = new ArrayList<>(List.of("Latte", "Mocha"));
menu.add("Tea");

List.of tạo danh sách bất biến nên add ném UnsupportedOperationException. Bọc vào new ArrayList<>(...) tạo ra một danh sách mới sửa được, chép sẵn hai đồ uống ban đầu.

Lời giải Bài 4. [Đã chạy, ba dòng khớp với kết quả mong đợi]

List<String> unique = new ArrayList<>(new LinkedHashSet<>(orders));  // bỏ trùng, giữ thứ tự
List<String> sorted = new ArrayList<>(new TreeSet<>(orders));        // bỏ trùng, sắp theo abc
List<String> frozen = List.copyOf(unique);                           // bản sao chỉ đọc

Bọc frozen.add("X") trong try và bắt UnsupportedOperationException để in dòng cuối.

Gợi ý lời giải Bài 5. Đưa phần nạp và đo của LookupCost vào hàm static void measure(int n) rồi gọi với ba giá trị. Mỗi lần đo, đặt calls = 0 trước dòng contains. Kết quả mong đợi: danh sách gọi equals đúng n lần, tập băm gọi 1 lần [Đã chạy ở n bằng 100000, giá trị khác suy luận từ cùng cơ chế]. Đường cong của danh sách là đường thẳng đi lên theo n, của tập băm là đường nằm ngang.

Đáp án Tự kiểm tra.

1. Ba nhánh là List, Set, Queue. Map không nằm trong Collection vì nó lưu cặp khoá và giá trị, nên các thao tác chung như add(x) và contains(x) không hợp với nó. Kiểm tra mục tiêu 1.
2. In ra true true false [Tea, Latte] [Đã chạy]. Lần thêm Tea thứ hai trả về false vì Tea đã có, và LinkedHashSet giữ thứ tự thêm vào. Kiểm tra mục tiêu 2.
3. view là [B, C] và copy là [A, B] [Suy luận]. Khung nhìn đi theo src nên thấy cả hai thay đổi, bản sao đã chụp lại từ trước. Kiểm tra mục tiêu 4.
4. Chỗ chậm là ids.contains(incoming): mỗi lần quét tới 200000 phần tử. Với 50000 mã mới là cỡ mười tỷ lần equals. Sửa bằng một LinkedHashSet<String> và dùng if (ids.add(incoming)) để vừa kiểm tra vừa thêm, mỗi lần chỉ khoảng 1 lần equals [Suy luận]. Kiểm tra mục tiêu 2 và 3.
5. Danh sách giống như lật từng cuốn trên kệ cho tới khi gặp cuốn cần tìm. Tập băm giống như có sổ ghi sẵn cuốn sách nằm ở kệ số mấy: bạn đi thẳng tới kệ đó rồi chỉ cần nhìn xem đúng cuốn chưa. Kiểm tra mục tiêu 3.