Set và Map

Tình huống mở đầu

Cuối bài trước, màn hình bếp quán Cà Phê Gió đã có danh sách đơn gọn gàng. Giờ cao điểm, khách bấm nhầm hai lần nên cùng mã đơn A100 vào bếp hai lần, và barista pha hai ly Latte cho một khách. Chủ quán còn muốn một việc nữa: nhìn số khách 7 là biết ngay khách đó đang chờ gì, không cần đọc cả danh sách 300 đơn.

Hai việc đều cần một cấu trúc khác List. Bạn thử viết bằng List thì chạy được, nhưng mỗi lần hỏi lại quét hết danh sách. Còn nếu dùng loại khác, bạn gặp một lỗi kỳ lạ: hai đơn giống hệt nhau mà tập hợp vẫn coi là hai đơn. Vậy máy so sánh hai đơn bằng cách nào, và nó dựa vào những gì?

Ôn nhanh bài trước: List.of("Latte").add("Tea") ném lỗi gì, và vì sao?

Đáp án: UnsupportedOperationException, vì List.of tạo danh sách bất biến. Muốn sửa được, bọc nó vào new ArrayList<>(...).

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

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

• Dùng Set.add (trả boolean) để chặn đơn trùng, và dùng put, get, getOrDefault, containsKey của Map để tra đơn theo khách.
• Giải thích được vì sao HashSet và HashMap chọn ngăn bằng hashCode trước rồi mới gọi equals, nên một lớp chỉ ghi đè equals làm kết quả sai.
• Viết được equals và hashCode nhất quán cho lớp đơn hàng bằng Objects.hash.
• Chọn được HashMap, LinkedHashMap hay TreeMap theo yêu cầu thứ tự duyệt.

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)

Trước khi vào chi tiết, hãy xem một đơn mới đi qua màn hình bếp như thế nào.

Cách đọc hình: đi từ trái sang phải. Đơn mới A100 gặp ô Set ở giữa. Nếu add trả về false (mã đã có), đơn bị từ chối theo nét đứt lên ô đỏ. Nếu trả về true, đơn đi tiếp sang hai ô vàng bên phải: List giữ thứ tự hàng chờ, Map ghi khách số 7 gọi Latte. Mỗi ô đều có chữ, màu chỉ là tín hiệu phụ.

Bài này nối thẳng từ bài 41: bạn vẫn giữ OrderBoard, chỉ thêm một cổng Set ở cửa và một sổ tra cứu Map ở bên cạnh. Ẩn dụ xuyên suốt là một cuốn sổ ở quầy: Set là cột "đã nhận đơn mã nào rồi", Map là sổ tra "khách số mấy gọi gì". Chỗ ẩn dụ không còn đúng: sổ giấy thì bạn dò từng dòng, còn HashSet và HashMap nhảy tới đúng chỗ nhờ một con số tính từ nội dung, và bài này giải thích con số đó.

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: Set, tập hợp không trùng

Set là nhóm phần tử không có hai phần tử giống nhau. Phương thức add của nó trả về boolean: true nếu phần tử mới được thêm, false nếu phần tử đã có và tập không đổi. Trong cuốn sổ ở quầy, đó là cột mã đơn: ghi thêm mã đã có thì không thêm dòng nào.

Cách đọc hình: ba ô bên trái là ba lệnh add theo thứ tự trên xuống dưới. Ô Set ở giữa chứa A100 và A101. Ba ô bên phải là giá trị trả về: true, true, rồi false cho lệnh thêm lại A100. Dòng ghi chú cuối nhắc rằng không cần gọi contains riêng.

Nhờ giá trị trả về, if (seen.add(id)) vừa kiểm tra vừa thêm trong một dòng. Nếu bạn viết if (!seen.contains(id)) seen.add(id) thì máy phải tìm hai lần.

Khái niệm 2: Map, sổ tra theo khoá

Map lưu từng cặp khoá (key) và giá trị (value). Mỗi khoá chỉ có một giá trị, giá trị thì có thể trùng nhau. put(k, v) ghi cặp và trả về giá trị cũ của khoá đó (hoặc null nếu khoá mới). get(k) trả về giá trị, hoặc null nếu không có khoá. getOrDefault(k, d) trả về d thay cho null. containsKey(k) hỏi có khoá không.

