99 Ngày Java — Ngày 35: TreeMap & LinkedHashMap

Ngày 34 ta mở nắp capo HashMap và thấy cái giá của O(1): thứ tự bị vứt bỏ — duyệt map ra thứ tự tùy hứng theo bucket. Hôm nay gặp hai anh em lấy lại thứ tự theo hai cách khác nhau: TreeMap giữ key luôn được sắp xếp trên cây đỏ-đen và tặng kèm cả họ câu hỏi "gần nhất" qua NavigableMap; LinkedHashMap xâu sợi chỉ qua các entry để duyệt đúng thứ tự chèn mà vẫn O(1). Và tiết mục đinh: chỉnh một cờ + override một method, LinkedHashMap biến thành LRU cache hoàn chỉnh — câu hỏi thiết kế phỏng vấn kinh điển, giải trong mười dòng.

Sketchnote Ngày 35: TreeMap và LinkedHashMap — cây đỏ-đen với NavigableMap, danh sách liên kết giữ thứ tự chèn, access order và LRU cache với removeEldestEntry, bảng chọn map

TreeMap — key luôn được sắp xếp

// HashMap (Ngày 34) đánh đổi MỘT thứ lấy O(1): THỨ TỰ.
// Duyệt HashMap — thứ tự tùy hứng theo bucket. Hai anh em hôm nay lấy lại nó.

// TreeMap — key LUÔN được sắp xếp (cây đỏ-đen bên trong)
TreeMap<String, Integer> diem = new TreeMap<>();
diem.put("Minh", 8); diem.put("An", 9); diem.put("Trang", 7);
System.out.println(diem);   // {An=9, Minh=8, Trang=7} — theo alphabet, LUÔN LUÔN

// Cái giá: mọi thao tác O(log n) — không còn O(1) như HashMap
// (cây đỏ-đen tự cân bằng: 1 triệu entry → chỉ ~20 bước so sánh)

// Key phải SO SÁNH ĐƯỢC: Comparable — hoặc đưa Comparator vào constructor
TreeMap<String, Integer> khongPhanBietHoa =
    new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

// TreeMap KHÔNG nhận key null (so sánh với null nổ NullPointerException)
// HashMap cho 1 key null — TreeMap: cấm tuyệt đối

Bên trong là cây đỏ-đen tự cân bằng — đúng cấu trúc mà bucket của HashMap "treeify" thành khi quá dài (Ngày 34), nhưng ở đây là toàn bộ map: một triệu entry chỉ cần ~20 bước so sánh, mọi thao tác O(log n).
Key phải so sánh được: hoặc cài Comparable, hoặc đưa Comparator vào constructor — String.CASE_INSENSITIVE_ORDER là ví dụ có sẵn hay dùng nhất.
Khác biệt hay bị hỏi: TreeMap cấm key null (so sánh với null là NullPointerException), trong khi HashMap cho đúng một key null.

NavigableMap — họ câu hỏi "gần nhất"

// NavigableMap — siêu năng lực thật sự của TreeMap: câu hỏi "GẦN NHẤT"
// Bậc thuế thu nhập: từ mức lương nào → thuế suất nào?
TreeMap<Integer, String> bacThue = new TreeMap<>();
bacThue.put(0, "5%"); bacThue.put(10_000_000, "10%");
bacThue.put(18_000_000, "15%"); bacThue.put(32_000_000, "20%");

// Lương 25 triệu rơi vào bậc nào? floorEntry = entry có key LỚN NHẤT <= 25tr
bacThue.floorEntry(25_000_000);    // 18_000_000="15%" — MỘT dòng, O(log n)
// HashMap làm được không? Phải DUYỆT HẾT key rồi tự so — O(n) và dài dòng

// Cả họ hàng câu hỏi "gần nhất":
bacThue.ceilingKey(25_000_000);    // key nhỏ nhất >= 25tr → 32_000_000
bacThue.firstKey();                // 0        — nhỏ nhất
bacThue.lastEntry();               // 32tr=20% — lớn nhất

// Và LÁT CẮT theo khoảng — view sống, không copy:
bacThue.headMap(18_000_000);       // các bậc < 18tr
bacThue.tailMap(18_000_000);       // các bậc >= 18tr
bacThue.subMap(10_000_000, 32_000_000);  // [10tr, 32tr)

// Use case đúng chất: bậc giá/thuế, lịch (sự kiện kế tiếp?), range query theo thời gian
// TreeSet (Ngày 33) = TreeMap chỉ có key — cùng bộ floor/ceiling/subSet

