Hình dung hai cách giữ một mớ từ. HashMap là một đống thẻ ghi vứt trong hộp: tra đúng từ bạn cần thì nhanh không đâu bằng, nhưng hỏi "từ nào đứng ngay trước từ này theo bảng chữ cái" thì chịu — phải lật cả hộp. TreeMap là cuốn từ điển đóng gáy xếp theo vần: lật tới đâu cũng biết ngay cái gì đứng trước, cái gì đứng sau, và cả một khoảng liền nhau. Cái giá là tra một từ hơi chậm hơn chút; đổi lại là cả một họ câu hỏi mà đống thẻ lộn xộn không bao giờ trả lời được. Hôm nay là về những câu hỏi đó.

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.

Muốn tự thấy khác biệt thì lấy một chuỗi if-else so sánh ngưỡng trong dự á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.

Mẫu số chung

Sự phân đôi "map băm cho tra cứu bằng nhau, map sắp xếp cho truy vấn khoảng" không phải của riêng Java — nó là một quyết định cấu trúc dữ liệu nền tảng mà mọi ngôn ngữ, và cả cơ sở dữ liệu, đều phải chọn.

  • C++ làm nổi bật nhất: std::unordered_map (bảng băm) và std::map — mà std::map chính là một cây đỏ đen, y hệt TreeMap, với lower_bound/upper_bound đóng đúng vai ceilingKey/higherKey. Ai học C++ rồi sang Java thấy quen ngay.
  • C# tách rõ Dictionary (băm), SortedDictionary (cây, như TreeMap) và SortedList (mảng sắp xếp — tra nhanh nhưng chèn chậm). Go thì nổi tiếng không có map sắp xếp trong thư viện chuẩn: cách làm chính thống là giữ slice rồi sort cộng sort.Search (tìm nhị phân) — đúng bài toán, chỉ là ráp tay.
  • Python cũng không có dict sắp xếp dựng sẵn, nhưng có module bisect cho tìm-vị-trí-chèn trên danh sách đã sắp (chính là floor/ceiling), và thư viện sortedcontainers rất được ưa dùng.
  • Chỗ sâu nhất là cơ sở dữ liệu: một chỉ mục hash chỉ trả lời WHERE x = ?, còn chỉ mục B-tree (họ hàng của cây đỏ đen, được thiết kế cho đĩa) mới trả lời WHERE x BETWEEN a AND b và ORDER BY x. Đây chính xác là khác biệt HashMap với TreeMap, phóng to lên quy mô hàng tỉ dòng — và là lý do khi truy vấn của bạn có khoảng hoặc sắp xếp, đúng loại chỉ mục quyết định nó chạy trong mili giây hay quét cả bảng.

Sợi chỉ chung đáng mang theo: giữ dữ liệu có thứ tự tốn hơn một chút, nhưng mở khoá cả một lớp câu hỏi mà cấu trúc không thứ tự không bao giờ trả lời rẻ được — "cái gì đứng ngay trước/sau x" và "mọi thứ giữa a và b". Câu hỏi để chọn đúng, ở bất kỳ ngôn ngữ hay ở tầng CSDL, luôn giống nhau: tôi chỉ tra cứu bằng khoá chính xác, hay tôi còn hỏi theo khoảng và theo thứ tự? Trả lời "chỉ bằng khoá" thì băm nhanh hơn; trả lời "có khoảng" thì cây/B-tree là thứ duy nhất làm được mà không quét toàn bộ.

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.