How do you implement an LRU cache using LinkedHashMap?

LinkedHashMap can keep entries in access order instead of insertion order. Every get() moves the entry to the end, so the first entry is always the least recently used. Overriding removeEldestEntry() to return true when the size exceeds the capacity turns it into an LRU cache in a few lines.

Key Points: • Use the constructor new LinkedHashMap<>(capacity, 0.75f, true). The third argument, accessOrder = true, is the key. • removeEldestEntry() is called after every put(). Returning true removes the oldest (least recently used) entry. • get() and put() are O(1), because it is a hash table plus a doubly linked list. • It isn't thread-safe. Wrap it with Collections.synchronizedMap(), or use a library such as Caffeine in production. • Interviewers may also ask you to build it from scratch with a HashMap and your own doubly linked list.

Code Example:

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

public class LruCacheDemo {

    static class LruCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;

        LruCache(int capacity) {
            super(capacity, 0.75f, true);      // true = access order
            this.capacity = capacity;
        }

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

    public static void main(String[] args) {
        LruCache<String, String> cache = new LruCache<>(3);
        cache.put("A", "Apple");
        cache.put("B", "Banana");
        cache.put("C", "Cherry");
        System.out.println(cache.keySet());

        cache.get("A");                         // A becomes most recently used
        System.out.println("After get(A): " + cache.keySet());

        cache.put("D", "Date");                 // evicts B, the least recently used
        System.out.println("After put(D): " + cache.keySet());
    }
}

Output:

[A, B, C] After get(A): [B, C, A] After put(D): [C, A, D]

Good to Know: If the interviewer asks for an implementation without LinkedHashMap, combine a HashMap<K, Node> for O(1) lookup with a doubly linked list where you move accessed nodes to the head and remove from the tail. That is exactly what LinkedHashMap does internally.

Interview Tip: A concise interview answer is:

"I extend LinkedHashMap with accessOrder set to true, so every get moves the entry to the end, and override removeEldestEntry to return true when size exceeds the capacity, which evicts the least recently used entry. Both get and put stay O(1). For a thread-safe production cache I'd use Caffeine instead."

Previous question: How do you use TreeMap and NavigableMap methods like floorKey, ceilingKey, headMap and subMap?

Next question: What are EnumMap and EnumSet, and why are they faster than HashMap and HashSet?

How do you implement an LRU cache using LinkedHashMap?

More Java Collections interview questions