Cách đọc hình: cột trái là ba lệnh put. Hai lệnh dùng khoá 7 cùng nối vào ô Key 7, ghi chú "Latte, then Tea" cho thấy giá trị bị thay. Lệnh khoá 8 nối vào ô Key 8. Ô get(9) bên phải không nối với ô nào vì không có khoá 9. Hai khoá nên size là 2.

Concept Check 1. byCustomer đang có cặp 7 và Latte. Chạy String old = byCustomer.put(7, "Tea");. Điều gì đúng?

• A. old là null, vì khoá 7 bị xoá rồi thêm lại như một khoá mới.
• B. old là Tea, vì put trả về chính giá trị vừa mới ghi vào.
• C. old là Latte, get(7) từ giờ cho Tea, và số cặp không đổi.
• D. Ném IllegalStateException, vì khoá 7 đã tồn tại trong Map.

Đáp án: C. put trả về giá trị cũ của khoá, nên bạn biết đơn nào vừa bị thay. A sai vì Map không xoá rồi thêm lại, nó thay giá trị tại chỗ. B nhầm put với get. D sai vì ghi đè khoá cũ là cách dùng bình thường của Map, không phải lỗi.

Khái niệm 3: hashCode quyết định ngăn, equals quyết định bằng nhau

Đây là khái niệm quan trọng nhất của bài. hashCode là một con số int suy ra từ nội dung đối tượng. HashSet và HashMap dùng nó để chọn một ngăn (bucket), rồi chỉ nhìn vào ngăn đó và gọi equals để xác nhận. Vì vậy hai đơn bằng nhau theo equals bắt buộc phải có cùng hashCode. Đây là hợp đồng của Java. Ẩn dụ: số kệ trong sổ ghi sẵn cho mỗi cuốn sách. Hai cuốn giống nhau mà ghi hai số kệ khác nhau thì bạn không bao giờ tìm ra cuốn kia.

Chương trình HashContract có hai lớp đơn: BadOrder chỉ có equals, GoodOrder có thêm hashCode. Phần đầu của BadOrder là:

static class BadOrder {
    final int customer;
    final String drink;

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof BadOrder)) {
            return false;
        }
        BadOrder other = (BadOrder) o;
        return customer == other.customer && drink.equals(other.drink);  // so sánh nội dung
    }
}

GoodOrder giống hệt, chỉ thêm một phương thức:

@Override
public int hashCode() {
    return Objects.hash(customer, drink);  // đúng hai trường mà equals dùng
}

Và phần đo, chạy với từng lớp:

Set<BadOrder> bad = new HashSet<>();
bad.add(new BadOrder(7, "Latte"));  // bản sao dưới đây có mã băm mặc định khác nên tìm ở ngăn khác
System.out.println("bad:  contains " + bad.contains(new BadOrder(7, "Latte")) + ", add again " + bad.add(new BadOrder(7, "Latte")) + ", size " + bad.size());

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

bad:  contains false, add again true, size 2
good: contains true, add again false, size 1

Dòng bad phụ thuộc vào mã băm theo danh tính của JVM. Hai đối tượng khác nhau trùng cả mã băm là chuyện có thể xảy ra về lý thuyết nhưng cực kỳ hiếm, nên mình ghi nhận kết quả này như kết quả thường gặp [Có thể khác nhau, rất hiếm].

Cách đọc hình: hàng trên là GoodOrder: có hashCode nhất quán nên bản sao vào cùng ngăn, equals xác nhận và contains trả true. Hàng dưới là BadOrder: mã băm theo danh tính nên bản sao vào ngăn khác, equals không được gọi, contains trả false và size thành 2. Cả hai hàng đều có chữ ghi kết quả.

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

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

Concept Check 2. BadOrder chỉ có equals. Sau bad.add(new BadOrder(7, "Latte")), câu bad.contains(new BadOrder(7, "Latte")) trả về gì, và vì sao?

• A. false, vì HashSet đi vào ngăn theo mã băm mặc định của đối tượng mới và không gặp đơn đã lưu, nên equals chưa được gọi.
• B. true, vì equals nói hai đơn bằng nhau nên tập hợp đủ thông tin để nhận ra đơn đã lưu.
• C. Lỗi biên dịch, vì Java bắt buộc mọi lớp ghi đè equals phải ghi đè luôn hashCode.
• D. NullPointerException, vì ngăn của bản sao chưa được tạo nên HashSet không so sánh được.

