A cache that forgets the stale
A cache holds a limited number of entries to speed up repeated lookups. When it fills, it must evict something. The least recently used policy, or LRU, evicts the entry untouched for the longest time, betting that recently used items will be used again soon. The challenge is doing both the lookup and the recency update in constant time.
Two structures working together
A single structure cannot do it alone, so LRU combines two.
- A hash map maps each key to a node, giving constant time lookup.
- A doubly linked list orders nodes from most to least recently used.
The most recently used entry sits at the front and the eviction victim sits at the back.
How a get and a put work
On a get, the hash map finds the node, then the node is unlinked and moved to the front to mark it freshly used. On a put, a new node is added to the front and recorded in the map; if capacity is exceeded, the node at the back is removed from both the list and the map. Every step is a constant time pointer or map operation.
Key idea
An LRU cache pairs a hash map for constant time lookup with a doubly linked list ordered by recency, so getting, updating, and evicting the least recently used entry all run in constant time.