LRU Cache

Design a cache with a fixed capacity that evicts the least recently used entry when it is full:

get(key) returns the value for key (or an empty OptionalInt) and marks key as most recently used.
put(key, value) inserts or updates key and marks it as most recently used. If this adds a new key to a full cache, the least recently used key is evicted first.

Both operations should run in O(1).

Example

Text

capacity 2
put(1, 1), put(2, 2)
get(1)    -> 1         order (most recent first): 1, 2
put(3, 3)              evicts 2
get(2)    -> empty
put(4, 4)              evicts 1
get(1)    -> empty
get(3)    -> 3
get(4)    -> 4

OptionalInt is a container that holds either one int or nothing. get returns it so that a missing key is not confused with a stored value.

Brute force: an ArrayList in recency order

Keep int[]{key, value} pairs in an ArrayList, most recent at index 0. Every operation searches for the key, moves it to the front, and a full cache drops the last element. ArrayList.add(0, x) and remove(i) shift elements, so each costs O(capacity).

Java

import java.util.ArrayList;
import java.util.List;
import java.util.OptionalInt;

public class Main {
    static class LruCache {
        private final int capacity;
        private final List<int[]> entries = new ArrayList<>(); // most recently used first

        LruCache(int capacity) {
            this.capacity = capacity;
        }

        private int indexOf(int key) {
            for (int i = 0; i < entries.size(); i++) {
                if (entries.get(i)[0] == key) return i;
            }
            return -1;
        }

        OptionalInt get(int key) {
            int i = indexOf(key);
            if (i < 0) return OptionalInt.empty();
            int[] entry = entries.remove(i);
            entries.add(0, entry);
            return OptionalInt.of(entry[1]);
        }

        void put(int key, int value) {
            if (capacity == 0) return;
            int i = indexOf(key);
            if (i >= 0) {
                entries.remove(i);
            } else if (entries.size() == capacity) {
                entries.remove(entries.size() - 1);
            }
            entries.add(0, new int[]{key, value});
        }
    }

    public static void main(String[] args) {
        LruCache cache = new LruCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.print(cache.get(1) + " ");
        cache.put(3, 3);
        System.out.print(cache.get(2) + " ");
        cache.put(4, 4);
        System.out.println(cache.get(1) + " " + cache.get(3) + " " + cache.get(4));
    }
}

Output

OptionalInt[1] OptionalInt.empty OptionalInt.empty OptionalInt[3] OptionalInt[4]

Time: O(capacity) per operation, for the search and the shifting. Space: O(capacity).

Optimal: HashMap and a doubly linked list

Two structures together give O(1) for everything:

A doubly linked list in recency order. A node can be unlinked from anywhere and pushed to the front in O(1), and the back is the eviction candidate.
A HashMap from key to the key's node, so the node can be found in O(1).

graph LR
    map["HashMap: key -> node"] -.-> n3
    map -.-> n1
    head(["head"]) --> n3["3: 3"] <--> n1["1: 1"]
    n1 --> tail(["tail (evict next)"])

Java nodes are objects reached through references. A reference is either an object or null, so prev and next are plain mutable fields and null marks the end of the list. No wrapper type is needed. An evicted node is reused for the new entry, so the cache never creates more than capacity nodes.

Java

import java.util.HashMap;
import java.util.Map;
import java.util.OptionalInt;

public class Main {
    static class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class LruCache {
        private final int capacity;
        private final Map<Integer, Node> map = new HashMap<>(); // key -> node
        private Node head; // most recently used
        private Node tail; // least recently used

        LruCache(int capacity) {
            this.capacity = capacity;
        }

        private void unlink(Node n) {
            if (n.prev == null) head = n.next; else n.prev.next = n.next;
            if (n.next == null) tail = n.prev; else n.next.prev = n.prev;
        }

        private void pushFront(Node n) {
            n.prev = null;
            n.next = head;
            if (head == null) tail = n; else head.prev = n;
            head = n;
        }

        OptionalInt get(int key) {
            Node n = map.get(key);
            if (n == null) return OptionalInt.empty();
            unlink(n);
            pushFront(n);
            return OptionalInt.of(n.value);
        }

        void put(int key, int value) {
            Node n = map.get(key);
            if (n != null) {
                n.value = value;
                unlink(n);
                pushFront(n);
                return;
            }
            if (capacity == 0) return;
            if (map.size() == capacity) {
                n = tail;
                unlink(n);
                map.remove(n.key);
                n.key = key;     // reuse the evicted node
                n.value = value;
            } else {
                n = new Node(key, value);
            }
            map.put(key, n);
            pushFront(n);
        }
    }

    public static void main(String[] args) {
        LruCache cache = new LruCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.print(cache.get(1) + " ");
        cache.put(3, 3);
        System.out.print(cache.get(2) + " ");
        cache.put(4, 4);
        System.out.println(cache.get(1) + " " + cache.get(3) + " " + cache.get(4));

        cache = new LruCache(1);
        cache.put(1, 10);
        cache.put(1, 11); // update, no eviction
        cache.put(2, 20);
        System.out.println(cache.get(1) + " " + cache.get(2));
    }
}

Output

OptionalInt[1] OptionalInt.empty OptionalInt.empty OptionalInt[3] OptionalInt[4]
OptionalInt.empty OptionalInt[20]

Time: O(1) average per operation (HashMap lookups are O(1) on average). Space: O(capacity).

The node stores its own key so that eviction, which starts from the list's tail, can remove the matching HashMap entry.

LinkedHashMap built with accessOrder set to true and an overridden removeEldestEntry method provides the same behavior in the standard library. This lesson builds the list by hand to show the mechanism.

Edge cases

Updating an existing key: changes the value and recency; it never evicts.
Capacity 0: put stores nothing.
Capacity 1: every new key evicts the previous one; head and tail are the same node.