Đáp án: A. B là hiểu lầm hay gặp nhất: equals chỉ được gọi bên trong ngăn mà mã băm trỏ tới. C sai vì Java không bắt buộc, trình biên dịch vẫn biên dịch bình thường và lỗi chỉ lộ ra khi chạy. D sai vì ngăn rỗng chỉ là chưa có phần tử, không gây ngoại lệ.

Khái niệm 4: chọn lớp Map theo thứ tự duyệt

Map có ba lớp thường dùng, khác nhau ở thứ tự khi duyệt. HashMap không hứa thứ tự nào. LinkedHashMap duyệt theo thứ tự khoá được thêm lần đầu. TreeMap duyệt theo thứ tự sắp xếp của khoá. Ẩn dụ: sổ tra có thể xếp tuỳ ý, xếp theo lúc ghi, hoặc xếp theo abc.

Map<String, Integer> linked = new LinkedHashMap<>();
Map<String, Integer> sorted = new TreeMap<>();
for (String drink : new String[] {"Tea", "Latte", "Mocha"}) {
    linked.put(drink, drink.length());  // nhớ thứ tự thêm
    sorted.put(drink, drink.length());  // xếp theo abc
}

Kết quả [Đã chạy, JDK 17.0.15], đã bỏ dòng in thứ tự của HashMap vì không được bảo đảm:

LinkedHashMap {Tea=3, Latte=5, Mocha=5}
TreeMap       {Latte=5, Mocha=5, Tea=3}
HashMap size  3

Lần put lại một khoá đã có không đổi vị trí của khoá đó trong LinkedHashMap, chỉ đổi giá trị [Đã chạy, {a=3, b=2} sau put a, put b, put a].

Cách đọc hình: ô bên trái là dữ liệu vào theo thứ tự Tea, Latte, Mocha. Ô LinkedHashMap giữ nguyên thứ tự đó, ô TreeMap xếp theo abc, ô HashMap ghi rõ "order not promised". Dòng ghi chú nhắc việc put lại khoá cũ.

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 bài này: cổng Set và sổ tra Map.

DeskDemo.java

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

public class DeskDemo {
    public static void main(String[] args) {
        // Set bỏ trùng: add trả về true nếu mã mới, false nếu mã đã có
        Set<String> seen = new HashSet<>();
        System.out.println("add: " + seen.add("A100") + " " + seen.add("A101") + " " + seen.add("A100") + ", size " + seen.size());

        // Map: put trả về giá trị cũ của khoá (null nếu khoá mới)
        Map<Integer, String> byCustomer = new HashMap<>();
        System.out.println("put: " + byCustomer.put(7, "Latte") + " " + byCustomer.put(8, "Mocha") + " " + byCustomer.put(7, "Tea"));
        // get thiếu khoá cho null, getOrDefault cho giá trị dự phòng
        System.out.println("get: " + byCustomer.get(7) + " " + byCustomer.get(9) + " " + byCustomer.getOrDefault(9, "none"));
        System.out.println("has 8: " + byCustomer.containsKey(8) + ", size " + byCustomer.size());
    }
}

Predict: hãy dừng lại, lấy giấy nháp và đoán bốn dòng in ra. Đặc biệt: ba giá trị trả về của add là gì, và put(7, "Tea") lần hai trả về gì? Đoán xong rồi hãy đọc tiếp.

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

add: true true false, size 2
put: null null Latte
get: Tea null none
has 8: true, size 2

Đọ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 hai 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 Set và Map rồi nói đúng giá trị trả về và kích thước 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. Cần in bảng giá theo thứ tự abc của tên đồ uống, mỗi lần chạy đều giống nhau. Chọn lớp Map nào?

• A. HashMap, vì khoá là chuỗi nên chúng tự được in theo thứ tự abc.
• B. LinkedHashMap, vì nó tự sắp xếp khoá theo abc mỗi khi bạn gọi put.
• C. HashMap hoặc LinkedHashMap đều được, vì cả hai đều sắp xếp khi duyệt.
• D. TreeMap, vì nó luôn giữ khoá theo thứ tự sắp xếp, kể cả khi thêm khoá mới.

Đáp án: D. A sai vì HashMap không hứa thứ tự nào, kể cả với chuỗi. B nhầm: LinkedHashMap chỉ nhớ thứ tự thêm vào, không sắp xếp. C sai vì cả hai đều không sắp xếp. Chỉ TreeMap dùng thứ tự của khoá.