Đây mới là lý do chọn TreeMap: floorEntry/ceilingKey trả lời "gần nhất về phía dưới/trên" trong O(log n) — bài toán bậc thuế, bậc giá, tìm khung giờ kế tiếp mà HashMap phải duyệt hết O(n) mới xong.
headMap/tailMap/subMap cắt lát theo khoảng và trả về view sống — không copy dữ liệu, sửa view là sửa map gốc; range query theo thời gian gọn một dòng.
Nối với Ngày 33: TreeSet chính là TreeMap chỉ giữ key — cùng bộ floor/ceiling/subSet, học một lần dùng hai nơi.

LinkedHashMap — O(1) mà vẫn giữ thứ tự

// LinkedHashMap — HashMap + sợi chỉ xuyên qua các entry
// Bên trong: bucket y hệt HashMap, CỘNG danh sách liên kết đôi nối mọi entry
// → tra cứu vẫn O(1), duyệt LUÔN theo THỨ TỰ CHÈN

LinkedHashMap<String, Integer> gioHang = new LinkedHashMap<>();
gioHang.put("áo", 2); gioHang.put("quần", 1); gioHang.put("nón", 3);
System.out.println(gioHang);  // {áo=2, quần=1, nón=3} — đúng thứ tự bỏ vào

// So sánh cùng dữ liệu:
// HashMap        → {nón=3, áo=2, quần=1}?  — tùy bucket, đổi theo capacity
// TreeMap        → {nón=3, quần=1, áo=2}   — theo alphabet
// LinkedHashMap  → {áo=2, quần=1, nón=3}   — theo lúc chèn ✅

// Chế độ hai: ACCESS ORDER — get() cũng đẩy entry xuống cuối
LinkedHashMap<String, Integer> ganDay =
    new LinkedHashMap<>(16, 0.75f, true);   // true = access order
// → entry ĐẦU danh sách luôn là "lâu không dùng nhất" — LRU tự nhiên!

// Đời thường bạn đã gặp nó: kết quả JSON giữ nguyên thứ tự field,
// thống kê theo ngày giữ đúng trình tự ngày — đều là LinkedHashMap

Cấu trúc lai thông minh: bucket y hệt HashMap (tra cứu O(1)) cộng danh sách liên kết đôi xuyên qua mọi entry (duyệt đúng thứ tự chèn) — trả giá chỉ vài con trỏ mỗi entry.
Chế độ thứ hai ít người biết: constructor ba tham số với accessOrder = true — mỗi get đẩy entry xuống cuối danh sách, nên đầu danh sách luôn là entry lâu không dùng nhất. Ghim ý này — đoạn sau ăn tiền.
Bạn gặp nó hằng ngày mà không biết: JSON giữ nguyên thứ tự field, thống kê theo ngày in đúng trình tự — các thư viện đều lót LinkedHashMap bên dưới.

Ảo thuật LRU cache trong mười dòng

// Ảo thuật hôm nay: LRU CACHE HOÀN CHỈNH trong ~10 dòng
// LRU (Least Recently Used): đầy thì đuổi phần tử LÂU KHÔNG DÙNG nhất
// — đúng chiến lược mà Redis, guava cache, buffer pool của DB đều xoay quanh

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int sucChua;

    LruCache(int sucChua) {
        super(16, 0.75f, true);          // access order BẬT
        this.sucChua = sucChua;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> giaNhat) {
        return size() > sucChua;         // quá sức chứa → tự đuổi entry già nhất
    }
}
// removeEldestEntry được LinkedHashMap GỌI SẴN sau mỗi put —
// trả true là entry đầu danh sách (lâu dùng nhất) bị gỡ. Thế là xong.

LruCache<String, String> cache = new LruCache<>(3);
cache.put("a","1"); cache.put("b","2"); cache.put("c","3");
cache.get("a");                    // "a" vừa được dùng → thoát án tử
cache.put("d","4");                // đầy! đuổi "b" — kẻ lâu không dùng nhất
System.out.println(cache.keySet());  // [c, a, d]

// Phỏng vấn "thiết kế LRU cache"? — HashMap + doubly-linked list.
// Bạn vừa thấy JDK lắp sẵn đúng bộ đôi đó trong MỘT class.
// (Đa luồng thì dùng Caffeine — LRU cache công nghiệp; phần Spring Ngày 36 gặp!)

