Limited fast memory needs an eviction policy
A cache keeps frequently needed data close to the application so repeated requests avoid an expensive database, disk or network operation. Capacity is limited, so inserting a new key into a full cache requires removing an existing entry. Least Recently Used (LRU) removes the entry that has gone unused for the longest time.
“Recently used” includes both reading a key and updating it. Therefore every successful get and put changes recency order. A miss does not. The system must support lookup, insertion, update and eviction efficiently while keeping the recency policy correct after every mutation.
Get
Return a stored value and move its entry to most-recent position.
Put
Insert or update, then mark the key most recently used.
Evict
When full, remove exactly the least-recent entry.
Make recency semantics unambiguous
| Operation | Existing key | Missing key | Recency effect |
|---|---|---|---|
| GET(key) | Return value; hit++ | Report miss; miss++ | Hit moves key to MRU; miss changes nothing |
| PUT(key,value) | Replace value | Create entry; evict first if full | Stored key becomes MRU |
| REMOVE(key) | Delete from both structures | Report absent | Remaining order is preserved |
| DISPLAY | Show entries from MRU to LRU | No change | |
Defined terms
MRU
Most Recently Used: the key touched most recently. It lives at the list head.
LRU
Least Recently Used: the oldest untouched key. It lives at the list tail and is the eviction candidate.
One structure is not enough for both goals
A hash table finds a key in O(1) average time but does not naturally identify the oldest key. A linked list orders entries by recency, but finding an arbitrary key would take O(n). The LRU cache combines them: the hash table points directly to the same nodes that also form a doubly linked list.
Hash bucket 4 ───────┐
Hash bucket 11 ──┐ │ recency links
▼ ▼
MRU/head → [30:300] ⇄ [10:100] ⇄ [20:200] ← LRU/tailNode fields
| Field | Purpose | Used by |
|---|---|---|
| key, value | Cached mapping | Both views |
| previous, next | Bidirectional recency order | Doubly linked list |
| hashNext | Collision chain inside one bucket | Hash table |
The cache owns each node exactly once even though two structures reference it. The hash table and list are two indexes over the same allocation; neither creates a duplicate node.
Every operation must preserve both views
sizeequals the number of unique nodes reachable from the recency list.- Every list node appears in exactly one hash bucket chain.
- Every hash-table node appears exactly once in the recency list.
mostRecent->previous == NULLandleastRecent->next == NULLwhen non-empty.- For adjacent nodes
A.next == B, the reverse link satisfiesB.previous == A. - An empty cache has size zero and both endpoints NULL.
- Size never exceeds capacity.
Ownership lifecycle
Small pointer functions reduce mutation risk
Mark a node most recent
- If it is already the head, do nothing.
- Detach it by reconnecting its previous and next neighbours.
- If it was the tail, move the tail pointer to its previous node.
- Attach it before the old head.
- Set it as the new head.
GET
On a miss, increment miss count and leave the linked list untouched.
PUT
- Search for the key.
- If found, update its value and move it to MRU.
- If absent and full, identify the tail in O(1), remove it from both indexes and free it.
- Allocate one new node, insert it into its hash bucket and attach it as MRU.
Why a doubly linked list?
A hash lookup returns the exact node to move. With both previous and next, it can be detached in O(1). A singly linked list would still need the predecessor, forcing a scan or an additional mapping.
Compiler-ready C11 simulator
The program stores integer keys and values, uses separate chaining for hash collisions, displays MRU-to-LRU order and tracks hit/miss statistics. Its small capacity limit keeps classroom traces readable; the algorithm itself is not tied to that limit.
Loading source…Hash collision
hashNext chains keys that map to the same bucket.
Recency mutation
detach and attach handle head, middle, tail and singleton nodes.
Cleanup
clearCache traverses the list once and frees every allocation.
Trace a capacity-three cache
- Create an empty cache.
- Store the first key.
- Key 2 becomes MRU.
- Store the third key.
- Reading key 1 refreshes its recency.
- A missing key does not change order.
- A full-cache insertion begins eviction.
- The new key becomes MRU.
- Updating a key counts as use.
- Explicit removal preserves remaining order.
Press Next to begin.
Test every position and both indexes
Test 1 — Capacity one
Test 2 — GET refreshes recency
Test 3 — Update without growth
Test 4 — Collision safety
Test 5 — Remove head, middle and tail
Test 6 — Miss behaviour
Test 7 — Complete cleanup
O(1) is average—not unconditional
| Operation | Average time | Worst time | Extra space |
|---|---|---|---|
| GET | O(1) | O(n) | O(1) |
| PUT existing | O(1) | O(n) | O(1) |
| PUT new/evict | O(1) | O(n) | O(1) per node |
| REMOVE | O(1) | O(n) | O(1) |
| DISPLAY/CLEAR | O(n) | O(n) | O(1) |
The worst case occurs when many keys collide into one bucket chain. A production cache resizes its table or uses a robust map implementation to keep load factor controlled. Total storage is O(capacity + bucket count).
When LRU is imperfect
LRU assumes recent past predicts near future. A one-time sequential scan larger than the cache can evict genuinely useful entries—a behaviour called cache pollution. LFU considers frequency; TTL policies consider age; ARC and related strategies adapt to workload. Policy selection depends on access patterns, not fashion.
Check the hybrid design
Why does an efficient LRU cache combine two structures?
After GET succeeds, what must happen?
Build the next version
- Resize the hash table when load factor crosses a chosen threshold.
- Add string keys and dynamically owned string values.
- Add a TTL and distinguish capacity eviction from expiry.
- Persist hit/miss/eviction statistics and compare workloads.
- Design thread-safe GET and PUT operations; explain locking granularity.
Defend every structural decision
Why not use only a hash table?
A hash table locates keys quickly but does not maintain a constant-time oldest-entry order. Finding the least recent entry would require extra metadata and a scan.
Why not use only a doubly linked list?
It gives O(1) removal when a node is already known, but locating a key is O(n). The hash table provides the missing direct lookup.
Why is the tail the eviction victim?
The list is maintained from most recent at head to least recent at tail. Therefore the tail encodes exactly the LRU policy and can be removed without scanning.
What is the hardest correctness problem?
Keeping the hash table and recency list consistent. Every insertion and deletion must update both views; moving a node changes only list links, not its hash membership.
How would concurrency change the design?
GET is no longer read-only because it mutates recency. Concurrent operations need synchronization around both indexes, careful lock ordering, and a policy for reducing contention.
Powerful structures are often compositions
The LRU cache achieves its performance by assigning separate responsibilities: the hash table answers “where is this key?” and the doubly linked list answers “which key is oldest?” Correctness comes from preserving the relationship between those views after every operation.