How to Build a Java LRU Cache in 5 Lines

To build a simple Least Recently Used (LRU) cache in Java, extend the standard LinkedHashMap with accessOrder set to true and override the removeEldestEntry method. While this standard library approach is incredibly elegant and fits in five lines of code, I should warn you that it is not thread-safe by default.

Whenever I'm talking shop with other engineers, the classic "build an LRU cache" interview question always seems to come up. Most devs immediately start sketching out a custom doubly linked list and a hash map, sweating over manual pointer updates. But if you're writing Java, we've had a production-ready, elegant solution sitting right under our noses in the standard library since 2002.

It's called LinkedHashMap, and I'm going to show you how to turn it into a fully functional LRU cache with almost zero boilerplate.

How does LinkedHashMap work as an LRU cache?

LinkedHashMap maintains a doubly linked list running through all of its entries to track element ordering. By initializing it with the accessOrder constructor argument set to true, the map automatically moves any accessed element to the end of the list. This ensures that the least recently used item always remains at the very front of the list.

I like to think of a standard hash map as a messy drawer where you toss items. It is highly efficient for retrieving things, but it has no sense of order. LinkedHashMap threads a string through all those items to keep track of them.

When you set accessOrder to true, the map changes its behavior. Instead of keeping items in insertion order, it reshuffles them every time you call get() or put(). Reading an item unhooks it from its current position and moves it to the end. Because it uses a doubly linked list, this pointer swap runs in O(1) constant time, meaning it takes the same amount of time whether your cache has three items or three million.

How do you implement a 5-line LRU cache in Java?

To implement the cache, extend LinkedHashMap and override the protected removeEldestEntry method to return true when the map exceeds your capacity limit. This hook runs after every put operation, instructing the map to automatically evict the oldest entry.

Personally, I love this solution because of how clean it is. We can inherit all the heavy lifting from the standard library. Here is how I implement it in just five lines of actual logic:

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

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public LruCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }

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

Let’s trace how this works with a capacity of three. Imagine you insert keys A, B, and C. Your cache is now full. If you read key A, the pointer swaps move A to the end of the list, leaving B at the front as the oldest, least recently used entry. When you insert a new key, D, the overridden removeEldestEntry method checks if the size exceeds three, returns true, and discards B instantly.

Is the LinkedHashMap LRU cache thread-safe?

No, the default LinkedHashMap implementation is not thread-safe. If multiple threads access and modify the cache concurrently, you must wrap it in a synchronized wrapper or use a dedicated concurrent cache.

I should warn you, though: this elegant little class is not thread-safe out of the box. If you have multiple threads modifying the cache at the same time, you'll run into race conditions.

If I need to use this approach in a multi-threaded environment, I wrap it using Collections.synchronizedMap:

Map<String, String> cache = Collections.synchronizedMap(new LruCache<>(100));

However, synchronization introduces locks, which can slow down high-throughput applications. If your service handles heavy concurrent traffic, I recommend comparing your options before deciding on an implementation strategy:

Cache Strategy	Thread-Safety	Performance Under Load	Best Use Case
LinkedHashMap (Standard)	No	Extremely Fast (Single Thread)	Lightweight, single-threaded memory management
Synchronized LinkedHashMap	Yes (Lock-based)	Medium (Lock Contention)	Simple multi-threaded apps with low write volume
Caffeine / Guava Cache	Yes (Lock-free)	Industry-leading	High-throughput, concurrent production services

FAQ

Can you use LinkedHashMap as an LRU cache without extending it?

Yes, but you lose the automatic eviction. Without overriding removeEldestEntry, you would have to manually check the map's size and delete the oldest item using an iterator after every insertion, which defeats the purpose of this clean implementation.

What is the time complexity of LinkedHashMap LRU operations?

Both read and write operations run in O(1) constant time. The pointer updates in the underlying doubly linked list require only a few reference swaps, which do not scale with the size of the cache.

Why does the LinkedHashMap constructor require a float value?

The float value (typically 0.75f) is the load factor. It determines when the underlying hash table resizes itself to prevent collision chains, ensuring lookup times remain predictable and fast.

---

That is all there is to it. Next time someone challenges you to write an LRU cache, you can show them how to get it done in five lines of clean, standard Java. Have you ever used this trick in production, or do you always reach for Caffeine? Let me know!

Cheers,

Doogal