Java LRUCache Guide: SequencedMap vs LinkedHashMap (JDK 21 & Earlier)


1️⃣ Introduction

An LRUCache (Least Recently Used Cache) is a data structure that evicts the least recently accessed item when it reaches its capacity. This guide covers how to implement an LRUCache in Java using the new SequencedMap (JDK 21+) and the classic LinkedHashMap (for earlier JDKs).

  • Why use LRUCache?
  • What are the best ways to implement it in modern and legacy Java?
A B C D E LRU MRU

Diagram: LRUCache with 5 entries. LRU = Least Recently Used, MRU = Most Recently Used.


2️⃣ Implementing LRUCache in JDK 21+ with SequencedMap

Java 21 introduced SequencedMap, making LRUCache implementation more intuitive and efficient.

// Java 21+ LRUCache using SequencedMap
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.SequencedMap;

public class LRUCache<K, V> {
    private final int capacity;
    private final SequencedMap<K, V> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>();
    }

    public V get(K key) {
        if (!cache.containsKey(key)) return null;
        V value = cache.remove(key);
        cache.put(key, value); // Move to end (most recently used)
        return value;
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            cache.remove(key);
        } else if (cache.size() == capacity) {
            K lruKey = cache.firstKey(); // Remove least recently used
            cache.remove(lruKey);
        }
        cache.put(key, value);
    }
}

Note: SequencedMap provides firstKey() and lastKey() for easy LRU management.


3️⃣ Implementing LRUCache in Earlier JDKs with LinkedHashMap

Before Java 21, LinkedHashMap was the go-to for LRUCache. Override removeEldestEntry for automatic eviction.

// LRUCache using LinkedHashMap (JDK 8+)
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }

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

Pro Tip: This approach is thread-unsafe. Use Collections.synchronizedMap or external synchronization for thread safety.


4️⃣ Q&A / Frequently Asked Questions

Use SequencedMap (e.g., LinkedHashMap in Java 21+) to manage insertion/access order and evict the least recently used item using firstKey().

Extend LinkedHashMap and override removeEldestEntry to evict the eldest entry when the cache exceeds its capacity.

SequencedMap (Java 21+) is a new interface that standardizes access to the first and last entries, making LRU logic more explicit. LinkedHashMap is the classic way, but requires overriding methods for LRU behavior.

No, both implementations are not thread-safe by default. Use Collections.synchronizedMap or ConcurrentHashMap with additional logic for thread safety.

5️⃣ Best Practices & Pro Tips 🚀

  • Choose SequencedMap for new projects on Java 21+ for clarity and maintainability.
  • For legacy systems, LinkedHashMap is reliable and widely supported.
  • Always consider thread safety for multi-threaded environments.
  • Monitor cache hit/miss rates for optimal sizing.
  • Document cache eviction policy for maintainers.

Read Next 📖


Conclusion

Implementing an LRUCache in Java is straightforward with both modern and legacy approaches. Use SequencedMap for new projects and LinkedHashMap for older JDKs. Always consider thread safety and cache sizing for production systems.

Java Essentials