How do you build an LRU cache using LinkedHashMap?

“How do you build an LRU cache using LinkedHashMap?”

accessOrder=true moves a touched entry to the tail, so the head is always the least-recently-used. removeEldestEntry returns true to evict it when over capacity.

Map<K,V> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<K,V> e) {
        return size() > MAX;
    }
};

Time:

O(1) get/put with LRU eviction

LinkedHashMap LRU is a great interview demonstration and fine for small single-threaded caches, but real services use Caffeine for bounded, concurrent, observable caching.

Keywords they're listening for:

• ✓ accessOrder=true
• ✓ removeEldestEntry
• ✓ O(1) LRU
• ✓ not thread-safe
• ✓ Caffeine for prod

• ✗Forgetting accessOrder=true (gives insertion-order, not LRU)
• ✗Using it concurrently without synchronization
• ✗Reinventing caching instead of using Caffeine

• ✓Use Caffeine/Guava for production caches
• ✓Bound every cache (size + TTL)
• ✓Expose hit-rate metrics

1. 1How would you make it thread-safe?
2. 2How does Caffeine's W-TinyLFU differ from pure LRU?
3. 3How do you add TTL/expiry?

• Caffeine
• Guava Cache
• ConcurrentHashMap