Why eviction is needed
A cache has limited memory. When it is full and a new item must be stored, an eviction policy decides which existing entry to remove. The goal is to keep the items most likely to be used again.
How LRU works
Least Recently Used evicts the entry that was accessed longest ago. It assumes the recent past predicts the near future, so a key untouched for a long time is the safest to drop.
A common implementation pairs a hash map for lookup with a doubly linked list ordering keys by recency. Each access moves the key to the front, and eviction removes the tail.
Strengths and weaknesses
- It adapts well to temporal locality, where recently used data is reused soon.
- Lookup, insert, and eviction are all constant time.
- A single large scan of many unique keys can flush out hot data, since each scanned key looks recent.
Key idea
LRU evicts the entry untouched for the longest time, working in constant time and exploiting the fact that recently used data tends to be used again.