Cài LRU cache chỉ bằng thư viện chuẩn của Java thì làm thế nào?

Dùng LinkedHashMap với access-order rồi override removeEldestEntry.

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

    LruCache(int capacity) {
        super(16, 0.75f, true);       // accessOrder = true
        this.capacity = capacity;
    }

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

Cơ chế:
- Constructor 3 tham số với accessOrder = true khiến mỗi lần get/put đẩy entry được truy cập về cuối danh sách liên kết nội bộ. Entry ở đầu là entry lâu chưa dùng nhất.
- Sau mỗi put, HashMap gọi removeEldestEntry; trả về true thì entry đầu bị loại.
- Mặc định (accessOrder = false) thì LinkedHashMap giữ thứ tự chèn — đây mới là công dụng hay dùng nhất của nó.

Giới hạn cần nói khi phỏng vấn: class này không thread-safe (phải bọc Collections.synchronizedMap, và vẫn phải tự đồng bộ khi duyệt), không có TTL, không có thống kê hit/miss. Cache production thường dùng Caffeine hoặc Redis; LinkedHashMap hợp cho cache nhỏ trong một tiến trình.