HashMap trả lời được đúng một câu hỏi: khoá này có giá trị gì? Nhanh, O(1), và đủ cho phần lớn công việc.

Nhưng có một loại câu hỏi nó không trả lời được, và người ta hay giải bằng vòng lặp:

Khoá lớn nhất mà không vượt quá 300 là bao nhiêu?

Cho tôi mọi bản ghi từ tháng 1 tới tháng 3.

Giá trị nhỏ nhất trong map là gì?

TreeMap giữ khoá theo thứ tự sắp xếp trong một cây đỏ đen, nên trả lời cả ba trong O(log n).

Bảng giá theo bậc

Đây là bài toán tôi gặp thường xuyên nhất: mua càng nhiều càng rẻ.

TreeMap<Integer,Integer> bacGia = new TreeMap<>();
bacGia.put(0,    10_000);
bacGia.put(100,   8_000);
bacGia.put(500,   6_500);
bacGia.put(1000,  5_000);

Cách viết thường gặp là một chuỗi if:

if (sl >= 1000) return 5_000;
if (sl >= 500)  return 6_500;
if (sl >= 100)  return 8_000;
return 10_000;

Với TreeMap, một dòng:

bacGia.floorEntry(soLuong).getValue();

  mua     1 -> bậc từ    0, đơn giá 10,000
  mua    99 -> bậc từ    0, đơn giá 10,000
  mua   100 -> bậc từ  100, đơn giá  8,000
  mua   300 -> bậc từ  100, đơn giá  8,000
  mua  1500 -> bậc từ 1000, đơn giá  5,000

floorEntry(x) trả về phần tử có khoá lớn nhất mà không vượt quá x — đúng định nghĩa của "bậc giá áp dụng".

Ưu điểm không chỉ là ngắn: bảng bậc giờ là dữ liệu, không phải mã. Đọc từ cấu hình, sửa lúc chạy, thêm bậc mới mà không đụng tới một dòng lệnh nào.

Bốn phương thức điều hướng

  floorKey(35)   : 30   (<= 35)
  ceilingKey(35) : 40   (>= 35)
  lowerKey(30)   : 20   (< 30, chặt)
  higherKey(30)  : 40   (> 30, chặt)
  floorKey(5)    : null (không có)

Cách nhớ: floor và ceiling là "sàn" và "trần" — có bao gồm giá trị bằng. lower và higher thì chặt, loại giá trị bằng ra.

Mỗi cái có ba biến thể: ...Key trả khoá, ...Entry trả cả cặp, và không có gì thì trả null. Nên luôn nhớ kiểm null — không có khoá nào thoả điều kiện là chuyện bình thường.

Kèm theo là firstKey(), lastKey(), firstEntry(), lastEntry(), và hai bản có xoá luôn: pollFirstEntry(), pollLastEntry() — tiện khi dùng TreeMap như một hàng đợi ưu tiên có tra cứu.

Truy vấn theo khoảng

  headMap(30)       : {10=v10, 20=v20}
  headMap(30, true) : {10=v10, 20=v20, 30=v30}
  tailMap(30)       : {30=v30, 40=v40, 50=v50}
  subMap(20, 40)    : {20=v20, 30=v30}
  descendingMap     : {50=v50, 40=v40, 30=v30, 20=v20, 10=v10}

Chú ý quy ước biên, vì nó gây nhầm nhiều nhất:

headMap(x) — loại x. tailMap(x) — bao gồm x. Không đối xứng, và tôi vẫn phải kiểm lại mỗi lần dùng.

subMap(a, b) — bao gồm a, loại b, giống như substring.

Muốn khác thì dùng bản có tham số boolean: headMap(30, true), subMap(20, true, 40, true).

Áp vào dữ liệu theo thời gian thì rất gọn:

TreeMap<LocalDate,Integer> doanhThu = new TreeMap<>();
var q1 = doanhThu.subMap(LocalDate.of(2026,1,1), LocalDate.of(2026,4,1));

  quý 1: [100, 250, 180] tổng = 530

Không vòng lặp, không so sánh ngày thủ công. Và vì TreeMap đã sắp xếp, việc lấy khoảng là O(log n) để tìm điểm đầu rồi duyệt tuyến tính phần cần — thay vì quét cả map.