Concept Check 4. Hai cách chặn mã đơn trùng: cách một là if (!seen.contains(id)) { seen.add(id); }, cách hai là if (seen.add(id)) { ... }. Điều nào đúng?

• A. Hai cách cho kết quả khác nhau, vì add không trả về giá trị nên không dùng được trong if.
• B. Hai cách cho cùng kết quả, nhưng cách một tìm trong tập hai lần còn cách hai chỉ tìm một lần.
• C. Hai cách cho cùng kết quả, và cách một nhanh hơn vì contains luôn rẻ hơn add.
• D. Hai cách cho kết quả khác nhau, vì contains xét hashCode còn add chỉ xét equals.

Đáp án: B. add trả về true khi mã mới nên vừa kiểm tra vừa ghi trong một lần tìm. A sai vì add của Set trả về boolean. C sai vì contains cũng phải tìm giống add. D sai vì cả hai đều chọn ngăn bằng hashCode rồi so bằng equals.

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

Bạn sẽ dựng dần class Desk 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 Desk.java rồi chạy bằng java Desk.java.

Bước 1: chặn mã đơn trùng.

import java.util.*;

public class Desk {
    public static void main(String[] args) {
        Set<String> seen = new HashSet<>();
        boolean a = seen.add("A100");
        boolean b = false;
        boolean c = false;
        // TODO 1: thêm tiếp "A101", rồi thêm lại "A100", lưu kết quả vào b và c
        System.out.println("step 1: " + a + " " + b + " " + c);
    }
}

Chạy xong bạn sẽ thấy: step 1: true true false.

Bước 2: ghi khách và đồ uống. Thêm dưới dòng in của bước 1:

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

Chạy xong bạn sẽ thấy: step 2: Latte 2.

Vẽ ra giấy: kẻ hai cột khoá và giá trị, điền hai cặp. Đối chiếu: get(7) cho Latte, size bằng 2 vì có hai khoá.

Bước 3: đổi đơn của khách và biết đơn cũ.

        String old = null;
        // TODO 3: khách 7 đổi sang "Tea", lưu đơn cũ của khách 7 vào old
        System.out.println("step 3: " + old + " " + byCustomer.get(7) + " " + byCustomer.size());

Chạy xong bạn sẽ thấy: step 3: Latte Tea 2. Vẽ ra giấy: vẽ lại hai cặp trước và sau bước này. Đối chiếu: chỉ ô giá trị của khoá 7 đổi, số cặp vẫn là 2. Gợi ý: giá trị cũ là thứ put trả về.

Bước 4: tra khách không có đơn. Bạn tự quyết cách viết.

        String none = null;
        // TODO 4: lấy đơn của khách 9, nếu không có thì dùng chữ "none"
        System.out.println("step 4: " + none + " " + byCustomer.containsKey(9));

Chạy xong bạn sẽ thấy: step 4: none false. Gợi ý: có một phương thức get kèm giá trị dự phòng.

Bước 5: bản thực đơn xếp theo abc.

        // TODO 5: tạo Map price rỗng sắp theo abc, ghi Tea 30, Latte 45, Mocha 50 rồi in price
        System.out.println("step 5: " + price);

Chạy xong bạn sẽ thấy: step 5: {Latte=45, Mocha=50, Tea=30}. Gợi ý: chọn lớp Map theo yêu cầu thứ tự, rồi tự khai báo biến price đứng trước dòng in. Lời giải đầy đủ nằm ở cuối bài.

Bạn vừa làm được: tự dựng chương trình dùng Set chặn trùng và Map ghi, đổi, tra đơn theo khách. Toàn bộ mã nguồn của bài cũng nằm trong thư mục 12-collections/03-set-map 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 với Set và Map. 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].

Lỗi thứ nhất và thứ hai cùng một gốc: mã băm của khoá phải ổn định và nhất quán với equals. Hình dưới đặt mô hình sai và đúng cạnh nhau.

Cách đọc hình: hàng trên màu đỏ là mô hình sai: tin rằng tập hợp so sánh mọi phần tử bằng equals nên dự đoán đơn trùng bị chặn và size bằng 1. Hàng dưới màu lục là mô hình đúng: hashCode chọn ngăn trước, nên khi thiếu hashCode bản sao lọt qua và size bằng 2. Dòng ghi chú cuối nhắc viết equals và hashCode cùng nhau.

Bạn vừa làm được: đọc bốn lỗi phổ biến của Set và Map và nói được nguyên nhân bằng lời thường.

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:

