Java — Từ Zero đến Senior/Generics & Collections/Mini-challenge: LRU Cache generic với LinkedHashMap
5/5
~30 phútGenerics & Collections

Mini-challenge: LRU Cache generic với LinkedHashMap

Bài thực hành khép lại Module 8 — xây LruCache<K, V> generic dựa trên LinkedHashMap(accessOrder=true), thread-safe version với ReentrantLock, benchmark so sánh.

Đây là mini-challenge khép lại Module 8. 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

ConceptBàiDùng ở đây
Generic classModule 8, bài 1LruCache<K, V>
Type erasure, boundModule 8, bài 2K/V không có bound — dùng được mọi kiểu
LinkedHashMap access orderModule 8, bài 4Core của LRU
EncapsulationModule 5, bài 4Field map private final
Validate inputModule 7, bài 4throw IllegalArgumentException
try/finallyModule 7, bài 1Lock + unlock an toàn

▶️ 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 ý

💡 💡 Gợi ý — đọc khi bị kẹt

LruCache với LinkedHashMap:

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(); }
}

Điểm mấu chốt:

  • LinkedHashMap(initialCapacity, loadFactor, accessOrder) — constructor với 3 param.
  • accessOrder = true: thay vì thứ tự insert, list liên kết trong map tracks access order (get/put đẩy key lên cuối, oldest ở đầu).
  • removeEldestEntry gọi sau mỗi put — trả true thì evict eldest.
  • containsKey vs get: get update access order, containsKey không — API rõ ràng.

ThreadSafeLruCache với ReentrantLock:

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(); }
    }
}

Pattern: mỗi method lock → try { delegate } finally { unlock }. Critical — unlock trong finally để không leak khi exception.

✅ Lời giải

ℹ️ ✅ Lời giải — xem sau khi đã thử

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));
    }
}

Giải thích từng phần:

  • Generic <K, V>: cache dùng được với bất kỳ kiểu key/value. Không cần bound — LinkedHashMap đã yêu cầu equals/hashCode runtime, không cần compile-time constraint.

  • LinkedHashMap(16, 0.75f, true): 3 param constructor.

    • initialCapacity = 16 — default.
    • loadFactor = 0.75f — default.
    • accessOrder = true — điểm quan trọng. Thứ tự iterate là thứ tự truy cập (get move lên cuối), không phải thứ tự insert. Oldest ở đầu, newest ở cuối.

  • removeEldestEntry: hook của LinkedHashMap — được gọi sau mỗi put. Trả true → eldest entry bị remove. Ta return size() > maxSize → auto-evict khi đầy.

  • Inner anonymous class: tạo subclass LinkedHashMap tại chỗ để override removeEldestEntry. LruCache.this.maxSize để tham chiếu field outer class từ inner.

  • contains vs get: phân biệt intent. get "truy cập value" → update access order. contains "check existence" → không update. API rõ ràng.

  • ThreadSafeLruCache dùng composition + delegation: không extends LruCache mà wrap nó, lock mọi method. Pattern composition an toàn hơn inheritance (bài Module 6).

  • lock.lock() / try { } finally { lock.unlock() }: pattern bắt buộc. Nếu exception trong body mà không unlock → deadlock thread khác.

🎓 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 synchronized hoặc ConcurrentHashMap — trade-off:

  • synchronized: đơn giản nhất, nhưng không có tryLock / timeout.
  • ReentrantLock: flexible (tryLock, fairness, condition).
  • 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.

✨ Đ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 — module 6 rule.
  • Á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 8! Từ đây bạn có công cụ mô hình dữ liệu đầy đủ (generic + collections). Module 9 sẽ bước sang Stream API và Lambda — xử lý dữ liệu theo functional style, core của Java modern.