Mini-challenge: LRU Cache generic với LinkedHashMap

Đây là mini-challenge khép lại module Generics & Collections. Bạn sẽ xây một LRU Cache (Least Recently Used) — cấu trúc dữ liệu phổ biến: giữ tối đa N entry, khi vượt giới hạn thì evict entry truy cập cũ nhất. Dùng làm browser cache, CPU cache, database query cache.

Yêu cầu: generic <K, V> để dùng được với mọi kiểu key/value, tận dụng LinkedHashMap(accessOrder=true) của JDK thay vì tự viết doubly-linked list + hash table.

Mục tiêu: kết hợp generics, collections, và hiểu vì sao JDK bày sẵn công cụ cho pattern phổ biến như LRU.

🎯 Đề bài

Thiết kế LruCache<K, V>:

1. class LruCache<K, V>

• Constructor LruCache(int maxSize) — throw IllegalArgumentException nếu maxSize ≤ 0.
• V get(K key) — trả value, return null nếu không có. Đồng thời đánh dấu key là "vừa truy cập".
• void put(K key, V value) — thêm/cập nhật. Nếu vượt maxSize, evict entry cũ nhất (LRU).
• int size() — số entry hiện tại.
• boolean contains(K key) — không cập nhật access order.
• void clear() — xoá tất cả.

2. Yêu cầu impl

• Bên dưới dùng LinkedHashMap<K, V> với accessOrder = true.
• Override removeEldestEntry để evict tự động khi vượt maxSize.
• Wrap trong class riêng, không expose LinkedHashMap ra ngoài (encapsulation).

3. Sau đó tạo ThreadSafeLruCache<K, V> (bonus)

• Cùng API nhưng thread-safe bằng ReentrantLock.

Output mẫu:

-- Simple LRU --
put(a, 1)
put(b, 2)
put(c, 3)
get(a) = 1              // a bay gio moi nhat
put(d, 4)               // vuot 3 entry -> evict b (cu nhat)
size = 3
contains(b) = false
contains(a) = true
contains(c) = true
contains(d) = true

📦 Concept dùng trong bài

▶️ Starter code

import java.util.*;
import java.util.concurrent.locks.*;

public class LruCacheApp {

    // TODO: class LruCache<K, V>
    //   - field private final Map<K, V> map = LinkedHashMap(maxSize, 0.75, true) override removeEldestEntry
    //   - field private final int maxSize
    //   - constructor validate maxSize > 0
    //   - get, put, size, contains, clear

    // TODO: class ThreadSafeLruCache<K, V>
    //   - wrap LruCache voi ReentrantLock cho moi method

    public static void main(String[] args) {
        System.out.println("-- Simple LRU --");
        LruCache<String, Integer> cache = new LruCache<>(3);
        cache.put("a", 1); System.out.println("put(a, 1)");
        cache.put("b", 2); System.out.println("put(b, 2)");
        cache.put("c", 3); System.out.println("put(c, 3)");

        System.out.println("get(a) = " + cache.get("a"));   // 1, a moi nhat
        cache.put("d", 4); System.out.println("put(d, 4)"); // evict b

        System.out.println("size = " + cache.size());
        System.out.println("contains(b) = " + cache.contains("b"));
        System.out.println("contains(a) = " + cache.contains("a"));
        System.out.println("contains(c) = " + cache.contains("c"));
        System.out.println("contains(d) = " + cache.contains("d"));
    }
}

javac LruCacheApp.java
java LruCacheApp

Dành 25–30 phút tự làm.

💡 Gợi ý

public static class LruCache<K, V> {
    private final Map<K, V> map;
    private final int maxSize;

    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize must be > 0, got " + maxSize);
        }
        this.maxSize = maxSize;
        // accessOrder = true -> iterate/evict theo thu tu truy cap cuoi
        this.map = new LinkedHashMap<K, V>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > LruCache.this.maxSize;
            }
        };
    }

    public V get(K key) {
        return map.get(key);   // LinkedHashMap cap nhat order tu dong
    }

    public void put(K key, V value) {
        map.put(key, value);   // removeEldestEntry tu check va evict
    }

    public int size() { return map.size(); }

    public boolean contains(K key) {
        // containsKey KHONG update access order (unlike get)
        return map.containsKey(key);
    }

    public void clear() { map.clear(); }
}

public static class ThreadSafeLruCache<K, V> {
    private final LruCache<K, V> delegate;
    private final ReentrantLock lock = new ReentrantLock();