Khung nhìn là "sống"

Đây là chi tiết quan trọng nhất và cũng hay bị bỏ qua: headMap, tailMap, subMap, descendingMap đều trả về khung nhìn, không phải bản sao.

  sau khi put(25)    : {20=v20, 25=v25, 30=v30}     <- thêm vào map gốc
  put vào khung nhìn : m = [10, 20, 25, 30, 35, 40, 50]
  put(99) ngoài khoảng : IllegalArgumentException

Ba hành vi:

Thêm vào map gốc trong khoảng thì khung nhìn thấy ngay.

Thêm vào khung nhìn thì map gốc cũng có.

Thêm khoá ngoài khoảng vào khung nhìn thì ném IllegalArgumentException — khung nhìn tự bảo vệ ranh giới của nó.

Điều này rất mạnh nhưng cũng là chỗ dễ sai: nếu bạn định lấy một bản sao độc lập, phải viết new TreeMap<>(m.subMap(a, b)).

Cây đỏ đen: cái giá phải trả

TreeMap là cây nhị phân tìm kiếm tự cân bằng. Mọi thao tác chính — get, put, remove — đều O(log n), so với O(1) trung bình của HashMap.

Với một triệu phần tử, đó là khoảng 20 lần so sánh thay vì một phép băm. Không nhiều, nhưng đủ để thấy được trong vòng lặp nóng.

Đổi lại TreeMap cho bạn: thứ tự, truy vấn theo khoảng, và hiệu năng ổn định — không có trường hợp xấu O(n) như HashMap khi hàm băm tồi.

Vài điểm khác biệt cần nhớ:

TreeMap không nhận khoá null — nó phải so sánh khoá, mà null.compareTo là NPE. HashMap thì nhận, như bài bản đồ đã đo.

Khoá phải Comparable, hoặc phải truyền Comparator khi tạo map. Đây là chỗ hay quên với lớp tự viết.

compareTo quyết định "bằng nhau", không phải equals. Đúng cái bẫy BigDecimal ở bài Comparable: TreeMap coi 1.0 và 1.00 là cùng một khoá, còn HashMap thì không.

Khi nào dùng

Dùng TreeMap khi:

Cần truy vấn theo khoảng — thời gian, khoảng giá, phạm vi số.

Cần tra cứu gần đúng — bậc giá, mức thuế, ngưỡng cấu hình.

Cần duyệt theo thứ tự thường xuyên. Sắp xếp một HashMap mỗi lần hiển thị thì TreeMap rẻ hơn.

Cần phần tử nhỏ nhất/lớn nhất liên tục.

Dùng HashMap cho mọi thứ còn lại. Và nếu chỉ cần thứ tự chèn thì LinkedHashMap nhanh hơn TreeMap mà vẫn có thứ tự — đúng bài hôm qua.

TreeSet cũng vậy

Mọi thứ trên áp dụng y hệt cho TreeSet, chỉ khác là không có giá trị:

TreeSet<Integer> s = new TreeSet<>(List.of(10, 20, 30));
s.floor(25);        // 20
s.ceiling(25);      // 30
s.headSet(25);      // [10, 20]
s.descendingSet();  // [30, 20, 10]

Một công dụng đáng nhớ: TreeSet dùng làm hàng đợi có sắp xếp mà không trùng lặp — thứ mà PriorityQueue không làm được vì nó cho phép trùng và không có contains nhanh.

Thử ba mươi giây

Lấy một chuỗi if-else so sánh ngưỡng trong dự án của bạn — bậc giá, mức phí, khung điểm — và viết lại bằng TreeMap với floorEntry.

Đếm số dòng trước và sau. Rồi thử thêm một bậc mới vào cả hai bản: một bên là sửa mã và biên dịch lại, một bên là thêm một dòng dữ liệu.

Ngày mai: ba loại Set — HashSet, LinkedHashSet, TreeSet — chi phí và thứ tự duyệt của từng loại, cùng câu hỏi "bằng nhau nghĩa là gì" mà mỗi loại trả lời một kiểu.