Einen LRU-Cache entwerfen
Eine klassische Design-Frage: kombiniere eine Hash-Map mit einer doppelt verketteten Liste für O(1)-get und -put mit LRU-Verdrängung.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
The LRU cache is the most-asked design question in interviews, and it's the perfect capstone for this
module because the answer combines a hash map with a linked list - two structures you now know - to hit
a demanding requirement: both get and put in O(1), with automatic eviction of the least-recently-used
entry when the cache is full.
The requirement
An LRU (Least Recently Used) cache has a fixed capacity. get(key) returns the value and marks it as
just-used; put(key, value) inserts or updates and marks it just-used; when inserting would exceed
capacity, it evicts the entry that was used longest ago. Everything must be O(1).
No single structure does this. A hash map gives O(1) lookup but no notion of order. A list gives order but O(n) lookup. The insight is to combine them.
Hash map + doubly linked list
- A doubly linked list holds the entries in usage order - most-recently-used at the front, least-recently-used at the back. A doubly linked (not singly) list lets you unlink any node in O(1) because each node knows its predecessor.
- A hash map maps each key directly to its node in that list, so you find any entry in O(1) without walking.
Together: get looks up the node via the map (O(1)) and moves it to the front (O(1) unlink + insert).
put does the same, and when over capacity, removes the back node (the LRU) and its map entry (O(1)).
class LRUCache {
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0), tail = new Node(0, 0); // dummy sentinels
LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail; tail.prev = head; // empty list between sentinels
}
int get(int key) {
Node n = map.get(key);
if (n == null) return -1;
moveToFront(n); // mark as most-recently-used
return n.val;
}
void put(int key, int val) {
Node n = map.get(key);
if (n != null) { n.val = val; moveToFront(n); return; }
if (map.size() == capacity) { // evict least-recently-used
Node lru = tail.prev;
remove(lru);
map.remove(lru.key);
}
Node fresh = new Node(key, val);
map.put(key, fresh);
addToFront(fresh);
}
// remove(), addToFront(), moveToFront() are O(1) pointer re-wiring;
// dummy head/tail sentinels remove the empty-list edge cases.
}The dummy head and tail sentinels (from the linked-list module) mean insertion and removal never hit a
null-neighbor special case - every real node always has a prev and next.
Know the shortcut, but be ready to build it
Java's LinkedHashMap implements exactly this with an access-ordered mode, and overriding
removeEldestEntry gives an LRU cache in a few lines. Mention it - it shows ecosystem knowledge - but
interviewers usually want you to build it from a HashMap + doubly linked list to prove you
understand the mechanics. Know both.
Imagine keeping only the papers you use most, on a desk with room for a fixed number. Each time you consult a paper, you put it back on top. When a new paper arrives and the desk is full, you toss the one at the bottom - it's the one you haven't touched in the longest time. The pile is the doubly linked list (top = most recent, bottom = least), and to avoid rummaging for a specific paper you keep an index card telling you exactly where each one sits - that's the hash map. Together you always grab, restack, or discard in one motion.
The LRU design uses a doubly linked list. Explain why a singly linked list wouldn't give O(1) operations, and what role the hash map plays that the list alone cannot.
Which two data structures combine to make an LRU cache with O(1) get and put?
Key takeaways
- An LRU cache needs O(1) get and put with eviction of the least-recently-used entry - no single structure achieves this.
- Combine a hash map (key → node, O(1) lookup) with a doubly linked list (usage order, O(1) reorder/evict).
- A doubly linked list is required (not singly) so any node can be unlinked in O(1) via its prev pointer.
- Dummy head/tail sentinels remove empty-list and boundary edge cases.
- LinkedHashMap in access-order mode gives an LRU in a few lines - know it, but be ready to build the mechanics by hand.