Building a Custom LRU Cache in Java Using LinkedHashMap

Suppose you are building an image-rendering microservice for a social network.

To speed up profile page loads, your service caches decoded user avatar images in RAM. But server memory is finite. You can only store 5,000 decoded avatar images in memory before the server runs out of heap space.

When avatar #5,001 arrives, your cache must decide which image to evict.

If you evict randomly, you might delete the avatar of a celebrity whose profile receives 1,000 views per second, forcing expensive image re-decodes.

The optimal strategy is Least Recently Used (LRU) Eviction: delete the image that hasn’t been accessed for the longest time.

To build an LRU cache, you need a data structure that provides $O(1)$ key lookups AND maintains strict access ordering. Standard HashMap fails because hash buckets destroy ordering.

Java’s LinkedHashMap solves this by placing a global doubly linked list across all bucket entries.

---

Dual Architecture: Buckets + Global Doubly Linked List

Every entry in a LinkedHashMap maintains two sets of pointers simultaneously:

1. Node.next: Singly linked list pointer for collision handling inside a bucket array slot.
2. Entry.before and Entry.after: Doubly linked list pointers connecting all map entries in historical order across the entire map.

BUCKET TABLE (O(1) Hash Access)
[ 0 ] ---> Entry("A") ---> null
[ 1 ] ---> null
[ 2 ] ---> Entry("B") ---> Entry("C") ---> null

GLOBAL DOUBLY LINKED LIST (Iteration Order: A -> B -> C)
head                                                   tail
  |                                                     |
  v                                                     v
+------------+       +------------+       +------------+
| Entry("A") |<=====>| Entry("B") |<=====>| Entry("C") |
+------------+       +------------+       +------------+

Iterating over LinkedHashMap walks the global before/after pointers instead of scanning array buckets.

---

Access-Order Mode vs Insertion-Order Mode

By default, LinkedHashMap maintains insertion order. New entries attach to the tail of the global doubly linked list.

If you set accessOrder = true, accessing an entry via get() unlinks that entry and moves it to the tail of the list.

Initial Order:  [ "A" <-> "B" <-> "C" ]

User calls get("A"):
Updated Order:  [ "B" <-> "C" <-> "A" ]  ("A" becomes most recently used)

The oldest (least recently used) entry remains at head. The newest (most recently used) entry lives at tail.

---

Implementing MyLinkedHashMap<K, V>

import java.util.Map;

public class MyLinkedHashMap<K, V> {
    static class Entry<K, V> {
        final int hash;
        final K key;
        V value;
        Entry<K, V> next; // Bucket collision pointer
        Entry<K, V> before, after; // Global insertion/access order pointers

        Entry(int hash, K key, V value, Entry<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Entry<K, V>[] table;
    private Entry<K, V> head;
    private Entry<K, V> tail;
    private int size;
    private final boolean accessOrder;
    private static final int CAPACITY = 16;

    @SuppressWarnings("unchecked")
    public MyLinkedHashMap(boolean accessOrder) {
        this.table = (Entry<K, V>[]) new Entry[CAPACITY];
        this.accessOrder = accessOrder;
    }

    public V get(K key) {
        int hash = hash(key);
        int index = (table.length - 1) & hash;
        Entry<K, V> e = table[index];
        while (e != null) {
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                if (accessOrder) {
                    afterNodeAccess(e);
                }
                return e.value;
            }
            e = e.next;
        }
        return null;
    }

    public V put(K key, V value) {
        int hash = hash(key);
        int index = (table.length - 1) & hash;
        Entry<K, V> e = table[index];

        while (e != null) {
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                V oldValue = e.value;
                e.value = value;
                if (accessOrder) {
                    afterNodeAccess(e);
                }
                return oldValue;
            }
            e = e.next;
        }

        Entry<K, V> newEntry = new Entry<>(hash, key, value, table[index]);
        table[index] = newEntry;
        linkNodeLast(newEntry);
        size++;

        if (removeEldestEntry(head)) {
            remove(head.key);
        }

        return null;
    }

    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return false; // Override in LRU subclass to return true when capacity exceeded
    }

    private void linkNodeLast(Entry<K, V> p) {
        Entry<K, V> last = tail;
        tail = p;
        if (last == null) {
            head = p;
        } else {
            p.before = last;
            last.after = p;
        }
    }

    private void afterNodeAccess(Entry<K, V> e) {
        Entry<K, V> last;
        if (accessOrder && (last = tail) != e) {
            Entry<K, V> p = e, b = p.before, a = p.after;
            p.after = null;
            if (b == null) head = a;
            else b.after = a;
            if (a != null) a.before = b;
            else last = b;

            if (last == null) head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
        }
    }

    public void remove(K key) {
        // Unlinks from table[] AND updates head/tail pointers
        // Implementation left as standard unlinking exercise
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
}

---

Building an LRU Cache in 10 Lines

To build an LRU (Least Recently Used) cache, extend LinkedHashMap, set accessOrder = true, and override removeEldestEntry():

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); // true sets access-order mode!
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity; // Evicts eldest node when max capacity exceeded!
    }
}

---

Quick Summary

• LinkedHashMap augments hash bucket nodes with before and after pointers.
• Iteration traverses the global doubly linked list in exact insertion (or access) order.
• Setting accessOrder = true moves accessed items to the tail, turning LinkedHashMap into an LRU cache.

References & Further Reading

1. Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347–348.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.PriorityQueue. GitHub.
3. Cormen, T. H., et al. (2022). Introduction to Algorithms (4th Edition) — Chapter 6: Heapsort. MIT Press.

---