Set<String> s = new HashSet<>();
s.add("A1"); s.add("A2"); s.add("A1"); s.remove("A2"); s.add("A3");  // A1 lần hai đã có
Map<String, Integer> m = new HashMap<>();
m.put("x", 1); m.put("y", 2); m.put("x", 3); m.remove("y");
m.put("z", m.getOrDefault("y", 0) + 5);  // y đã bị xoá nên getOrDefault cho 0

Điền bảng: mỗi lệnh add, put, remove là một dòng, với các cột giá trị trả về, nội dung s hoặc m sau dòng đó (không cần thứ tự), và size. Kết quả mong đợi: s cuối cùng là A1, A3, m cuối cùng là x=3, z=5. Tiêu chí nghiệm thu: bảng của bạn đúng với kết quả chạy thật, và bạn chỉ ra được những dòng không làm size đổi. Gợi ý: getOrDefault("y", 0) chạy sau khi y đã bị xoá.

Bài 2. Chọn lớp theo thứ tự. Dữ liệu vào: thứ tự put là Tea, Latte, Mocha. Viết ra kết quả duyệt khoá khi dùng LinkedHashMap và khi dùng TreeMap, rồi nói với HashMap bạn dự đoán được gì. Kết quả mong đợi: hai danh sách khoá khác nhau và một câu trả lời trung thực cho HashMap. Tiêu chí nghiệm thu: bạn nêu được vì sao không nên in thứ tự HashMap ra làm đáp án cố định. Gợi ý: xem lại bảng khái niệm 4.

Bài 3. Sửa lỗi hợp đồng. Dữ liệu vào: lớp Ticket có hai trường code (chuỗi) và seat (số nguyên), chỉ ghi đè equals so sánh cả hai trường. Chạy set.add(new Ticket("A1", 3)) rồi set.contains(new Ticket("A1", 3)) trả false. Sửa để contains trả true và add lần hai trả false. Tiêu chí nghiệm thu: thêm đúng một phương thức, dùng đúng hai trường của equals. Gợi ý: Objects.hash nhận nhiều tham số.

Mức Vận dụng

Bài 4. Nâng cấp OrderBoard cho màn hình bếp. Giữ class OrderBoard của bài 41 (bọc một ArrayList) và thêm hai thứ: một Set mã đơn đã nhận và một Map từ số khách tới đồ uống mới nhất của họ. Thêm các phương thức sau:

Dữ liệu vào là hàm main sau:

OrderBoard board = new OrderBoard();
System.out.println(board.place("A100", 7, "Latte"));
System.out.println(board.place("A101", 8, "Mocha"));
System.out.println(board.place("A100", 9, "Tea"));
System.out.println(board.drinkOf(7) + " " + board.drinkOf(9) + " " + board.size());

Kết quả mong đợi:

true
true
false
Latte none 2

Tiêu chí nghiệm thu: bốn dòng khớp từng ký tự, và đơn bị chặn không để lại dấu vết nào trong danh sách hay Map. Gợi ý: một lệnh add của Set vừa kiểm tra vừa ghi.

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

Bài 5. Đếm đơn theo đồ uống. Dữ liệu vào: danh sách Latte, Mocha, Latte, Tea. Đếm số đơn của từng đồ uống bằng một Map, dùng phương thức merge, và in theo thứ tự abc. Kết quả mong đợi: {Latte=2, Mocha=1, Tea=1}. Tiêu chí nghiệm thu: không có vòng if kiểm tra khoá đã có chưa, và thứ tự in cố định giữa các lần chạy. Gợi ý: merge(key, 1, Integer::sum) đặt 1 nếu khoá chưa có, nếu có rồi thì cộng giá trị cũ với 1. Chọn lớp Map theo yêu cầu thứ tự.

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). Set.add trả về gì khi phần tử đã có, và Map.put trả về gì khi khoá đã có?

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

Map<String, Integer> m = new TreeMap<>();
m.put("b", 1);
m.put("a", 2);
m.put("b", 3);
System.out.println(m + " " + m.size() + " " + m.get("c"));

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

Set<Integer> ts = new TreeSet<>(List.of(5, 1, 3));
ts.add(3);
ts.add(2);
ts.remove(5);

Câu 4 (tìm lỗi, mục tiêu 2 và 3). Đoạn sau in false dù người viết mong đợi true. Chỉ ra lỗi và sửa.

