# 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:

```java
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`:

```java
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