Có một câu hỏi phỏng vấn kinh điển: cài đặt một bộ nhớ đệm LRU. Ứng viên thường bắt đầu vẽ một HashMap cộng một danh sách liên kết đôi, và mất hai mươi phút.

Trong Java, câu trả lời đúng là sáu dòng — vì LinkedHashMap đã làm gần hết phần khó.

Nhưng trước khi tới đó, phải hiểu tham số thứ ba của nó.

Thứ tự chèn: mặc định

LinkedHashMap là HashMap cộng thêm một danh sách liên kết đôi xuyên qua mọi phần tử. Nhờ đó nó nhớ thứ tự — điều mà HashMap không làm.

LinkedHashMap<String,Integer> chen = new LinkedHashMap<>();
for (String k : List.of("a","b","c","d")) chen.put(k, 1);
chen.get("a"); chen.get("b");

  sau khi đọc a, b: [a, b, c, d]

Đọc phần tử không đổi thứ tự. Đây là hành vi mặc định, và nó đủ dùng cho 90% trường hợp: giữ nguyên thứ tự người dùng nhập, thứ tự cột trong file CSV, thứ tự trường khi sinh JSON.

Thứ tự truy cập: một tham số đổi hẳn mọi thứ

new LinkedHashMap<>(16, 0.75f, true);
//                            ^^^^ accessOrder

  ban đầu          : [a, b, c, d]
  sau khi đọc a    : [b, c, d, a]
  sau khi đọc c    : [b, d, a, c]

Giờ mỗi lần get đẩy phần tử xuống cuối. Danh sách luôn xếp từ "lâu chưa dùng nhất" ở đầu tới "vừa dùng" ở cuối.

Đó chính xác là thứ tự mà một bộ nhớ đệm LRU cần.

Ở chế độ thứ tự truy cập, ngay cả get cũng là thao tác sửa cấu trúc. Nên duyệt map trong lúc luồng khác đang đọc sẽ ném ConcurrentModificationException — và điều này khiến người ta bất ngờ, vì get trông như thao tác chỉ đọc. Muốn dùng nhiều luồng thì phải tự đồng bộ, hoặc chuyển sang Caffeine.

removeEldestEntry: phương thức sinh ra để bị ghi đè

LinkedHashMap có một phương thức protected luôn trả về false:

protected boolean removeEldestEntry(Map.Entry<K,V> cuNhat) {
    return false;
}

Nó được gọi sau mỗi lần put, và nếu trả về true thì phần tử cũ nhất bị loại. Toàn bộ bộ nhớ đệm LRU nằm ở đó:

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

    BoNhoDem(int sucChua) {
        super(16, 0.75f, true);       // thứ tự truy cập
        this.sucChua = sucChua;
    }

    @Override protected boolean removeEldestEntry(Map.Entry<K, V> cuNhat) {
        return size() > sucChua;
    }
}

Chạy với sức chứa 3:

  nạp A B C        : [A, B, C]
  đọc A            : [B, C, A]
  thêm D (đầy)     : [C, A, D]   <- B bị đẩy ra
  thêm E           : [A, D, E]   <- C bị đẩy ra
  get(B) = null

Đọc kỹ dòng thứ ba. Khi thêm D, phần tử bị loại là B chứ không phải A — dù A vào trước. Vì A vừa được đọc nên nó đã nhảy xuống cuối, còn B trở thành cái lâu chưa dùng nhất.

Đó là toàn bộ ý nghĩa của chữ "LRU": least recently used — lâu chưa dùng nhất, không phải cũ nhất.

Đây là chỗ kế thừa hợp lý

Bài về kế thừa đã kết luận nên ưu tiên thành phần. Nhưng đây là một trong số ít chỗ kế thừa đúng, và đáng phân tích vì sao:

removeEldestEntry được thiết kế có chủ đích cho việc ghi đè. Tài liệu của nó nói rõ khi nào được gọi, được phép làm gì. Đây là mẫu phương thức khuôn mẫu ở bài lớp trừu tượng — lớp cha giữ trình tự, để trống đúng một điểm.

So với TapDem extends HashSet ở bài kế thừa: ở đó ta phụ thuộc vào một chi tiết cài đặt không được ghi trong tài liệu (addAll gọi add). Ở đây ta dùng đúng điểm mở rộng mà tác giả đã chuẩn bị.

Khác biệt giữa "kế thừa tồi" và "kế thừa tốt" nằm ở chỗ đó, không nằm ở bản thân từ khoá extends.

Sequenced API của Java 21

LinkedHashMap là SequencedMap, nên từ Java 21 có thêm:

  firstEntry : x=1
  lastEntry  : z=1
  reversed   : [z, y, x]
  putFirst w : [w, x, y, z]

Trước đây lấy phần tử đầu tiên phải viết map.entrySet().iterator().next(), còn phần tử cuối thì phải duyệt hết. Giờ có tên gọi tử tế.

reversed() trả về khung nhìn, không sao chép — sửa nó thì map gốc đổi theo.

Khi nào đừng tự viết cache

Sáu dòng ở trên là bài học tốt, nhưng với hệ thống chạy thật thì tôi khuyên dùng thư viện — Caffeine là lựa chọn mặc định trong hệ sinh thái Java.

Lý do không phải vì mã trên sai, mà vì cache thật cần nhiều thứ hơn:

Hết hạn theo thời gian, không chỉ theo sức chứa. Dữ liệu cũ 10 phút thường nên bỏ dù cache chưa đầy.

An toàn nhiều luồng mà không khoá toàn bộ map.

Số liệu: tỷ lệ trúng, số lần loại bỏ — không có chúng thì bạn không biết cache có ích hay không.

Nạp lại tự động khi thiếu, và chỉ nạp một lần dù mười luồng cùng hỏi.

Thuật toán tốt hơn LRU. Caffeine dùng W-TinyLFU, chống được kiểu truy cập quét một lượt qua toàn bộ dữ liệu — thứ làm LRU mất sạch nội dung hữu ích.

Cái LRU sáu dòng vẫn hợp cho: bộ nhớ đệm nhỏ trong một lớp, dữ liệu không bao giờ cũ, và mã chạy một luồng.

Vài chi tiết khác

LinkedHashMap tốn bộ nhớ hơn HashMap — mỗi phần tử thêm hai con trỏ. Đổi lại việc duyệt lại nhanh hơn, vì nó đi theo danh sách liên kết thay vì quét cả bảng băm, kể cả những ngăn rỗng.

Duyệt một HashMap thưa thớt là quét toàn bộ bảng. Một map từng có một triệu phần tử rồi xoá còn mười vẫn phải quét bảng một triệu ô mỗi lần duyệt. LinkedHashMap không có vấn đề đó.

LinkedHashSet hoạt động y hệt, cho Set.

Sinh JSON có thứ tự trường ổn định là một công dụng ít được nhắc: dùng LinkedHashMap thì hai lần sinh cho cùng một chuỗi, tiện cho việc so sánh và cho kiểm thử.

Thử ba mươi giây

Lấy lớp BoNhoDem ở trên, đổi super(16, 0.75f, true) thành super(16, 0.75f, false) rồi chạy lại đúng kịch bản đó.

Lần này khi thêm D, phần tử bị loại sẽ là A chứ không phải B — vì không còn thứ tự truy cập, "cũ nhất" quay về nghĩa "vào trước nhất". Bạn vừa biến LRU thành FIFO bằng cách đổi một chữ.

Ngày mai: TreeMap — cây đỏ đen, và những phép truy vấn theo khoảng mà HashMap không làm được.