Set và Map
Bài này đi qua hai nhóm còn lại: tập hợp Set không cho phần tử trùng, và ánh xạ Map
lưu cặp khoá-giá trị. Bộ ba cài đặt của Set phản chiếu đúng bộ ba của Map.
Vì sao cần tới hai nhóm này? Hãy nghĩ tới một phần mềm điểm danh. Câu hỏi "sinh viên này đã
điểm danh chưa" là câu hỏi về sự có mặt, không quan tâm thứ tự hay số lần, và Set trả lời
đúng nó. Câu hỏi "mã này ứng với ai" là câu hỏi tra cứu, và Map sinh ra cho việc đó. Nếu
chỉ có List, cả hai đều phải trả lời bằng cách quét toàn bộ danh sách.
Hãy đặt con số vào cho thấy rõ. Một lớp có ba trăm sinh viên, mỗi buổi điểm danh ta quét mã
thẻ ba trăm lần, và mỗi lần quét lại phải hỏi "mã này đã có trong danh sách chưa" để chặn
điểm danh hai lần. Nếu danh sách là ArrayList, mỗi câu hỏi kéo theo một lượt quét trung
bình một trăm năm mươi phần tử, tổng cộng khoảng bốn mươi lăm nghìn phép so sánh cho một
buổi. Nếu là HashSet, mỗi câu hỏi chỉ tốn một phép băm rồi nhảy thẳng tới ngăn cần tìm,
tổng cộng khoảng ba trăm thao tác. Chênh nhau hơn một trăm lần, mà mã nguồn hai bên dài
ngang nhau, chỉ khác một cái tên lớp lúc khởi tạo. Đây là lý do thật sự khiến Set và Map
tồn tại: chúng không thêm chức năng gì mà List không làm được, chúng chỉ làm cùng một việc
với một cái giá rẻ hơn hẳn.
Cái giá rẻ ấy không tự nhiên mà có. Nó được đổi bằng hai thứ. Thứ nhất là bộ nhớ: bảng băm
luôn giữ dư chỗ trống để tránh va chạm, nên tốn nhiều hơn một mảng chặt khít. Thứ hai, và
quan trọng hơn nhiều đối với người học, là một hợp đồng mà lớp phần tử phải tuân thủ.
HashSet và HashMap chỉ chạy đúng khi lớp của phần tử hoặc của khoá cài equals và
hashCode một cách nhất quán. TreeSet và TreeMap chỉ chạy đúng khi có một thứ tự xác
định trên khoá. Vi phạm những hợp đồng này thì chương trình vẫn biên dịch, vẫn chạy, chỉ có
điều nó cho ra kết quả sai một cách âm thầm. Nửa sau của bài dành hẳn cho phần hợp đồng đó,
vì đây là chỗ gây lỗi nhiều nhất trong toàn bộ chương tập hợp.
Thử ngay: xem HashMap chạy từng bước
Chưa cần thuộc lý thuyết bảng băm, hãy bấm ▶ Chạy (hoặc kéo thanh trượt) và nhìn một khoá
được cất vào rồi tra ra: đối tượng HashMap nằm trên bộ nhớ động, mỗi trường là một ngăn
của mảng băm. Quan sát khoá "tra" và "ca phe" cùng băm về ngăn [3] (va chạm), còn "che"
nằm một mình ở ngăn [0]; sau đó get("ca phe") đi thẳng tới ngăn [3] rồi quét chuỗi trong
đó. Nửa dưới của bài sẽ giải thích phép băm ấy và hợp đồng mà nó dựa vào.
1import java.util.HashMap;2import java.util.Map;34public class Demo {5 static int bucketOf(String key) {6 // simplified: index = hashCode mod 47 return Math.floorMod(key.hashCode(), 4);8 }910 public static void main(String[] args) {11 Map<String, Integer> gia = new HashMap<>();12 gia.put("tra", 18000); // hashes to bucket 313 gia.put("ca phe", 25000); // also bucket 3 -> collision14 gia.put("che", 12000); // hashes to bucket 015 int g = gia.get("ca phe"); // look up: recompute bucket, scan chain16 System.out.println(g);17 }18}
Tập hợp Set
Set là tập hợp không cho phần tử trùng. Ba cài đặt khác nhau ở thứ tự duyệt và cách
lưu trữ.
HashSetdựa trên bảng băm: thêm, xoá, kiểm tra tồn tại đều trung bìnhO(1), nhưng thứ tự duyệt không xác định.LinkedHashSetthêm một danh sách liên kết ghi lại thứ tự chèn, nên duyệt ra đúng thứ tự đã thêm, chi phí cao hơn một chút.TreeSetdựa trên cây đỏ đen (red-black tree), giữ phần tử luôn được sắp, các thao tác mấtO(log n)và cho thêm các truy vấn theo khoảng nhưfirst,last,ceiling,floor.
Set<String> a = new HashSet<>(); // no order guarantee, O(1) average
a.add("b"); a.add("a"); a.add("b"); // duplicate "b" ignored
System.out.println(a.size()); // 2
Set<String> b = new LinkedHashSet<>(); // preserves insertion order
b.add("b"); b.add("a"); b.add("c"); // iterates as b, a, c
Set<String> c = new TreeSet<>(); // sorted order, O(log n)
c.add("b"); c.add("a"); c.add("c"); // iterates as a, b, c
System.out.println(((TreeSet<String>) c).first()); // "a"
Cách chọn rất thẳng: mặc định dùng HashSet vì nhanh nhất; đổi sang LinkedHashSet khi cần
in lại đúng thứ tự đã thêm; đổi sang TreeSet khi cần kết quả luôn được sắp, hoặc cần truy
vấn theo khoảng như "phần tử nhỏ nhất còn lớn hơn x" qua higher, ceiling, headSet.
Ba cài đặt nhìn từ bên trong
Ba lớp trên không phải ba biến thể tuỳ hứng, mỗi lớp là một cấu trúc dữ liệu khác hẳn nhau, và hiểu bên trong thì việc chọn trở nên hiển nhiên chứ không phải học thuộc.
HashSet thật ra chỉ là một HashMap được giấu đi. Nó giữ phần tử của ta làm khoá, còn giá
trị thì luôn là một đối tượng giả duy nhất dùng chung cho mọi khoá. Nghe có vẻ lãng phí
nhưng đây là một quyết định kỹ thuật rất tiết kiệm: toàn bộ logic băm, va chạm, giãn bảng đã
viết một lần cho HashMap thì HashSet dùng lại nguyên xi mà không phải viết lại dòng nào.
Điều này cũng giải thích vì sao hai lớp có cùng đặc tính hiệu năng và cùng đòi hỏi hợp đồng
equals với hashCode.
LinkedHashSet kế thừa HashSet và bổ sung thêm một danh sách liên kết đôi xuyên qua mọi
phần tử, nối chúng lại theo đúng thứ tự đã chèn. Việc tra cứu vẫn đi qua bảng băm nên vẫn
O(1), còn việc duyệt thì đi dọc danh sách liên kết nên ra đúng thứ tự chèn. Cái giá là mỗi
phần tử phải mang thêm hai con trỏ, tốn bộ nhớ hơn khoảng vài chục phần trăm. Một chi tiết
hay bị hiểu sai: thêm lại một phần tử đã có không đẩy nó xuống cuối, vì lần thêm ấy
không làm tập thay đổi nên thứ tự cũng giữ nguyên.
TreeSet không dùng bảng băm gì cả. Nó là một cây tìm kiếm nhị phân tự cân bằng, cụ thể là
cây đỏ đen. Mỗi phần tử nằm ở một nút, và cây luôn giữ tính chất mọi nút bên trái nhỏ hơn
nút gốc, mọi nút bên phải lớn hơn. Vì thế duyệt cây theo thứ tự giữa sẽ cho ra dãy đã sắp mà
không cần sắp xếp gì thêm. Chiều cao cây luôn được giữ ở mức log n nhờ phép cân bằng lại
sau mỗi lần thêm hoặc xoá, nên mọi thao tác đều O(log n). Đây cũng là lý do TreeSet cho
ta các truy vấn mà hai lớp kia chịu chết: hỏi phần tử nhỏ nhất, lớn nhất, phần tử ngay trước
hoặc ngay sau một giá trị, hay cả một lát cắt theo khoảng.
Có một hiểu nhầm phổ biến cần dẹp ngay: TreeSet không sắp xếp lúc ta duyệt. Nó giữ
trạng thái đã sắp ở mọi thời điểm, kể cả ngay sau lần add đầu tiên. Điều này khác hẳn
việc đổ một HashSet ra danh sách rồi gọi Collections.sort. Nếu ta chỉ cần dữ liệu đã sắp
đúng một lần ở cuối chương trình thì cách thứ hai rẻ hơn, vì trả O(n log n) một lần thay
vì trả O(log n) cho từng lần thêm suốt vòng đời. Còn nếu ta liên tục thêm, xoá và luôn cần
nhìn thấy dữ liệu ở dạng đã sắp, TreeSet mới đáng đồng tiền.
Các phép toán trên tập hợp
Ba phương thức addAll, retainAll, removeAll biến Set thành công cụ làm các phép toán
tập hợp toán học: hợp, giao, hiệu. Chúng sửa thẳng vào tập gọi chúng, nên nếu cần giữ tập
gốc thì phải sao chép trước.
import java.util.HashSet;
import java.util.Set;
public class PhepToanTap {
public static void main(String[] args) {
Set<String> lopA = new HashSet<>(Set.of("An", "Binh", "Cuong"));
Set<String> lopB = new HashSet<>(Set.of("Binh", "Cuong", "Dung"));
Set<String> giao = new HashSet<>(lopA); // copy first, retainAll mutates
giao.retainAll(lopB); // intersection: [Binh, Cuong]
Set<String> hop = new HashSet<>(lopA);
hop.addAll(lopB); // union: [An, Binh, Cuong, Dung]
Set<String> chiA = new HashSet<>(lopA);
chiA.removeAll(lopB); // difference: [An]
System.out.println(giao.size() + " " + hop.size() + " " + chiA.size()); // 2 4 1
}
}
Một câu hỏi thi rất hay gặp: "cho hai danh sách, tìm phần tử chung". Người mới học viết hai
vòng lặp lồng nhau, tốn O(n * m). Người hiểu tập hợp đổ một danh sách vào HashSet rồi
quét danh sách kia đúng một lần, tốn O(n + m). Cùng một bài toán, cùng một kết quả, khác
nhau ở chỗ có nhận ra đây là phép giao hay không.
TreeSet đòi hỏi một thứ tựNếu lớp phần tử không cài Comparable và ta cũng không truyền Comparator vào hàm dựng,
chương trình vẫn biên dịch bình thường nhưng ném ClassCastException ngay lần add đầu
tiên. Nhiều người đoán là lần thứ hai, vì nghĩ phần tử đầu chưa có gì để so; thực ra
TreeSet chủ động ép kiểu khoá về Comparable để kiểm tra ngay từ phần tử đầu, nên lỗi
lộ ra sớm chứ không đợi. Hãy nhớ: HashSet cần equals và hashCode, còn TreeSet cần
một thứ tự.
class Diem { int x, y; } // does not implement Comparable
Set<Diem> s = new TreeSet<>(); // compiles fine
s.add(new Diem()); // ClassCastException right here
// Fix: supply an order via a Comparator
Set<Diem> ok = new TreeSet<>(Comparator.comparingInt((Diem d) -> d.x)
.thenComparingInt(d -> d.y));
Xem HashSet chặn phần tử trùng
Bản trace về HashMap ở đầu bài cho thấy cách băm khoá vào ngăn. Bản này soi một cơ chế khác của cùng bảng băm: HashSet dùng chính phép băm ấy để từ chối phần tử trùng. Ta thêm "a", "b", rồi "a" một lần nữa. Hãy quan sát lần thêm "a" thứ hai: nó băm về đúng ngăn đã có "a", equals xác nhận trùng, nên phần tử mới bị bỏ đi và số phần tử không tăng.
1import java.util.HashSet;2import java.util.Set;34public class Demo {5 public static void main(String[] args) {6 Set<String> s = new HashSet<>();7 s.add("a");8 s.add("b");9 s.add("a");10 System.out.println(s.size());11 }12}
Ánh xạ Map
Map lưu các cặp khoá-giá trị, khoá không trùng. Đây là cấu trúc tra cứu quan trọng
bậc nhất trong lập trình thực tế: từ điển, bộ đếm tần suất, bộ nhớ đệm. Bộ ba cài đặt
phản chiếu đúng bộ ba của Set: HashMap tra cứu trung bình O(1) và không bảo đảm
thứ tự, LinkedHashMap duyệt theo thứ tự chèn, TreeMap giữ khoá được sắp với các thao
tác O(log n).
Map<String, Integer> gia = new HashMap<>();
gia.put("ca phe", 25000); // insert key-value, O(1) average
gia.put("tra", 18000);
int g = gia.getOrDefault("nuoc", 0); // 0 if key absent, no exception
// Word frequency: a classic Map use case
String[] tu = {"a", "b", "a", "c", "a"};
Map<String, Integer> dem = new HashMap<>();
for (String t : tu) {
dem.merge(t, 1, Integer::sum); // add 1, or start at 1 if absent
}
// dem = {a=3, b=1, c=1}
for (Map.Entry<String, Integer> e : dem.entrySet()) {
System.out.println(e.getKey() + " = " + e.getValue());
}
Duyệt Map cho đúng
Nhiều người duyệt Map bằng cách lấy keySet() rồi với mỗi khoá lại gọi get(k). Cách đó
chạy đúng nhưng lãng phí, vì mỗi lần get là một lần băm và một lần tìm ngăn, trong khi
cặp khoá-giá trị vốn đã nằm sẵn cạnh nhau. Cách đúng là duyệt entrySet(), nơi mỗi phần tử
là một Map.Entry có sẵn cả khoá lẫn giá trị.
// Wasteful: hashes every key a second time
for (String k : gia.keySet()) System.out.println(k + " = " + gia.get(k));
// Idiomatic: one pass, key and value already paired
for (Map.Entry<String, Integer> e : gia.entrySet()) {
System.out.println(e.getKey() + " = " + e.getValue());
}
// Shortest, when the body is a single statement
gia.forEach((k, v) -> System.out.println(k + " = " + v));
Nếu chỉ cần giá trị mà không cần khoá, dùng values(). Khi cần vừa duyệt vừa xoá, đừng gọi
map.remove trong vòng lặp for vì sẽ nhận ConcurrentModificationException; hãy dùng
entrySet().removeIf(...).
Ba phương thức làm gọn mã đếm
getOrDefault(k, m) trả về giá trị của k, hoặc m nếu khoá vắng mặt, thay cho việc kiểm
tra null. merge(k, v, f) đặt v nếu khoá vắng mặt, còn nếu đã có thì ghép giá trị cũ
với v bằng hàm f. computeIfAbsent(k, f) trả về giá trị của k, và nếu khoá vắng mặt
thì tạo giá trị mới bằng f rồi đặt vào; đây là công cụ chuẩn để dựng bản đồ nhiều giá trị.
Map<String, Integer> dem = new HashMap<>();
dem.merge("tra", 1, Integer::sum); // 1 if absent, else old + 1
dem.merge("tra", 1, Integer::sum); // now 2
int n = dem.getOrDefault("che", 0); // 0, no NullPointerException
// Group students by class: one line instead of a null check plus a put
Map<String, List<String>> theoLop = new HashMap<>();
for (String[] sv : danhSach) { // sv = {class, name}
theoLop.computeIfAbsent(sv[0], k -> new ArrayList<>()).add(sv[1]);
}
Ba phương thức này không chỉ làm mã ngắn hơn, chúng làm mã đúng hơn. Hãy so với cách viết
thủ công mà ai cũng từng viết: gọi get(k), kiểm tra kết quả có null không, nếu null thì
put giá trị khởi đầu, nếu không thì cộng thêm rồi put lại. Đoạn ấy dài bốn dòng, chứa một
phép kiểm tra null dễ quên, và băm khoá tới hai lần cho mỗi phần tử. merge gói cả bốn
dòng vào một, băm một lần, và không có chỗ nào để quên null. Khi mã ngắn lại vì đúng ngữ
nghĩa chứ không phải vì viết tắt, đó là dấu hiệu ta đang dùng đúng công cụ.
Có vài chi tiết ngữ nghĩa nên nhớ cho chắc. getOrDefault không đặt giá trị mặc định vào
bản đồ, nó chỉ trả về giá trị ấy cho lần gọi này thôi; bản đồ vẫn không có khoá đó. Ngược
lại, computeIfAbsent có đặt giá trị vừa tạo vào bản đồ, đó chính là điều làm nó hợp với
việc dựng bản đồ nhiều giá trị. Còn merge có một hành vi ít ai để ý: nếu hàm ghép trả về
null thì cặp bị xoá khỏi bản đồ. Nghe lạ nhưng rất tiện, vì nhờ đó ta viết được phép
"giảm một, hết thì bỏ" trong đúng một dòng.
import java.util.HashMap;
import java.util.Map;
public class TonKho {
public static void main(String[] args) {
Map<String, Integer> kho = new HashMap<>();
kho.put("tra", 2);
// Sell one unit; when the count reaches zero the entry disappears
kho.merge("tra", -1, (cu, moi) -> cu + moi == 0 ? null : cu + moi);
System.out.println(kho); // {tra=1}
kho.merge("tra", -1, (cu, moi) -> cu + moi == 0 ? null : cu + moi);
System.out.println(kho); // {} the key is gone, not left at zero
}
}
Bên trong HashMap: ngăn chứa và va chạm
Để hiểu vì sao tra cứu chỉ tốn O(1), ta nhìn vào cấu trúc bên trong. HashMap giữ một
mảng các ngăn chứa (bucket). Khi đặt một cặp, nó tính mã băm của khoá bằng
hashCode(), rút gọn về một chỉ số ngăn, rồi đặt cặp vào ngăn đó. Khi tra cứu, nó lặp
lại đúng phép tính để nhảy thẳng tới ngăn cần tìm thay vì quét cả mảng.
Hai khoá khác nhau có thể rơi vào cùng một ngăn, gọi là va chạm (collision). Khi đó các cặp trong cùng ngăn được nối thành một danh sách liên kết; nếu ngăn quá dài, từ Java 8 nó được chuyển thành cây cân bằng để tra cứu trong ngăn vẫn nhanh.
Tree hay LinkedCần kết quả luôn được sắp theo khoá thì dùng TreeMap/TreeSet. Cần giữ đúng thứ tự
chèn để in lại như lúc nhập thì dùng LinkedHashMap/LinkedHashSet. Không cần thứ tự gì
thì HashMap/HashSet là nhanh nhất.
Thử ngay: bảng băm và va chạm
Bản trace ở đầu bài chạy một kịch bản băm cố định. Bảng dưới đây để bạn tự lái: thêm hoặc xoá
khoá tuỳ ý và xem chỉ số ngăn được tính lại bằng hash mod dung lượng, nhiều khoá cùng ngăn
nối thành một chuỗi va chạm. Khi hệ số tải vượt 0.75, bảng tự tăng gấp đôi dung
lượng và băm lại toàn bộ khoá, nên bạn thấy tận mắt một va chạm sinh ra rồi biến mất sau khi
băm lại. Không có con số nào bị gõ tay: mọi ngăn đều do engine tính thật.
Hợp đồng equals và hashCode
Hai bản trace phía trước cho thấy toàn bộ tốc độ của HashSet và HashMap dựa trên một giả định: hai
đối tượng bằng nhau phải băm về cùng một ngăn. Java biến giả định đó thành hợp đồng bắt
buộc giữa hai phương thức của Object. Nếu a.equals(b) trả về true thì a.hashCode()
phải bằng b.hashCode(). Chiều ngược lại không bắt buộc: hai đối tượng cùng mã băm vẫn có
thể khác nhau, đó chính là va chạm.
Hệ quả rất cụ thể. Nếu ghi đè equals mà quên hashCode, hai đối tượng bằng nhau theo
nghĩa nghiệp vụ vẫn giữ mã băm mặc định dựa trên địa chỉ nên rơi vào hai ngăn khác nhau.
HashSet không bao giờ mang chúng ra so bằng equals, và nó chứa cả hai như thể là hai
phần tử riêng biệt. Tập hợp mất đúng cái tính chất làm nên nó.
public final class MaSV {
private final String ma;
public MaSV(String ma) { this.ma = ma; }
@Override
public boolean equals(Object o) {
if (this == o) return true; // same reference
if (!(o instanceof MaSV other)) return false;
return ma.equals(other.ma); // compare the same field
}
@Override
public int hashCode() {
return Objects.hash(ma); // MUST use exactly the fields equals() uses
}
}
Từ Java 16, khai báo record MaSV(String ma) {} sinh sẵn equals, hashCode và toString
theo đúng hợp đồng, nên trong mã mới hãy ưu tiên record cho các lớp chỉ mang dữ liệu.
HashSet và HashMapGhi đè equals mà quên hashCode, hoặc ngược lại. Hai phương thức phải luôn đi cùng nhau
và dựa trên cùng một tập trường.
Dùng đối tượng khả biến làm khoá rồi sửa trường của nó sau khi đã put. Mã băm đổi theo,
HashMap vẫn để cặp ở ngăn cũ, nên get trả về null dù cặp vẫn nằm trong bảng.
Vì sao khoá phải bất biến
Lỗi thứ hai trong khung cảnh báo trên đáng được mổ xẻ chậm, vì nó là loại lỗi khiến người ta
ngồi nhìn màn hình cả buổi mà không hiểu chuyện gì đang xảy ra. Chương trình không ném ngoại
lệ, không cảnh báo, chỉ trả về null cho một khoá mà ta nhìn thấy rành rành trong bảng khi
in ra.
Hãy dựng lại hiện trường theo từng bước. Ta có một lớp có trường thay đổi được, và hashCode
của nó tính từ chính trường đó. Ta tạo một đối tượng với trường mang giá trị "A1", rồi
put nó vào HashMap. Lúc này bản đồ băm giá trị "A1", ra chỉ số ngăn giả sử là 3, và
đặt cặp vào ngăn 3. Tới đây mọi thứ vẫn đúng. Sau đó, ở một chỗ khác trong chương trình, ta
sửa trường của đối tượng thành "B7". Cái đối tượng ấy vẫn nằm nguyên trong ngăn 3, vì bản
đồ không hề được báo tin, nó đâu có cách nào biết ta vừa động vào bên trong khoá của nó.
Bây giờ ta gọi get với chính cái đối tượng vừa sửa. Bản đồ tính lại mã băm, nhưng lần này
mã băm dựa trên "B7" nên ra ngăn 5 chứ không phải 3. Nó tìm trong ngăn 5, thấy rỗng,
và trả về null. Cặp của ta vẫn còn nguyên trong bảng, size() vẫn đếm nó, in bản đồ ra
vẫn thấy nó, nhưng không ai lấy được nó ra nữa. Nó trở thành một cặp mồ côi, chiếm bộ nhớ mà
vô dụng, và không có cách nào xoá bằng remove(khoa) vì remove cũng đi tìm ở ngăn 5.
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
class Khoa { // mutable key: a bug waiting to happen
String ma;
Khoa(String ma) { this.ma = ma; }
@Override public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Khoa k)) return false;
return Objects.equals(ma, k.ma);
}
@Override public int hashCode() { return Objects.hash(ma); }
}
public class KhoaKhaBien {
public static void main(String[] args) {
Map<Khoa, String> bang = new HashMap<>();
Khoa k = new Khoa("A1");
bang.put(k, "gia tri"); // hashed with "A1", stored in that bucket
k.ma = "B7"; // the key mutates behind the map's back
System.out.println(bang.get(k)); // null: it now hashes to another bucket
System.out.println(bang.size()); // 1: the pair is still in there
System.out.println(bang.containsKey(k)); // false, yet it is printed by toString
}
}
Cách phòng lỗi này rất dứt khoát: khoá phải bất biến. Cụ thể là lớp khoá nên khai báo
final, mọi trường tham gia vào equals và hashCode cũng nên final, và lớp không được
cung cấp phương thức nào sửa các trường ấy. Nếu buộc phải dùng một đối tượng khả biến làm
khoá, hãy tự đặt ra kỷ luật là không đụng vào nó suốt thời gian nó còn nằm trong bản đồ, dù
kỷ luật kiểu ấy sớm muộn cũng có người phá.
May thay, từ Java 16 ta có một câu trả lời gọn gàng. Kiểu record sinh sẵn equals,
hashCode và toString theo đúng hợp đồng, đồng thời mọi thành phần của nó tự động là
final, nên một record bất biến ngay từ bản chất. Với vai trò khoá của bản đồ, record
gần như luôn là lựa chọn đúng, và nó rút cả lớp Khoa phía trên xuống đúng một dòng.
import java.util.HashMap;
import java.util.Map;
public class KhoaRecord {
record MaSV(String ma) {} // Java 16+: equals, hashCode, immutable
public static void main(String[] args) {
Map<MaSV, String> bang = new HashMap<>();
bang.put(new MaSV("A1"), "Nguyen Van An");
// A brand new object with the same value finds the entry: that is the contract
System.out.println(bang.get(new MaSV("A1"))); // Nguyen Van An
}
}
Dòng cuối của ví dụ nói lên toàn bộ ý nghĩa của hợp đồng equals và hashCode. Ta tra bằng
một đối tượng hoàn toàn mới, khác địa chỉ, khác thể hiện, nhưng vẫn lấy ra được giá trị.
Bản đồ không đi tìm theo đối tượng, nó đi tìm theo giá trị của khoá. Đó chính là điều mà
hai phương thức kia định nghĩa: thế nào là hai khoá được coi là một.
String là khoá phổ biến nhất, và không phải ngẫu nhiên. Nó bất biến, equals so theo nội
dung, hashCode đã cài đúng và còn được nhớ đệm sau lần tính đầu. Các lớp bao như Integer,
Long cũng bất biến và đúng hợp đồng. Nói cách khác, những khoá mà ta vẫn dùng hằng ngày mà
không phải nghĩ gì đều là khoá bất biến, ta chỉ không để ý mà thôi.
TreeMap cần một thứ tự
HashMap cần biết hai khoá có bằng nhau không. TreeMap cần nhiều hơn thế: nó cần biết khoá
nào đứng trước khoá nào, vì nó xếp khoá vào một cây tìm kiếm. Thứ tự ấy đến từ một trong
hai nguồn. Nguồn thứ nhất là thứ tự tự nhiên, khi lớp khoá cài Comparable và định nghĩa
compareTo. String, Integer, LocalDate đều có sẵn thứ tự tự nhiên nên dùng thẳng làm
khoá TreeMap được ngay. Nguồn thứ hai là một Comparator truyền vào hàm dựng, dùng khi lớp
khoá không có thứ tự tự nhiên, hoặc khi ta cần một thứ tự khác với thứ tự mặc định.
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
public class ThuTuKhoa {
record SinhVien(String ho, String ten) {} // no natural order of its own
public static void main(String[] args) {
// Descending order: a comparator overrides the natural order of String
Map<String, Integer> giam = new TreeMap<>(Comparator.reverseOrder());
giam.put("a", 1); giam.put("c", 3); giam.put("b", 2);
System.out.println(giam); // {c=3, b=2, a=1}
// A record has no natural order, so a comparator is mandatory here
Map<SinhVien, Integer> diem = new TreeMap<>(
Comparator.comparing(SinhVien::ho).thenComparing(SinhVien::ten));
diem.put(new SinhVien("Nguyen", "An"), 8);
diem.put(new SinhVien("Le", "Binh"), 9);
System.out.println(diem.keySet()); // Le Binh first, then Nguyen An
}
}
Có một chỗ tinh vi mà ngay cả người đi làm cũng hay vấp: TreeMap không dùng equals để
xác định hai khoá có trùng nhau hay không. Nó dùng compareTo hoặc Comparator, và coi
hai khoá là một khi phép so sánh trả về 0. Hệ quả là nếu thứ tự ta cung cấp không nhất quán
với equals, bản đồ sẽ hành xử theo một cách khiến ta ngạc nhiên. Ví dụ ta truyền vào một
Comparator chỉ so theo họ, thì hai sinh viên khác tên nhưng cùng họ sẽ được TreeMap coi
là cùng một khoá, và người thứ hai ghi đè lên điểm của người thứ nhất. Không có ngoại lệ,
không có cảnh báo, chỉ có một bản ghi lặng lẽ biến mất.
TreeMap và TreeSetThứ nhất, dùng lớp không cài Comparable mà không truyền Comparator: ClassCastException
ngay lần add hoặc put đầu tiên, dù mã biên dịch sạch.
Thứ hai, Comparator không nhất quán với equals, ví dụ chỉ so một phần các trường. Bản đồ
sẽ gộp những khoá mà ta coi là khác nhau, và dữ liệu bị ghi đè âm thầm. Quy tắc an toàn: so
sánh trên đúng tập trường mà equals dùng, và nếu cần thì thenComparing thêm cho đủ.
Thứ ba, viết compareTo bằng phép trừ a - b với số nguyên lớn. Phép trừ có thể tràn số và
đảo dấu, làm thứ tự sai lung tung ở đúng những dữ liệu hiếm gặp nhất. Hãy dùng
Integer.compare(a, b).
Thứ tư, đưa null làm khoá vào TreeMap. HashMap chấp nhận một khoá null, còn TreeMap
thì không, vì nó phải gọi phép so sánh trên khoá và không so được với null. Kết quả là
NullPointerException.
Bài tập thực hành
Bài tập 1: giữ phần tử xuất hiện đúng một lần
Viết phương thức chiMotLan(List<Integer> a) trả về danh sách mới chỉ giữ các phần tử
xuất hiện đúng một lần trong a, theo đúng thứ tự xuất hiện ban đầu. Yêu cầu dùng
LinkedHashMap để vừa đếm vừa bảo toàn thứ tự.
Lời giải chi tiết
Bước 1: dùng LinkedHashMap đếm số lần xuất hiện của từng giá trị; vì là Linked, thứ
tự duyệt sẽ đúng thứ tự lần đầu gặp mỗi khoá. Bước 2: duyệt các cặp, giữ lại khoá nào có
giá trị đếm bằng 1.
static List<Integer> chiMotLan(List<Integer> a) {
Map<Integer, Integer> dem = new LinkedHashMap<>(); // preserves first-seen order
for (int x : a) {
dem.merge(x, 1, Integer::sum); // count occurrences
}
List<Integer> ketQua = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : dem.entrySet()) {
if (e.getValue() == 1) ketQua.add(e.getKey()); // keep singletons only
}
return ketQua;
}
Ý chính: LinkedHashMap cho ta đếm tần suất mà vẫn nhớ thứ tự chèn, nên không phải sắp
lại ở cuối.
Bài tập 2: in theo thứ tự khoá
Cho danh sách lượt mua hàng, mỗi lượt là tên mặt hàng. In các mặt hàng theo thứ tự bảng
chữ cái kèm số lần mua. Gợi ý: chọn Map nào cho kết quả tự được sắp theo khoá.
Lời giải chi tiết
Vì cần kết quả được sắp theo khoá, chọn TreeMap; phép đếm dùng merge.
String[] luot = {"tra", "ca phe", "tra", "banh", "ca phe", "tra"};
Map<String, Integer> dem = new TreeMap<>(); // sorted by key
for (String m : luot) {
dem.merge(m, 1, Integer::sum); // count occurrences
}
dem.forEach((k, v) -> System.out.println(k + ": " + v));
// banh: 1
// ca phe: 2
// tra: 3
Nếu đề bài chỉ cần đếm mà không quan tâm thứ tự, đổi TreeMap thành HashMap để tra
cứu nhanh hơn. Một thay đổi nhỏ ở dòng khởi tạo, nhờ ta đã lập trình theo giao tiếp Map.
Bài tập 3: nhóm từ theo chữ cái đầu
Cho một mảng từ, hãy dựng một Map ánh xạ mỗi chữ cái đầu tới danh sách các từ bắt đầu
bằng chữ cái đó, và in ra theo thứ tự chữ cái. Yêu cầu dùng computeIfAbsent.
Lời giải chi tiết
Cần kết quả sắp theo khoá nên chọn TreeMap. computeIfAbsent lo việc tạo danh sách rỗng
cho chữ cái gặp lần đầu, nhờ đó không phải viết đoạn kiểm tra null rồi put.
String[] tu = {"tra", "banh", "ca phe", "bun", "che"};
Map<Character, List<String>> nhom = new TreeMap<>(); // sorted by letter
for (String t : tu) {
nhom.computeIfAbsent(t.charAt(0), k -> new ArrayList<>()).add(t);
}
nhom.forEach((k, v) -> System.out.println(k + ": " + v));
// b: [banh, bun]
// c: [ca phe, che]
// t: [tra]
Ý chính: computeIfAbsent trả về danh sách đã có hoặc danh sách vừa tạo, nên lời gọi add
phía sau luôn hợp lệ.
Bài tập 4: chẩn đoán một khoá biến mất
Đoạn mã dưới in ra null ở dòng cuối, dù bản đồ rõ ràng vẫn chứa đúng một cặp. Hãy giải
thích nguyên nhân gốc, chỉ ra chính xác dòng nào gây ra vấn đề, rồi sửa lại lớp Sach sao
cho đoạn mã in ra tên sách.
class Sach {
String isbn;
Sach(String isbn) { this.isbn = isbn; }
@Override public boolean equals(Object o) {
return o instanceof Sach s && isbn.equals(s.isbn);
}
@Override public int hashCode() { return isbn.hashCode(); }
}
Map<Sach, String> thuVien = new HashMap<>();
Sach s = new Sach("111");
thuVien.put(s, "Lap trinh Java");
s.isbn = "222"; // somewhere else in the program
System.out.println(thuVien.get(s)); // prints null
Lời giải chi tiết
Dòng gây lỗi là s.isbn = "222";. Nó sửa trường mà hashCode dựa vào, ngay khi đối tượng
đang được dùng làm khoá trong bản đồ.
Diễn biến cụ thể: lúc put, bản đồ băm chuỗi "111" và đặt cặp vào ngăn tương ứng, giả sử
là ngăn X. Khi trường isbn đổi thành "222", cặp vẫn nằm ở ngăn X vì bản đồ không được
báo tin và cũng không có cách nào biết. Tới lúc get(s), bản đồ băm lại khoá, lần này ra
"222" nên nhảy tới ngăn Y, không thấy gì ở đó, và trả về null. Cặp cũ vẫn còn trong
bảng, size() vẫn bằng 1, nhưng nó đã thành một cặp mồ côi không ai lấy ra được nữa.
Điều đáng nói là equals và hashCode ở đây viết đúng hợp đồng. Lỗi không nằm ở hai
phương thức ấy mà nằm ở tính khả biến của lớp. Bài học: hợp đồng equals và hashCode chỉ
có ý nghĩa khi giá trị của khoá đứng yên trong suốt thời gian nó nằm trong bản đồ.
Cách sửa gọn nhất là biến Sach thành record, vì record bất biến sẵn và sinh sẵn hai
phương thức kia đúng hợp đồng. Khi đó dòng s.isbn = "222"; không còn biên dịch được nữa,
tức là trình biên dịch chặn lỗi giúp ta ngay từ đầu, thay vì để nó âm thầm phát tác lúc chạy.
import java.util.HashMap;
import java.util.Map;
public class ThuVien {
record Sach(String isbn) {} // immutable: equals and hashCode generated
public static void main(String[] args) {
Map<Sach, String> thuVien = new HashMap<>();
thuVien.put(new Sach("111"), "Lap trinh Java");
// s.isbn = "222"; // would not even compile now
System.out.println(thuVien.get(new Sach("111"))); // Lap trinh Java
}
}
Nếu vì lý do nào đó không dùng được record, cách sửa thứ hai là khai báo lớp final, cho
trường isbn là private final, và bỏ mọi phương thức đặt giá trị. Kết quả về mặt an toàn
là như nhau, chỉ dài dòng hơn.
Câu hỏi tự kiểm
- 1Trong cây phân cấp của Bộ khung tập hợp, Map có kế thừa Collection không?
- 2TreeMap và TreeSet xác định hai khoá có trùng nhau hay không dựa vào đâu?
- 3Điểm khác nhau then chốt giữa computeIfAbsent và getOrDefault là gì?
- 4Với merge(k, v, f), nếu hàm ghép f trả về null thì điều gì xảy ra?
Tóm tắt
Settrả lời câu hỏi có mặt hay không;Maptrả lời câu hỏi khoá này ứng với gì.- Bộ ba của
Setphản chiếu bộ ba củaMap:Hashnhanh nhất và không thứ tự,Linkedgiữ thứ tự chèn,Treeluôn được sắp với chi phíO(log n). HashSetbên trong là mộtHashMapgiấu đi;LinkedHashSetthêm một danh sách liên kết ghi thứ tự chèn;TreeSetlà cây đỏ đen nên luôn ở trạng thái đã sắp.- Duyệt
MapbằngentrySethoặcforEach, không lấykeySetrồigetlại từng khoá. getOrDefaultkhông ghi vào bản đồ,computeIfAbsentcó ghi, cònmergexoá cặp nếu hàm ghép trả vềnull.- Hợp đồng bắt buộc: bằng nhau thì phải cùng mã băm. Ghi đè
equalsvàhashCodecùng lúc, trên cùng tập trường, và giữ khoá bất biến. - Sửa trường của một khoá đang nằm trong bản đồ sẽ đẩy nó vào sai ngăn: cặp còn đó nhưng
không ai lấy ra được. Với vai trò khoá, hãy ưu tiên
recordhoặc lớp bất biến. TreeMapxác định khoá trùng bằng phép so sánh trả về0, không phải bằngequals, nên mộtComparatorthiếu trường sẽ làm dữ liệu bị ghi đè âm thầm.