Card 03/ 06
LRU Cache in Python, Java and TypeScript
A cache built from a hash map and a doubly linked list, then each language's shortcut.
An LRU cache is short to write once its two structures are clear, and each of Python, Java and TypeScript also has a shortcut that hides the list inside a built-in. This card covers the hand-written cache in all three languages, using placeholder nodes at both ends of the list, and the built-in version in each.
An LRU cache evicts the least recently used key when it is full. It keeps a hash map from each key to a node of a doubly linked list, a list in which each node points both to the next node and to the previous one, ordered from most to least recently used.
The list starts with two sentinel nodes, head and tail, which hold no data and are never removed. With a sentinel at each end, every real node has a node before it and a node after it, so unlinking and relinking need no special case for an empty list or for the first or last node. _unlink joins a node's two neighbours to each other, _push_front places a node after head, and the least recently used node is always tail.prev.
Each listing runs the same seven operations on a cache of capacity 3, first on the hand-written cache and then on the built-in one, and prints the two gets and the final contents.
The same cache, hand-written and built in, in each language
from collections import OrderedDict
class Node:
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.nodes = {}
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.nodes.get(key)
if node is None:
return None
self._unlink(node)
self._push_front(node)
return node.value
def put(self, key, value):
node = self.nodes.get(key)
if node is not None:
node.value = value
self._unlink(node)
else:
if len(self.nodes) == self.capacity:
oldest = self.tail.prev
self._unlink(oldest)
del self.nodes[oldest.key]
node = Node(key, value)
self.nodes[key] = node
self._push_front(node)
def entries(self):
node, entries = self.head.next, []
while node is not self.tail:
entries.append(f"{node.key}={node.value}")
node = node.next
return entries
class OrderedDictCache:
def __init__(self, capacity):
self.capacity = capacity
self.store = OrderedDict()
def get(self, key):
if key not in self.store:
return None
self.store.move_to_end(key)
return self.store[key]
def put(self, key, value):
self.store[key] = value
self.store.move_to_end(key)
if len(self.store) > self.capacity:
self.store.popitem(last=False)
def entries(self):
return [f"{key}={value}" for key, value in reversed(self.store.items())]
def run(name, cache):
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
first = cache.get("a")
cache.put("d", 4)
second = cache.get("b")
cache.put("c", 5)
print(f"{name}: get(a) gave {first}, get(b) gave {second}; most recent first: {' '.join(cache.entries())}")
run("hand-written", LRUCache(3))
run("OrderedDict", OrderedDictCache(3))hand-written: get(a) gave 1, get(b) gave None; most recent first: c=5 d=4 a=1
OrderedDict: get(a) gave 1, get(b) gave None; most recent first: c=5 d=4 a=1import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class LruCacheCode {
interface Cache {
Integer get(String key);
void put(String key, int value);
List<String> entries();
}
static final class Node {
final String key;
int value;
Node prev, next;
Node(String key, int value) {
this.key = key;
this.value = value;
}
}
static final class LruCache implements Cache {
private final int capacity;
private final Map<String, Node> nodes = new HashMap<>();
private final Node head = new Node(null, 0);
private final Node tail = new Node(null, 0);
LruCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
private void unlink(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void pushFront(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
public Integer get(String key) {
Node node = nodes.get(key);
if (node == null) return null;
unlink(node);
pushFront(node);
return node.value;
}
public void put(String key, int value) {
Node node = nodes.get(key);
if (node != null) {
node.value = value;
unlink(node);
} else {
if (nodes.size() == capacity) {
Node oldest = tail.prev;
unlink(oldest);
nodes.remove(oldest.key);
}
node = new Node(key, value);
nodes.put(key, node);
}
pushFront(node);
}
public List<String> entries() {
List<String> entries = new ArrayList<>();
for (Node node = head.next; node != tail; node = node.next) entries.add(node.key + "=" + node.value);
return entries;
}
}
static final class LinkedHashMapCache implements Cache {
private final Map<String, Integer> store;
LinkedHashMapCache(int capacity) {
store = new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
return size() > capacity;
}
};
}
public Integer get(String key) {
return store.get(key);
}
public void put(String key, int value) {
store.put(key, value);
}
public List<String> entries() {
List<String> entries = new ArrayList<>();
store.forEach((key, value) -> entries.addFirst(key + "=" + value));
return entries;
}
}
static void run(String name, Cache cache) {
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
Integer first = cache.get("a");
cache.put("d", 4);
Integer second = cache.get("b");
cache.put("c", 5);
System.out.println(name + ": get(a) gave " + first + ", get(b) gave " + second
+ "; most recent first: " + String.join(" ", cache.entries()));
}
public static void main(String[] args) {
run("hand-written", new LruCache(3));
run("LinkedHashMap", new LinkedHashMapCache(3));
}
}hand-written: get(a) gave 1, get(b) gave null; most recent first: c=5 d=4 a=1
LinkedHashMap: get(a) gave 1, get(b) gave null; most recent first: c=5 d=4 a=1interface Cache {
get(key: string): number | undefined;
put(key: string, value: number): void;
entries(): string[];
}
class CacheNode {
readonly key: string;
value: number;
prev!: CacheNode;
next!: CacheNode;
constructor(key: string, value: number) {
this.key = key;
this.value = value;
}
}
class LruCache implements Cache {
private readonly capacity: number;
private readonly nodes = new Map<string, CacheNode>();
private readonly head = new CacheNode("", 0);
private readonly tail = new CacheNode("", 0);
constructor(capacity: number) {
this.capacity = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
private unlink(node: CacheNode): void {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private pushFront(node: CacheNode): void {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
get(key: string): number | undefined {
const node = this.nodes.get(key);
if (node === undefined) return undefined;
this.unlink(node);
this.pushFront(node);
return node.value;
}
put(key: string, value: number): void {
let node = this.nodes.get(key);
if (node !== undefined) {
node.value = value;
this.unlink(node);
} else {
if (this.nodes.size === this.capacity) {
const oldest = this.tail.prev;
this.unlink(oldest);
this.nodes.delete(oldest.key);
}
node = new CacheNode(key, value);
this.nodes.set(key, node);
}
this.pushFront(node);
}
entries(): string[] {
const entries: string[] = [];
for (let node = this.head.next; node !== this.tail; node = node.next) entries.push(`${node.key}=${node.value}`);
return entries;
}
}
class MapCache implements Cache {
private readonly capacity: number;
private readonly store = new Map<string, number>();
constructor(capacity: number) {
this.capacity = capacity;
}
get(key: string): number | undefined {
const value = this.store.get(key);
if (value === undefined) return undefined;
this.store.delete(key);
this.store.set(key, value);
return value;
}
put(key: string, value: number): void {
this.store.delete(key);
this.store.set(key, value);
if (this.store.size > this.capacity) {
const oldest = this.store.keys().next().value!;
this.store.delete(oldest);
}
}
entries(): string[] {
return [...this.store].reverse().map(([key, value]) => `${key}=${value}`);
}
}
function run(name: string, cache: Cache): void {
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
const first = cache.get("a");
cache.put("d", 4);
const second = cache.get("b");
cache.put("c", 5);
console.log(`${name}: get(a) gave ${first}, get(b) gave ${second}; most recent first: ${cache.entries().join(" ")}`);
}
run("hand-written", new LruCache(3));
run("Map", new MapCache(3));hand-written: get(a) gave 1, get(b) gave undefined; most recent first: c=5 d=4 a=1
Map: get(a) gave 1, get(b) gave undefined; most recent first: c=5 d=4 a=1Every version printed the same result: get(a) found 1, get(b) missed, and the contents, most recent first, were c=5, d=4, a=1. A miss prints as None, null or undefined, each language's value for nothing.
The first highlighted lines are the eviction in the hand-written cache. They remove the node before tail from the list and then delete its key from the map, which is why each node stores its key: without it, the map entry could not be found without a search.
The shortcuts differ in how much they do. Python's OrderedDict is a dictionary that remembers order and can reorder: move_to_end marks a key as most recent and popitem(last=False) removes the oldest, both O(1). Java's LinkedHashMap does the whole job when its third constructor argument is true, which orders entries by access instead of insertion, so every get and put moves an entry to the end; overriding removeEldestEntry to return true above capacity makes each put evict on its own. TypeScript's Map keeps insertion order only, so the cache marks a key as recent by deleting it and setting it again, and the first key the map yields is the oldest. All three built-ins keep a linked list inside, so the shortcut is the same combination, already written.
← → move through sections and cards