LRU Cache
Updated 2026-08-17
INTRODUCTION
English translation pending.
CORE DEFINITION
Least recently used is a cache eviction policy that discards the entry that has not been accessed for the longest time when space runs out. It rests on temporal locality, the empirical regularity that data used recently is more likely to be used again soon. A standard implementation combines a hash map for constant-time lookup with a doubly linked list that keeps entries in access order, so a hit moves an entry to the front and an eviction removes the tail. The policy requires no knowledge of future access patterns, which is why it appears in operating system page caches, database buffer pools, and web caches.
SCAFFOLDING EFFECT
Reduce cognitive load
- Capacity planning: Size the cache from observed reuse distances rather than from total data volume. - Eviction choice: Pick least recently used only when reuse is dominated by recency, not by frequency. - Cost check: Weigh the bookkeeping per hit against the latency the cache actually saves.
Anchor fast decisions
Reuse is not uniformly distributed in time: after an item is touched, the probability that it is touched again decays as other items intervene. Keeping the most recently used entries therefore captures a disproportionate share of future hits, so the eviction decision can be made from past access order alone. The structure also makes the policy cheap, because a hash map plus a linked list gives constant-time lookup, promotion, and removal.
MINIMUM ACTION
In progress 0/1Practice this model in one real situation:
account_treeGenealogyexpand_more
menu_bookReferencesexpand_more
Source support: Explicit
- github.comhttps://github.com/kcchien/model-thinkingverified
PRIVATE NOTES · Only visible to you
SAVED Q&A
ENTRY Q&A · Private saving available
Ask with a clear boundary
thinkingmodels answers from published entry context only.
Your question is sent to thinkingmodels. The answer uses public entry context only.
RELATED MODELS