Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánMid16 phút đọc

Java Collections: TreeSet, TreeMap, Comparator và Iterator

Ôn 10 thẻ
Trong bài này

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:

  • compareTo của phần tử (natural ordering, phần tử phải implement Comparable).
  • Một Comparator truyề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
  • HashMap cho một key null, HashSet cho một phần tử null.
  • TreeMap/TreeSet với natural ordering ném NullPointerException khi gặp key null, vì phải gọi compareTo. Chúng chỉ chấp nhận null nếu Comparator tự xử lý, ví dụ Comparator.nullsFirst(...).
  • ConcurrentHashMap cấm null cả ở 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ụ String theo bảng chữ cái, Integer theo giá trị, LocalDate theo 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.

  • Iterator dùng được cho mọi Collection: hasNext, next, remove.
  • ListIterator chỉ 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 đó:

  1. ArrayList<Member>: thêm 5 thành viên, in ra.
  2. 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.
  3. TreeSet<Member>: bỏ các thành viên vào để có bảng xếp hạng theo tuổi, in ra.
  4. 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.
  5. 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ết equals/hashCode. Đề gợi ý phải viết, nhưng Integer đã có sẵn cả hai. Chỉ khi bỏ chính Member vào HashSet mớ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, TreeSet giữ 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êm id làm khoá phân biệt cuối, nhờ đó thứ tự nhất quán với equals củ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ần containsKey + get + put. Muốn “chưa có thì tạo với 10 điểm” thì dùng merge(1, 10, Integer::sum).
  • TreeMap luôn in theo id tăng dần dù thêm theo thứ tự 3, 1, 5, 2, 4. HashMap với key Integer nhỏ trông cũng “có thứ tự”, nhưng đó là trùng hợp do hash của Integer là chính nó; đừng dựa vào.
  • Khai báo bằng NavigableSet/NavigableMap thay vì Set/Map khi cần ceilingEntry, headSet…

Một senior sẽ cải thiện thêm:

  • Giữ Member immutable (record, không setter). Đề yêu cầu setter, nhưng sửa age của phần tử đang nằm trong TreeSet làm hỏng cây (phần tử nằm sai vị trí, contains trả false), y như sửa key trong HashMap.
  • Đừng nhét thứ tự “theo tuổi” vào compareTo nếu đó chỉ là thứ tự của một màn hình. Thứ tự tự nhiên hợp lý hơn là theo id; bảng xếp hạng dùng Comparator riêng (mục 2).
  • Nhiều luồng cùng cộng điểm thì HashMap không an toàn: dùng ConcurrentHashMap.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 TreeSet có thể “nuốt” một phần tử khác equals, và cách sửa bằng khoá phân biệt.
  • Biết khi nào chọn TreeMap thay HashMap, và viết được floorEntry/subMap cho 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ùng Comparator.
  • Giải thích được modCount và 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/contains tí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, remove cũ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ì remove ra, 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.