class Point {
    final int x;
    final int y;
    Point(int x, int y) { this.x = x; this.y = y; }
    @Override
    public boolean equals(Object o) {
        return o instanceof Point && ((Point) o).x == x && ((Point) o).y == y;
    }
}
Set<Point> s = new HashSet<>();
s.add(new Point(1, 2));
System.out.println(s.contains(new Point(1, 2)));

Câu 5 (giải thích cho bạn chưa học, mục tiêu 2). Bạn của bạn hỏi: "Hai đơn giống hệt nhau thì equals đã nói chúng bằng nhau rồi, sao HashSet còn cần hashCode?" Giải thích bằng hình ảnh số kệ sách.

Điều cần nhớ

• Set.add trả true khi phần tử mới, false khi trùng; Map.put trả giá trị cũ hoặc null, get thiếu khoá cho null (mục tiêu 1).
• HashSet và HashMap chọn ngăn bằng hashCode trước rồi mới gọi equals trong ngăn đó (mục tiêu 2).
• Ghi đè equals thì phải ghi đè hashCode bằng cùng các trường, ví dụ Objects.hash(...) (mục tiêu 3).
• HashMap không hứa thứ tự, LinkedHashMap theo thứ tự thêm, TreeMap theo thứ tự sắp xếp của khoá (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à thao tác nên dùng bên phải, kèm điều nó trả về. Đọc theo hàng ngang. Dòng ghi chú cuối nhắc viết equals và hashCode cùng nhau.

Câu hỏi để dành cho ngày mai: TreeSet và TreeMap xếp khoá theo thứ tự. Nhưng làm sao Java biết đơn Latte đứng trước hay sau đơn Mocha, hoặc đơn của khách 7 đứng trước hay sau đơn của khách 8? 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 HashMap. Javadoc của HashMap nêu hệ số tải mặc định là 0,75, nghĩa là khi số cặp vượt mức đó so với số ngăn thì bảng được mở rộng. Mã nguồn OpenJDK còn cho thấy khi một ngăn có quá nhiều khoá, ngăn đó được đổi sang dạng cây để tìm nhanh hơn. Đây là chi tiết cài đặt của OpenJDK, đừng viết code phụ thuộc vào nó. Điều bạn cần nhớ từ chi tiết này là: mã băm phân bố đều thì mỗi ngăn gần như chỉ có một khoá, và đó là lý do tra cứu gần như tức thì.

So với lựa chọn khác. TreeMap và TreeSet không dùng mã băm mà dùng thứ tự so sánh khoá, nên không cần hashCode mà cần khoá so sánh được. Đó là chủ đề của bài sau. Đổi lại, chúng cho bạn thứ tự và các câu hỏi lân cận như khoá nhỏ nhất.

Hiểu lầm nâng cao. Nhiều người nghĩ chỉ cần equals và hashCode đúng lúc put là xong. Thực ra chúng phải đúng suốt thời gian đối tượng làm khoá. Trong một lần thử, khi bạn put(cup, 1) rồi đổi cup.name từ Latte sang Mocha, cả get(cup) lẫn get(new Cup("Latte")) đều trả null và size vẫn là 1 [Đã chạy, JDK 17.0.15]. Khoá lạc ngăn nên không ai tìm ra nó nữa.

Giới hạn của bài. Bài này chưa nói về duyệt Map qua entrySet, computeIfAbsent, EnumMap, ConcurrentHashMap, và bộ nhớ đệm dùng LinkedHashMap. HashSet của JDK 17.0.15 in số nguyên nhỏ theo thứ tự tăng chỉ do trùng hợp, không phải lời hứa.

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

• The Java Tutorials: The Set Interface
• The Java Tutorials: The Map Interface
• Javadoc: java.util.HashMap
• Javadoc: java.util.Objects

Bài tiếp theo

Bài sau là Iterator, Comparable và Comparator: cách duyệt an toàn và cách dạy Java sắp xếp đơn hàng theo ý bạn, kể cả cho TreeSet và TreeMap vừa nhắc ở trên.

Mini-dự án nối tiếp: ở bài sau, màn hình bếp sẽ sắp các đơn theo độ ưu tiên và theo tên khách bằng Comparator. Hãy giữ lại OrderBoard có Set và Map bạn vừa viết làm điểm xuất phát.

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]:

b = seen.add("A101");
c = seen.add("A100");  // đã có nên false