    public ThreadSafeLruCache(int maxSize) {
        this.delegate = new LruCache<>(maxSize);
    }

    public V get(K key) {
        lock.lock();
        try { return delegate.get(key); }
        finally { lock.unlock(); }
    }

    public void put(K key, V value) {
        lock.lock();
        try { delegate.put(key, value); }
        finally { lock.unlock(); }
    }

    public int size() {
        lock.lock();
        try { return delegate.size(); }
        finally { lock.unlock(); }
    }

    public boolean contains(K key) {
        lock.lock();
        try { return delegate.contains(key); }
        finally { lock.unlock(); }
    }

    public void clear() {
        lock.lock();
        try { delegate.clear(); }
        finally { lock.unlock(); }
    }
}

✅ Lời giải

import java.util.*;
import java.util.concurrent.locks.*;

public class LruCacheApp {

    public static class LruCache<K, V> {
        private final Map<K, V> map;
        private final int maxSize;

        public LruCache(int maxSize) {
            if (maxSize <= 0) {
                throw new IllegalArgumentException("maxSize must be > 0, got " + maxSize);
            }
            this.maxSize = maxSize;
            this.map = new LinkedHashMap<K, V>(16, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > LruCache.this.maxSize;
                }
            };
        }

        public V get(K key) { return map.get(key); }
        public void put(K key, V value) { map.put(key, value); }
        public int size() { return map.size(); }
        public boolean contains(K key) { return map.containsKey(key); }
        public void clear() { map.clear(); }
    }

    public static class ThreadSafeLruCache<K, V> {
        private final LruCache<K, V> delegate;
        private final ReentrantLock lock = new ReentrantLock();

        public ThreadSafeLruCache(int maxSize) {
            this.delegate = new LruCache<>(maxSize);
        }

        public V get(K key) {
            lock.lock();
            try { return delegate.get(key); }
            finally { lock.unlock(); }
        }

        public void put(K key, V value) {
            lock.lock();
            try { delegate.put(key, value); }
            finally { lock.unlock(); }
        }

        public int size() {
            lock.lock();
            try { return delegate.size(); }
            finally { lock.unlock(); }
        }

        public boolean contains(K key) {
            lock.lock();
            try { return delegate.contains(key); }
            finally { lock.unlock(); }
        }

        public void clear() {
            lock.lock();
            try { delegate.clear(); }
            finally { lock.unlock(); }
        }
    }

    public static void main(String[] args) {
        System.out.println("-- Simple LRU --");
        LruCache<String, Integer> cache = new LruCache<>(3);

        cache.put("a", 1); System.out.println("put(a, 1)");
        cache.put("b", 2); System.out.println("put(b, 2)");
        cache.put("c", 3); System.out.println("put(c, 3)");

        System.out.println("get(a) = " + cache.get("a"));
        cache.put("d", 4); System.out.println("put(d, 4)");

        System.out.println("size = " + cache.size());
        System.out.println("contains(b) = " + cache.contains("b"));
        System.out.println("contains(a) = " + cache.contains("a"));
        System.out.println("contains(c) = " + cache.contains("c"));
        System.out.println("contains(d) = " + cache.contains("d"));

        System.out.println("\n-- ThreadSafe LRU (demo) --");
        ThreadSafeLruCache<Integer, String> tsCache = new ThreadSafeLruCache<>(2);
        tsCache.put(1, "one");
        tsCache.put(2, "two");
        tsCache.put(3, "three");   // evict 1
        System.out.println("get(1) = " + tsCache.get(1));
        System.out.println("get(2) = " + tsCache.get(2));
        System.out.println("get(3) = " + tsCache.get(3));
    }
}

🎓 Mở rộng

Mức 1 — Thống kê hit/miss:

private long hits = 0;
private long misses = 0;

public V get(K key) {
    V v = map.get(key);
    if (v != null) hits++;
    else misses++;
    return v;
}

public double hitRate() {
    long total = hits + misses;
    return total == 0 ? 0 : (double) hits / total;
}

Mức 2 — TTL (Time-To-Live):

Wrap value với timestamp, evict khi quá hạn:

record Entry<V>(V value, long expiresAt) { }

LruCache<String, Entry<Data>> cache = new LruCache<>(100);
cache.put("key", new Entry<>(data, System.currentTimeMillis() + 60_000));

// Khi get:
Entry<Data> e = cache.get("key");
if (e == null || System.currentTimeMillis() > e.expiresAt()) return null;
return e.value();

