Cụm bài Cấu trúc dữ liệu: 1. Array, Linked List, Stack, Queue · 2. List, Set, Map · 3. TreeMap, Comparator, Iterator · 4. Bên trong ArrayList, HashMap
Phần 2 dừng ở HashSet và HashMap: nhanh nhưng không có thứ tự. Phần này nói về dữ liệu có thứ tự (TreeSet, TreeMap, NavigableMap), cách định nghĩa thứ tự bằng Comparable/Comparator, và cách duyệt an toàn bằng Iterator. Cuối bài là Lab 09 (quản lý thành viên câu lạc bộ bằng năm loại collection) có lời giải chạy thử; nên đọc phần 2 trước (List, Set, Map, equals/hashCode).
Sơ đồ tóm tắt:
flowchart TD
A{"Cần gì?"} -->|"Tra key nhanh"| B["HashMap O(1)"]
A -->|"Thứ tự, gần nhất, khoảng"| C["TreeMap O(log n)"]
C --> D["floorEntry, ceilingKey, subMap"]
C --> E["Trùng theo compareTo"]
E --> F{"Thứ tự nào?"}
F -->|"Tự nhiên"| G["Comparable"]
F -->|"Nghiệp vụ"| H["Comparator"]
I["Sửa khi đang duyệt"] -->|"Qua iterator"| J["iterator.remove, removeIf"]
I -->|"Đường khác"| K["ConcurrentModificationException"]
1. TreeSet, TreeMap và NavigableMap
Ý chính: TreeMap giữ key luôn được sắp xếp, đổi lại mỗi thao tác tốn O(log n) thay vì O(1). Chọn nó khi cần thứ tự theo key hoặc hỏi “key gần nhất, key trong khoảng”.
TreeMap là cây đỏ-đen (red-black tree, cây nhị phân tìm kiếm tự cân bằng để không bao giờ bị lệch thành một đường thẳng). TreeSet thực chất là một TreeMap chỉ dùng phần key.
Thứ tự lấy từ một trong hai nguồn:
compareTocủa phần tử (natural ordering, phần tử phải implementComparable).- Một
Comparatortruyền vào constructor.
TreeMap implement NavigableMap, và đây mới là lý do chính để chọn nó: các truy vấn mà HashMap không làm được.
// Hạng thành viên theo tổng chi tiêu: key là mốc bắt đầu của mỗi hạng
NavigableMap<BigDecimal, String> tiers = new TreeMap<>();
tiers.put(BigDecimal.ZERO, "STANDARD");
tiers.put(new BigDecimal("5000000"), "SILVER");
tiers.put(new BigDecimal("20000000"), "GOLD");
tiers.floorEntry(new BigDecimal("7500000")).getValue(); // "SILVER": key lớn nhất <= 7 500 000
// Sự kiện theo timestamp: lấy các sự kiện trong một cửa sổ thời gian
NavigableMap<Long, String> events = new TreeMap<>();
events.subMap(from, true, to, false); // [from, to)
events.headMap(t); // mọi key < t
events.tailMap(t, true); // mọi key >= t
| Method | Trả về |
|---|---|
floorKey(k) / ceilingKey(k) |
key lớn nhất ≤ k / nhỏ nhất ≥ k (không có thì null) |
lowerKey(k) / higherKey(k) |
key lớn nhất < k / nhỏ nhất > k |
firstEntry() / lastEntry() |
entry nhỏ nhất / lớn nhất |
pollFirstEntry() / pollLastEntry() |
lấy ra và xoá entry nhỏ nhất / lớn nhất |
headMap, tailMap, subMap |
view theo khoảng, sửa view là sửa map gốc |
descendingMap() |
view theo thứ tự ngược |
TreeSet có bộ tương ứng: floor, ceiling, lower, higher, headSet, tailSet, subSet, pollFirst.
Key null trong HashMap, TreeMap và ConcurrentHashMap
HashMapcho một keynull,HashSetcho một phần tửnull.TreeMap/TreeSetvới natural ordering némNullPointerExceptionkhi gặp keynull, vì phải gọicompareTo. Chúng chỉ chấp nhậnnullnếu Comparator tự xử lý, ví dụComparator.nullsFirst(...).ConcurrentHashMapcấmnullcả ở key lẫn value.
2. Comparable và Comparator
Ý chính: Comparable là thứ tự tự nhiên viết trong class, mỗi class chỉ một. Comparator là thứ tự viết bên ngoài, dùng cho thứ tự theo nghiệp vụ hoặc cho class không sửa được.
Comparable<T>(compareTo): ví dụStringtheo bảng chữ cái,Integertheo giá trị,LocalDatetheo thời gian.Comparator<T>(compare): viết bao nhiêu cái cũng được, kể cả cho class của thư viện.
// Thứ tự tự nhiên: nằm trong class
record Version(int major, int minor) implements Comparable<Version> {
public int compareTo(Version o) {
return Comparator.comparingInt(Version::major).thenComparingInt(Version::minor).compare(this, o);
}
}
// Thứ tự bên ngoài: mỗi màn hình một kiểu sắp xếp
Comparator<Member> byAgeThenName = Comparator.comparingInt(Member::age)
.thenComparing(Member::name)
.thenComparingInt(Member::id); // khoá phân biệt cuối cùng
Comparator<Product> byPriceDescNullsLast =
Comparator.comparing(Product::price, Comparator.nullsLast(Comparator.reverseOrder()));
members.sort(byAgeThenName);
Quy tắc chọn: thứ tự “hiển nhiên” ai cũng đồng ý (số, ngày, phiên bản) thì implement Comparable. Thứ tự theo nghiệp vụ hay màn hình (giá, tên, điểm) thì dùng Comparator, đừng nhét vào compareTo.
Javadoc khuyến nghị thứ tự tự nhiên nhất quán với equals: a.compareTo(b) == 0 khi và chỉ khi a.equals(b). Vi phạm thì TreeSet và HashSet cho kết quả khác nhau với cùng dữ liệu (ví dụ Member ở mục 1). Các bẫy khi viết Comparator (phép trừ tràn số, vi phạm contract, null) có ở bài Merge sort, quick sort và cách Java sắp xếp.
3. Iterator, ListIterator và fail-fast
Ý chính: muốn sửa collection trong lúc duyệt thì sửa qua chính iterator (iterator.remove(), ListIterator.add/set) hoặc dùng removeIf. Sửa bằng đường khác thì iterator fail-fast ném ConcurrentModificationException (CME), nhưng không phải lúc nào cũng ném.
Iteratordùng được cho mọiCollection:hasNext,next,remove.ListIteratorchỉ có ởList: duyệt hai chiều, biết vị trí, thêm và sửa phần tử ngay tại chỗ đang đứng.
List<Integer> nums = new ArrayList<>(List.of(10, 20, 30));
ListIterator<Integer> it = nums.listIterator();
while (it.hasNext()) {
int v = it.next();
if (v == 20) it.add(25); // chèn ngay sau 20, không làm hỏng vòng lặp
if (v == 30) it.set(31); // thay phần tử vừa trả về bởi next()
}
// nums = [10, 20, 25, 31]
while (it.hasPrevious()) { // đi ngược: 31, 25, 20, 10
System.out.println(it.previousIndex() + ": " + it.previous());
}
Fail-fast hoạt động thế này: collection giữ bộ đếm modCount (số lần bị sửa cấu trúc). Iterator nhớ giá trị lúc tạo và so lại mỗi lần next(); lệch thì ném CME. Đây là cơ chế phát hiện lỗi theo kiểu cố gắng hết sức (best effort), không phải cơ chế đồng bộ. Giống chuông báo cửa: kêu thì chắc có người vào, không kêu chưa chắc là không ai vào.
Vì sao fail-fast chỉ là best effort: ca xoá phần tử áp chót
Bài tập
Bài 1: Lab 09: quản lý thành viên câu lạc bộ
Đề (diễn đạt lại): class Member gồm id, name, age, sắp xếp tự nhiên theo tuổi tăng dần, cùng tuổi thì theo tên. Sau đó:
ArrayList<Member>: thêm 5 thành viên, in ra.HashSet<Integer>: bỏ id của các thành viên vào, thử thêm một id trùng, in tập id.TreeSet<Member>: bỏ các thành viên vào để có bảng xếp hạng theo tuổi, in ra.HashMap<Integer, Integer>: điểm thưởng theo id cho 3 thành viên, cộng thêm 10 điểm cho thành viên id 1 nếu có, in ra.TreeMap<Integer, String>: id → tên của mọi thành viên, in ra và để ý thứ tự key.
Gợi ý: đề có một cái bẫy ở bước 3. Thử thêm hai thành viên cùng tên, cùng tuổi.
Lời giải Bài 1: code, output JDK 21 và giải thích
import java.util.*;
public class MemberLab {
// record: immutable, equals/hashCode/toString tự sinh theo cả ba field
record Member(int id, String name, int age) implements Comparable<Member> {
private static final Comparator<Member> ORDER = Comparator
.comparingInt(Member::age)
.thenComparing(Member::name)
.thenComparingInt(Member::id); // khoá phân biệt cuối cùng
Member {
if (id <= 0) throw new IllegalArgumentException("id must be > 0");
Objects.requireNonNull(name, "name");
if (age < 0) throw new IllegalArgumentException("age must be >= 0");
}
@Override
public int compareTo(Member other) {
return ORDER.compare(this, other);
}
}
public static void main(String[] args) {
// 1. Danh sách đăng ký: giữ thứ tự thêm vào, cho phép trùng
List<Member> members = new ArrayList<>(List.of(
new Member(3, "Chi", 22),
new Member(1, "An", 25),
new Member(5, "Binh", 22),
new Member(2, "Dung", 30),
new Member(4, "An", 25))); // cùng tên, cùng tuổi với id 1
System.out.println("Registered: " + members);
// 2. Tập id duy nhất: Integer đã có sẵn equals/hashCode
Set<Integer> memberIds = new HashSet<>();
for (Member m : members) memberIds.add(m.id());
boolean added = memberIds.add(1); // id trùng
System.out.println("Add duplicate id 1 -> " + added + ", ids = " + memberIds);
// 3. Xếp hạng theo tuổi, rồi tên, rồi id
NavigableSet<Member> ranked = new TreeSet<>(members);
System.out.println("Ranked:");
ranked.forEach(m -> System.out.println(" " + m));
System.out.println("Ranked size = " + ranked.size() + " (list size = " + members.size() + ")");
// 4a. Điểm thưởng: id -> điểm
Map<Integer, Integer> pointMap = new HashMap<>();
pointMap.put(1, 50);
pointMap.put(3, 20);
pointMap.put(5, 70);
pointMap.computeIfPresent(1, (id, p) -> p + 10); // chỉ cộng khi id 1 đã có
pointMap.computeIfPresent(9, (id, p) -> p + 10); // id 9 không có: không làm gì
System.out.println("Points: " + pointMap);
// 4b. id -> tên, luôn duyệt theo id tăng dần
NavigableMap<Integer, String> idNameMap = new TreeMap<>();
for (Member m : members) idNameMap.put(m.id(), m.name());
System.out.println("Id -> name: " + idNameMap);
System.out.println("First id >= 3: " + idNameMap.ceilingEntry(3));
// Thử nghiệm: bỏ khoá phân biệt id thì TreeSet nuốt mất một thành viên
Comparator<Member> byAgeThenName = Comparator.comparingInt(Member::age).thenComparing(Member::name);
Set<Member> lossy = new TreeSet<>(byAgeThenName);
lossy.addAll(members);
System.out.println("Without id tie-breaker: size = " + lossy.size());
}
}
Output khi chạy với JDK 21:
Registered: [Member[id=3, name=Chi, age=22], Member[id=1, name=An, age=25], Member[id=5, name=Binh, age=22], Member[id=2, name=Dung, age=30], Member[id=4, name=An, age=25]]
Add duplicate id 1 -> false, ids = [1, 2, 3, 4, 5]
Ranked:
Member[id=5, name=Binh, age=22]
Member[id=3, name=Chi, age=22]
Member[id=1, name=An, age=25]
Member[id=4, name=An, age=25]
Member[id=2, name=Dung, age=30]
Ranked size = 5 (list size = 5)
Points: {1=60, 3=20, 5=70}
Id -> name: {1=An, 2=Dung, 3=Chi, 4=An, 5=Binh}
First id >= 3: 3=Chi
Without id tie-breaker: size = 4
Giải thích:
HashSet<Integer>không cần viếtequals/hashCode. Đề gợi ý phải viết, nhưngIntegerđã có sẵn cả hai. Chỉ khi bỏ chínhMembervàoHashSetmới phải lo, và record đã tự sinh.- Thứ tự “tuổi rồi tên” theo đúng đề sẽ làm mất dữ liệu. Id 1 và id 4 cùng tên “An”, cùng 25 tuổi nên
compareTo == 0,TreeSetgiữ một và bỏ âm thầm cái kia (dòng cuối output: size 4). Đề không nhắc tới chuyện này. Lời giải thêmidlàm khoá phân biệt cuối, nhờ đó thứ tự nhất quán vớiequalscủa record. - “Cộng 10 điểm nếu tồn tại” đúng là việc của
computeIfPresent: một lần tra, không cầncontainsKey+get+put. Muốn “chưa có thì tạo với 10 điểm” thì dùngmerge(1, 10, Integer::sum). TreeMapluôn in theo id tăng dần dù thêm theo thứ tự 3, 1, 5, 2, 4.HashMapvới keyIntegernhỏ trông cũng “có thứ tự”, nhưng đó là trùng hợp do hash củaIntegerlà chính nó; đừng dựa vào.- Khai báo bằng
NavigableSet/NavigableMapthay vìSet/Mapkhi cầnceilingEntry,headSet…
Một senior sẽ cải thiện thêm:
- Giữ
Memberimmutable (record, không setter). Đề yêu cầu setter, nhưng sửaagecủa phần tử đang nằm trongTreeSetlàm hỏng cây (phần tử nằm sai vị trí,containstrảfalse), y như sửa key trongHashMap. - Đừng nhét thứ tự “theo tuổi” vào
compareTonếu đó chỉ là thứ tự của một màn hình. Thứ tự tự nhiên hợp lý hơn là theoid; bảng xếp hạng dùngComparatorriêng (mục 2). - Nhiều luồng cùng cộng điểm thì
HashMapkhông an toàn: dùngConcurrentHashMap.merge, hoặc tốt hơn là để database cộng (UPDATE ... SET points = points + 10).
Ghi nhớ
- Giải thích được vì sao
TreeSetcó thể “nuốt” một phần tử khácequals, và cách sửa bằng khoá phân biệt. - Biết khi nào chọn
TreeMapthayHashMap, và viết đượcfloorEntry/subMapcho bài toán hạng hoặc cửa sổ thời gian. - Biết khi nào dùng
Comparable, khi nào dùngComparator. - Giải thích được
modCountvà vì sao fail-fast chỉ là best effort. - Phân biệt được fail-fast, weakly consistent và snapshot, và chọn theo tỉ lệ đọc/ghi.
Câu hỏi phỏng vấn
Junior
Comparable và Comparator khác nhau thế nào? Khi nào dùng cái nào?
Comparable là thứ tự tự nhiên trong class (một cái mỗi class); Comparator là thứ tự bên ngoài, viết được nhiều cái.
Comparable (compareTo) có ở String, Integer, LocalDate. Comparator (compare) dùng được cho class không sửa được. Thứ tự hiển nhiên thì implement Comparable; thứ tự theo nghiệp vụ hoặc màn hình thì dùng Comparator.comparing(...).thenComparing(...).
TreeMap khác HashMap thế nào? Khi nào chọn TreeMap?
HashMap là bảng băm O(1), không thứ tự; TreeMap là cây đỏ-đen O(log n), luôn sắp theo key và có truy vấn gần nhất/theo khoảng.
HashMap cho một key null. TreeMap so key bằng compareTo/Comparator (natural ordering không nhận key null), và có floorEntry, ceilingKey, subMap, headMap của NavigableMap. Chọn TreeMap khi cần sắp theo key hoặc hỏi “key gần nhất/khoảng key”, ví dụ bảng hạng theo mức chi tiêu hoặc sự kiện theo khung thời gian; còn lại dùng HashMap.
Mid
Thêm hai object khác nhau vào TreeSet nhưng size() vẫn là 1. Vì sao?
Vì TreeSet xác định trùng bằng compareTo/Comparator, không gọi equals/hashCode.
Nếu thứ tự chỉ so một phần field (ví dụ tuổi rồi tên) thì hai object khác id nhưng cùng tuổi và tên có compare == 0, phần tử thứ hai bị bỏ qua âm thầm. Sửa bằng khoá phân biệt cuối chuỗi (thenComparingInt(Member::id)) để thứ tự nhất quán với equals.
Iterator fail-fast và fail-safe khác nhau thế nào?
Fail-fast ném ConcurrentModificationException khi collection bị sửa ngoài iterator; “fail-safe” thì không ném, nhưng đó là tên không chính thức cho hai loại khác nhau.
Fail-fast (ArrayList, HashMap) kiểm tra modCount, chỉ là best effort. Weakly consistent (ConcurrentHashMap) không ném, có thể thấy hoặc không thấy thay đổi mới. Snapshot (CopyOnWriteArrayList) duyệt trên bản chụp, mỗi lần ghi copy cả mảng. Chọn theo tỉ lệ đọc/ghi và việc có nhiều luồng hay không.
Senior
Xoá phần tử áp chót của ArrayList trong for-each không ném ConcurrentModificationException. Vì sao?
Vì hasNext() trả false trước khi next() kịp kiểm tra modCount, nên vòng lặp dừng sớm và phần tử cuối bị bỏ qua.
hasNext() của iterator ArrayList chỉ là cursor != size. Xoá phần tử áp chót làm size giảm đúng bằng cursor. Không có exception nhưng code sai. Bài học: fail-fast chỉ là best effort, phải dùng iterator.remove() hoặc removeIf.
Sửa field của một phần tử đang nằm trong TreeSet hoặc làm key HashMap thì chuyện gì xảy ra?
Cấu trúc không biết field đã đổi, nên phần tử “mất tích”: tìm không thấy, xoá không được, không có exception nào.
HashMap/HashSet: phần tử vẫn nằm ở bucket tính từ hash cũ,get/containstính ra bucket mới và không thấy nó.TreeSet/TreeMap: phần tử nằm sai vị trí trong cây, tìm kiếm đi sai nhánh,removecũng thất bại.- Hậu quả: dữ liệu mất và rò bộ nhớ. Cách phòng: chỉ dùng object immutable (record,
String) làm key và phần tử của set; buộc phải đổi thìremovera, sửa, rồi thêm lại.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu trong phỏng vấn |
|---|---|---|---|
| natural ordering | /ˈnætʃrəl ˈɔːrdərɪŋ/ | thứ tự tự nhiên (Comparable) | “TreeSet uses the natural ordering unless I pass a Comparator.” |
| consistent with equals | nhất quán với equals | “The comparator should be consistent with equals, or a TreeSet silently drops elements.” | |
| weakly consistent | /ˈwiːkli/ | nhất quán yếu (iterator) | “ConcurrentHashMap iterators are weakly consistent; they never throw CME.” |
| range query | /reɪndʒ ˈkwɪri/ | truy vấn theo khoảng | “TreeMap handles range queries with subMap and floorEntry.” |
| tie-breaker | /ˈtaɪ ˌbreɪkər/ | khoá phân biệt khi hoà | “I add the id as a final tie-breaker so the comparator never returns zero for different members.” |
| red-black tree | /rɛd blæk triː/ | cây đỏ-đen | “TreeMap is a red-black tree, so lookups are O(log n).” |
| comparator | /kəmˈpærətər/ | bộ so sánh | “I pass a comparator when the ordering depends on the screen.” |
| snapshot iterator | /ˈsnæpʃɑːt/ | iterator duyệt trên bản chụp | “CopyOnWriteArrayList gives a snapshot iterator, so it never sees later writes.” |
Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer) và tài liệu Java Core của Hỏi Dân IT, cộng thêm kiến thức tự tìm hiểu, viết lại theo cách hiểu của mình.