Card 01/ 06
Combining Two Structures to Cover Each Other's Slow Operation
When no single structure makes every operation cheap, two kept in step often can.
Some programs need a set of operations that no single structure makes cheap, and the answer is to keep the same items in two structures at once, each covering the operation the other is slow at. This card covers that idea through its best-known case, the LRU cache, built from a hash map and a doubly linked list, and why the map must point at the list's nodes.
A cache is a small, fast store that keeps recent results so they need not be fetched or computed again. It has a fixed capacity, so when it is full and a new item arrives, one item must go. An LRU cache, for least recently used, evicts the item that has gone longest without being read or written. It must do three things in O(1): get a value by its key, put a key and value, and evict the least recently used key.
A hash map gets a value by key in O(1) on average but keeps no order of use, so finding the least recently used key means looking at every key. A doubly linked list, in which every node points to the next node and the previous one, keeps the order of use cheaply: move a node to the front whenever it is used, and the last node is always the one to evict. It cannot find a key without walking the list.
Together they cover each other, as the table shows.
| Operation | Hash map alone | Doubly linked list alone | Both together |
|---|---|---|---|
| Get the value for a key | O(1) on average | O(n), walking the list | O(1): the map finds the node |
| Mark a key as most recently used | Not possible: no order kept | O(1) once the node is found | O(1): unlink the node and put it at the front |
| Evict the least recently used key | O(n), looking at every key | O(1): remove the last node | O(1): remove the last node and its key from the map |
The cache works because of what the map stores. Each key maps to its node in the list, not to the value alone, so a get reaches the node in one step and can move it to the front without a search. Each node also stores its key, so that evicting the last node can delete the right entry from the map. The drawing shows a cache of capacity 3 after a, b and c are put and a is read.
hash map: key → node doubly linked list, most recent first
a → node a head ⇄ a=1 ⇄ c=3 ⇄ b=2 ⇄ tail
b → node b
c → node cA library works in a similar way: the catalogue finds any book at once, and the returns trolley holds books in the order they came back. The likeness breaks on timing. A librarian can let the catalogue fall behind the trolley for an afternoon, and the cache cannot let its map and list disagree for a single operation, because the next get trusts both.
The pattern is general: name the operation each structure is slow at, check that the other makes it cheap, and update both on every change.
← → move through sections and cards