Ghép hai mảnh vừa học: accessOrder = true (đầu danh sách = lâu dùng nhất) + override removeEldestEntry (LinkedHashMap tự gọi sau mỗi put, trả true là entry già nhất bị đuổi) — thành LRU cache đầy đủ.
Câu phỏng vấn "thiết kế LRU cache" đáp án chuẩn là HashMap + doubly-linked list — và bạn vừa thấy JDK lắp sẵn đúng bộ đôi đó trong một class: hiểu cấu trúc rồi thì mười dòng là xong.
Giới hạn thật thà: phiên bản này không thread-safe (Ngày 34 dặn rồi) — production đa luồng dùng Caffeine, chính là LRU cache công nghiệp mà phần Spring Ngày 36 sẽ cắm vào @Cacheable.

Bảng chọn map — dán cạnh bảng List và Set

// Bảng chọn map — dán cạnh bảng chọn List (32) và Set (33)
// ┌──────────────┬───────────────┬──────────┬──────────────────────────────┐
// │              │ Thứ tự        │ get/put  │ Chọn khi                     │
// ├──────────────┼───────────────┼──────────┼──────────────────────────────┤
// │ HashMap      │ ❌ không       │ O(1)     │ mặc định — 95% trường hợp    │
// │ LinkedHashMap│ ✅ chèn/access │ O(1)     │ cần giữ thứ tự, LRU cache    │
// │ TreeMap      │ ✅ sắp xếp     │ O(log n) │ range query, floor/ceiling   │
// └──────────────┴───────────────┴──────────┴──────────────────────────────┘
// Cùng họ Set (Ngày 33): HashSet / LinkedHashSet / TreeSet — y hệt logic

// Quy tắc nhanh:
// 1. Bắt đầu bằng HashMap. CHỈ đổi khi có lý do gọi tên được.
// 2. "In ra phải đúng thứ tự bỏ vào" → LinkedHashMap (đừng sort lại mỗi lần!)
// 3. "Câu hỏi gần nhất / khoảng" → TreeMap (đừng duyệt hết O(n)!)
// 4. Khai báo bằng interface: Map<K,V> m = new TreeMap<>();
//    — đổi cài đặt sau này chỉ sửa MỘT chữ (Ngày 31 dặn rồi)
// 5. Key: bất biến + equals/hashCode chuẩn (34) + Comparable nếu TreeMap

Quy tắc không đổi từ Ngày 31: mặc định HashMap, chỉ đổi khi gọi tên được lý do — "cần giữ thứ tự chèn" → LinkedHashMap, "cần câu hỏi gần nhất/khoảng" → TreeMap.
Hai mùi code đáng sửa ngay: sort lại keySet mỗi lần in (đáng lẽ TreeMap giữ sẵn) và duyệt hết map tìm "gần nhất" (đáng lẽ floorEntry một dòng).
Khai báo bằng interface Map<K,V> để đổi cài đặt chỉ sửa một chữ — và key vẫn tuân luật cũ: bất biến, equals/hashCode chuẩn, thêm Comparable nếu vào TreeMap.

Bài tập nhỏ

Đổ cùng 5 cặp key-value vào HashMap, LinkedHashMap, TreeMap rồi in cả ba — nhìn tận mắt ba kiểu thứ tự.
Xây bảng bậc thuế bằng TreeMap và viết hàm thueSuat(luong) bằng floorEntry — thêm test cho biên: đúng mốc 18 triệu thì rơi bậc nào?
Dùng subMap lấy các sự kiện trong khoảng hai mốc thời gian từ TreeMap<LocalDateTime, String>.
Tự viết LruCache như bài, sức chứa 3 — put/get theo kịch bản rồi in keySet() sau mỗi bước, dự đoán trước khi chạy.
Thử quên accessOrder = true trong LruCache — nó thành cache FIFO: đuổi theo thứ tự chèn, get không cứu được entry nữa. Thấy khác biệt chưa?

Kết luận

Ba map, ba lời hứa: HashMap — nhanh nhất, không thứ tự; LinkedHashMap — vẫn O(1), giữ thứ tự chèn (hoặc access order); TreeMap — O(log n) đổi lấy key sắp xếp và cả họ câu hỏi gần nhất của NavigableMap. Và bài học đắt nhất hôm nay: hiểu cấu trúc bên trong thì "thiết kế LRU cache" từ câu phỏng vấn đáng sợ thành mười dòng code — accessOrder + removeEldestEntry, xong. Ngày 36 ta rời họ Map sang nhánh còn lại của cây Collection: Queue, Deque & Stack — hàng đợi FIFO, chồng đĩa LIFO, và vì sao ArrayDeque một mình đóng cả hai vai. Hẹn gặp lại!