A few years ago, I was reviewing a PR from a developer who had implemented a simple HashMap to cache expensive database queries for a user dashboard. It looked clean and it worked perfectly in staging. But the moment it hit production, the server started crashing every few hours with an OutOfMemoryError. The problem was simple: the cache had no expiration or size limit. It just grew indefinitely as more users logged in, eating up the heap until the JVM finally gave up. We needed a way to keep the "hot" data but toss out the stuff no one had touched in an hour.

That's where a Least Recently Used (LRU) cache comes in. The core philosophy is that data accessed recently is more likely to be accessed again soon. When the cache hits its maximum capacity, instead of crashing the system, we evict the entry that has sat untouched for the longest period of time. In Java, you could build this from scratch using a combination of a HashMap and a doubly-linked list, but that's a lot of boilerplate. Instead, we have a hidden gem in the standard library: LinkedHashMap.

Leveraging Access-Order in LinkedHashMap

By default, a LinkedHashMap maintains entries in the order they were inserted. That's useful, but not for an LRU cache. To make it work for us, we have to use a specific constructor that enables "access-order." When this is turned on, every time you call get() or put() on an entry, Java internally moves that entry to the end of the list. The entry at the very front of the list becomes, by definition, the least recently used item.

// The 'true' argument here is the magic switch for access-order
Map<K, V> cache = new LinkedHashMap<>(capacity, 0.75f, true);

I've seen people try to manually re-insert items to move them to the end, but that's inefficient and error-prone. Let the JDK handle the pointer manipulation for you.

Automating Eviction with removeEldestEntry

Now we have a list that keeps the oldest items at the front, but LinkedHashMap still doesn't know when to stop growing. To fix this, we override a single method: removeEldestEntry. This method is called by the internal put and putAll logic. If it returns true, the map automatically deletes the oldest entry before adding the new one.

It's a remarkably elegant pattern. You aren't manually scanning the map or running a background cleanup thread; the eviction happens as a side effect of adding new data. Here is the basic structure I usually use when I need a quick, thread-unsafe cache:

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

    public SimpleLRUCache(int maxCapacity) {
        // Initial capacity, load factor, and accessOrder = true
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }

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

One quick warning: LinkedHashMap is not thread-safe. If you're using this in a multi-threaded environment—like a Spring boot controller—you'll need to wrap it in Collections.synchronizedMap() or use a different concurrency strategy. For this exercise, though, we'll focus on the core LRU logic.

📋 Practical Task

Exercise: Implementing a Fixed-Size User Profile Cache with LRU Eviction

You are tasked with building a cache for a User Profile service. The system fetches profiles from a slow API, so you need to cache the most recently accessed UserProfile objects. However, to prevent memory leaks, the cache must never exceed 3 profiles.

Requirements:

• Create a UserProfile POJO with a userId (int) and a username (String).
• Implement a class UserProfileCache that extends LinkedHashMap.
• Configure the cache to use access-order.
• Override removeEldestEntry so that the cache maintains a maximum size of 3.
• In your main method, perform the following sequence to verify the LRU behavior:
  1. Add User 1, User 2, and User 3.
  2. Access User 1 (this should make it "recently used").
  3. Add User 4 (this should trigger eviction of User 2, as it's now the least recently used).
  4. Print the contents of the cache to verify that User 1, User 3, and User 4 remain, while User 2 is gone.