LRU Cache Implementation

The problem, simply

Build a cache: a small box that remembers up to capacity key and value pairs. It has two calls.

• get(key) gives back the value for key, or -1 if the key is not in the box. Getting a key counts as using it.
• put(key, value) stores the pair, or changes the value if the key is already there. That also counts as using it. If the box is now too full, throw out the key that was used least recently.

Both calls must be fast: O(1) on average, no matter how big the box is. That is the whole difficulty.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a plain list of entries. Give every entry a time stamp that says when it was last used. A counter goes up by one on every call.

1. get: scan the list for the key. If found, update its stamp and return the value.
2. put: scan for the key. If found, update the value and the stamp.
3. Otherwise, if the list is full, scan for the smallest stamp and remove that entry. Then add the new entry.

import java.util.*;

class LRUCache {
    private final List<int[]> entries = new ArrayList<>();   // {key, value, lastUsed}
    private final int capacity;
    private int clock = 0;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

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

    public int get(int key) {
        int i = find(key);
        if (i < 0) return -1;
        entries.get(i)[2] = ++clock;          // used just now
        return entries.get(i)[1];
    }

    public void put(int key, int value) {
        int i = find(key);
        if (i >= 0) {
            entries.get(i)[1] = value;
            entries.get(i)[2] = ++clock;
            return;
        }
        if (entries.size() == capacity) {
            int oldest = 0;
            for (int j = 1; j < entries.size(); j++) {
                if (entries.get(j)[2] < entries.get(oldest)[2]) oldest = j;
            }
            entries.remove(oldest);           // throw out the least recently used
        }
        entries.add(new int[]{key, value, ++clock});
    }
}

How long it takes: every call scans the list, O(n) where n is the capacity. Extra room: O(n) for the entries. Correct, but it fails the O(1) rule.

Way 2: the clever way

Use two structures that cover each other's weak spots.

• A doubly linked list keeps the order. Newest is right after a pretend head node, oldest is right before a pretend tail node. Because every node knows both neighbors, we can unhook any node in O(1).
• A hash map from key to node finds any node in O(1), so we never scan the list.

The moves:

1. get(key): look up the node in the map. If missing, return -1. Otherwise unhook it, hook it right after head, and return its value.
2. put(key, value): if the key is in the map, update the value and move the node to the front.
3. Otherwise, if the map is full, the node before tail is the oldest. Unhook it and remove its key from the map. That is why each node stores its own key.
4. Make a new node, hook it after head, and put it in the map.

import java.util.*;

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);   // pretend node before the newest
    private final Node tail = new Node(0, 0);   // pretend node after the oldest

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void unhook(Node node) {
        node.prev.next = node.next;             // the neighbors join hands
        node.next.prev = node.prev;
    }

    private void addFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        unhook(node);
        addFront(node);                         // just used, so it is the newest
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            unhook(node);
            addFront(node);
            return;
        }
        if (map.size() == capacity) {
            Node oldest = tail.prev;            // the least recently used
            unhook(oldest);
            map.remove(oldest.key);             // the node remembers its own key
        }
        Node fresh = new Node(key, value);
        addFront(fresh);
        map.put(key, fresh);
    }
}

How long it takes: each call does one map lookup and a few arrow changes, O(1) on average. Extra room: one node and one map entry per key, O(capacity).

Another way: LinkedHashMap

Java ships this exact structure. A LinkedHashMap built with accessOrder = true moves an entry to the end every time it is read or written. Override removeEldestEntry to throw out the oldest when the map is too big.

import java.util.*;

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);           // true means order by last use
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;               // too full: drop the oldest
    }
}

Mention it in an interview, but expect to be asked to build Way 2 by hand.

Watch out for

• Treating put on an existing key as a new key. That evicts someone for no reason and leaves two nodes for one key.
• Forgetting that get also counts as a use. A read must move the node to the front.
• Skipping the pretend head and tail nodes. Then every unhook needs checks for "is this the first node" and "is this the last node", and bugs hide there.
• Capacity 0. Decide with the interviewer; a simple rule is that put does nothing.

What interviewers ask next

• Make it safe for many threads. The simple answer is one lock around get and put. A faster answer splits the cache into several parts by key, each with its own lock.
• LFU cache: throw out the least frequently used key instead. Keep a map from key to node and a map from use count to a doubly linked list, plus the current smallest count. Still O(1).
• Add a time limit to each entry. Store an expiry time in each node and treat an expired node as missing on get.
• Why a doubly linked list and not a singly linked list? To unhook a node in O(1) you need its previous node, and only a doubly linked list keeps that link.
• Why not a heap of time stamps? Every use would change a stamp and cost O(log n). The list gets the same order for O(1).

Remember this

Grown-up words: the toy shelf is a cache, "used least recently" is LRU, the toys holding hands on both sides are a doubly linked list, the notebook is a hash map, the pretend end nodes are sentinel nodes, and throwing out a toy is eviction.