byCustomer.put(7, "Latte");
byCustomer.put(8, "Mocha");

old = byCustomer.put(7, "Tea");  // put trả về giá trị cũ

none = byCustomer.getOrDefault(9, "none");  // khoá 9 không có

Map<String, Integer> price = new TreeMap<>();  // luôn giữ khoá theo abc
price.put("Tea", 30);
price.put("Latte", 45);
price.put("Mocha", 50);

Lời giải Bài 1. [Suy luận, khớp với kết quả chạy thật [A1, A3] {x=3, z=5}]

Hai dòng không làm size đổi là s.add("A1") lần hai (đã có) và m.put("x", 3) (thay giá trị khoá có sẵn). Dòng cuối: getOrDefault("y", 0) cho 0 vì y đã bị xoá, nên giá trị ghi vào z là 5.

Lời giải Bài 2. [Đã chạy] LinkedHashMap duyệt khoá theo thứ tự Tea, Latte, Mocha. TreeMap duyệt khoá theo thứ tự Latte, Mocha, Tea. Với HashMap bạn chỉ chắc chắn có ba khoá, còn thứ tự [Có thể khác nhau] giữa các phiên bản và dữ liệu, nên không viết nó làm đáp án cố định.

Lời giải Bài 3. [Đã chạy, contains trả true và add lần hai trả false]

@Override
public int hashCode() {
    return Objects.hash(code, seat);  // đúng hai trường mà equals dùng
}

Objects.hash(code, seat) dùng đúng hai trường mà equals dùng, nên hai vé bằng nhau luôn ra cùng mã băm, rơi vào cùng ngăn, và equals được gọi để xác nhận.

Lời giải Bài 4. [Đã chạy, bốn dòng khớp với kết quả mong đợi] Thêm hai trường seenIds (một HashSet<String>) và byCustomer (một HashMap<Integer, String>) vào OrderBoard, rồi viết hai phương thức:

public boolean place(String id, int customer, String drink) {
    if (!seenIds.add(id)) {  // false nghĩa là mã đã có
        return false;
    }
    orders.add(drink);
    byCustomer.put(customer, drink);  // đơn mới nhất ghi đè đơn cũ
    return true;
}

public String drinkOf(int customer) {
    return byCustomer.getOrDefault(customer, "none");  // khách chưa có đơn thì none
}

Lời giải Bài 5. [Đã chạy, in ra {Latte=2, Mocha=1, Tea=1}]

Dùng Map<String, Integer> count = new TreeMap<>(); rồi trong vòng for gọi count.merge(drink, 1, Integer::sum);.

merge đặt 1 cho khoá mới, và với khoá đã có thì cộng giá trị cũ với 1 qua Integer::sum. TreeMap cho thứ tự abc cố định. Cú pháp Integer::sum sẽ được giải thích ở bài Lambda, bây giờ bạn chỉ cần dùng nó như một khuôn mẫu.

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

1. Set.add trả false khi phần tử đã có và tập không đổi. Map.put trả giá trị cũ của khoá đó (và thay bằng giá trị mới). Kiểm tra mục tiêu 1.
2. In ra {a=2, b=3} 2 null [Đã chạy]. TreeMap xếp khoá theo abc, put("b", 3) thay giá trị của b, hai khoá nên size là 2, khoá c không có nên get cho null. Kiểm tra mục tiêu 1 và 4.
3. ts chứa [1, 2, 3] [Đã chạy]. Từ [1, 3, 5], add(3) không đổi, add(2) thành [1, 2, 3, 5], remove(5) còn [1, 2, 3]. Kiểm tra mục tiêu 1.
4. Lỗi: Point chỉ ghi đè equals mà không ghi đè hashCode, nên bản sao lọt vào ngăn khác. Sửa bằng cách thêm public int hashCode() { return Objects.hash(x, y); } thì contains trả true [Suy luận]. Kiểm tra mục tiêu 2 và 3.
5. Hãy tưởng tượng thủ thư ghi sẵn số kệ cho mỗi cuốn dựa trên nội dung của nó. Có hai cuốn giống nhau mà ghi hai số kệ khác nhau thì khi đi tìm bạn sẽ tới nhầm kệ và không bao giờ so sánh được. equals là bước nhìn xem đúng cuốn chưa, hashCode là việc chọn đúng kệ để đi tới, nên cả hai phải khớp. Kiểm tra mục tiêu 2.