Implement an LRU cache using LinkedHashMap.

Subclass LinkedHashMap, enable access-order mode, and override removeEldestEntry to return true once the size exceeds your capacity. That's it — under 20 lines for a fully functional LRU cache.

The implementation

public final class LruCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    public LruCache(int capacity) {
        // accessOrder = true -> reads move entries to the tail
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

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

How it works

• The third constructor argument (accessOrder = true) makes every get/put reorder the chain, pushing the touched entry to the tail.
• After every successful put, LinkedHashMap calls afterNodeInsertion, which in turn calls your removeEldestEntry(head). If you return true, the head — the least-recently-used entry — is removed.

Both operations are O(1) (hash lookup plus a constant number of pointer updates).

Using it

var cache = new LruCache<String, String>(3);
cache.put("a", "alpha");
cache.put("b", "beta");
cache.put("c", "gamma");

cache.get("a");           // "a" is now most-recently-used
cache.put("d", "delta");  // capacity exceeded -> evicts "b" (eldest)

System.out.println(cache.keySet()); // [c, a, d]

Production caveats

This is great for examples and small in-process caches, but for production you should usually reach for Caffeine:

• LinkedHashMap is not thread-safe. Wrapping with Collections.synchronizedMap serialises every read, killing concurrency.
• No time-based expiry (TTL).
• No weight-based eviction (count only).
• No async loading, no statistics, no listeners.
• get mutates the chain, so you can't safely use plain unsynchronised reads even in mostly-read workloads.

// Production-grade alternative
Cache<String, String> cache = Caffeine.newBuilder()
    .maximumSize(10_000)
    .expireAfterAccess(Duration.ofMinutes(5))
    .recordStats()
    .build();