Production thường dùng Caffeine library — LRU + TTL + async refresh + W-TinyLFU eviction. Nhưng viết tay 1 lần để hiểu nền tảng.

Mức 3 — Unit test concurrent:

@Test
void threadSafeUnderContention() throws Exception {
    var cache = new ThreadSafeLruCache<Integer, Integer>(100);
    ExecutorService executor = Executors.newFixedThreadPool(10);

    for (int i = 0; i < 10_000; i++) {
        final int key = i % 50;
        executor.submit(() -> cache.put(key, key * 2));
        executor.submit(() -> cache.get(key));
    }

    executor.shutdown();
    executor.awaitTermination(10, TimeUnit.SECONDS);

    assertTrue(cache.size() <= 100);
    // Khong co ConcurrentModificationException, khong co NPE
}

Test với LruCache non-safe dưới concurrent → crash hoặc corrupted. ThreadSafeLruCache → clean.

Mức 4 — Thay ReentrantLock bằng cơ chế khác — trade-off:

• synchronized / Collections.synchronizedMap: đơn giản nhất, ít code, nhưng không có tryLock / timeout, và khi iterate vẫn phải tự synchronized bên ngoài.
• ReentrantLock: flexible (tryLock, fairness, condition) — lựa chọn của lời giải trên.
• ConcurrentHashMap: scalable hơn (lock striping), nhưng không support LRU built-in. Phải tự build LRU trên nó — phức tạp, thường dùng Caffeine thay.

Còn ReentrantReadWriteLock? — cái bẫy đáng học nhất ở đây.

Cache thường read-heavy (nhiều get, ít put), nên trực giác mách bảo: dùng ReentrantReadWriteLock để nhiều thread get song song qua read lock, chỉ put mới cần write lock. Phiên bản sau trông hợp lý nhưng SAI:

// SAI — KHONG duoc dung read lock cho get() khi accessOrder = true
public V get(K key) {
    readLock.lock();
    try { return delegate.get(key); }   // get() MUTATE linked list ben duoi!
    finally { readLock.unlock(); }
}

Vì sao sai? Bài 05 — Map và Set đã cảnh báo đúng điểm này: với LinkedHashMap(accessOrder = true), get() không phải thao tác chỉ đọc — nó di chuyển entry vừa truy cập xuống cuối doubly-linked list nội bộ để cập nhật vị trí most-recently-used. Read lock cho phép nhiều thread cùng vào get song song, nghĩa là nhiều thread cùng sửa các con trỏ prev/next của linked list một lúc → pointer corruption. Hậu quả y hệt như không lock gì: dữ liệu sai lệch, hoặc CPU treo 100% vì linked list bị nối thành vòng khi duyệt.

Kết luận: với LRU cache dựa trên accessOrder = true, mọi thao tác get/put đều là thao tác ghi → tất cả phải đi qua write lock. Lúc đó ReentrantReadWriteLock mất sạch lợi thế (không còn gì chạy song song được) mà còn chậm hơn ReentrantLock thường vì overhead quản lý 2 lock. ReadWriteLock chỉ có lợi khi thao tác đọc thật sự không mutate — ví dụ map accessOrder = false, nhưng khi đó cache không còn là LRU nữa.

Bảng so sánh trade-off giữa các cơ chế thread-safe:

✨ Điều bạn vừa làm được

Hoàn thành mini-challenge này, bạn đã:

• Viết generic class <K, V> dùng được với mọi kiểu — không phải StringCache, IntCache riêng.
• Tận dụng LinkedHashMap(accessOrder=true) của JDK thay vì tự build doubly-linked list + hash table. Principle: "know your stdlib" — nhiều pattern đã có trong JDK.
• Áp dụng encapsulation: field private final, map không lộ ra ngoài, API clean.
• Phân biệt get vs containsKey semantics — intent-revealing API.
• Dùng composition (ThreadSafeLruCache wrap LruCache) thay vì inheritance — nguyên tắc từ bài Composition over inheritance.
• Áp pattern lock + try/finally đảm bảo unlock an toàn — tránh deadlock khi exception.
• Validate input trong constructor (throw IllegalArgumentException) — fail fast với config sai.

Chúc mừng — bạn đã hoàn thành module Generics & Collections! Từ đây bạn có công cụ mô hình dữ liệu đầy đủ (generic + collections). Module tiếp theo — Stream API & Lambda — xử lý dữ liệu theo functional style, core của Java modern.