Course contentsShow
← Java
Lesson 1147 of 2,87026. Map ImplementationsFree lesson

Implementing LRU Cache with LinkedHashMap

Build a least-recently-used cache by overriding removeEldestEntry in access-order LinkedHashMap.

Implementing LRU Cache with LinkedHashMap

What you'll learn: How to build a least-recently-used (LRU) cache by overriding removeEldestEntry in an access-order LinkedHashMap.

The Core Idea

An LRU cache automatically evicts the oldest (least-recently-used) entries when it reaches capacity. Since LinkedHashMap in access-order mode already tracks access patterns, you just need to tell it when to remove old entries. You do this by overriding the removeEldestEntry method, which Java calls after every put operation.

How removeEldestEntry Works

This protected method receives the eldest (least-recently-accessed) entry as a parameter. If you return true, that entry gets removed automatically. Typically, you return true when the cache exceeds your desired maximum size.

Implementation

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(16, 0.75f, true);  // true = access-order mode
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;  // Remove when size exceeds limit
    }
}

// Usage:
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
cache.get("A");  // Access A (moves it to end)
cache.put("D", 4);  // B gets evicted (least-recently-used)
// Cache now contains: A, C, D

Think of it like a VIP line: every time someone is accessed, they move to the back. When the line is full and a new person arrives, the one at the front (who hasn't been accessed longest) leaves.

Key Takeaway: Override removeEldestEntry in an access-order LinkedHashMap to return true when size() > maxSize, creating an automatic LRU cache with minimal code.