Intermediate · INTERACTIVE LESSON

LRU cache eviction

Follow key accesses, recency updates and least-recently-used capacity evictions.

The interactive player is loading. If it does not appear, you can still read the explanation below.

THE IDEA BEHIND THE STEPS

How it works

An LRU (least recently used) cache remembers recent accesses. On a hit, move the key to the most-recent position. On a miss, insert it as most recent; if full, first remove the least-recent key. A hit never evicts another key.

Start with an empty cache of 1–8 entries and up to 32 sequential, case-sensitive key accesses. Lookup, hit/miss, eviction (when needed) and recency update are separate steps. Keys identify entries even when their positions change. No clock or service latency is simulated.

For capacity 2, A, B, A, C finishes in most-to-least order C, A: the second A is a hit and makes B the eviction victim. Compare Working set fits with Capacity thrashing using the same access sequence and different capacities.

Hits and misses each count one completed lookup; evictions count entries removed to make space. Hit ratio is hits divided by hits plus misses, displayed as a percentage rounded to two decimal places, with 0% before any lookup. Intermediate lookup steps do not count an outcome until hit or miss.

A hash map plus doubly linked list supports average O(1) lookup/update and O(capacity) space. This teaching engine uses array searches and copied snapshots for replay; its internal costs are not the conceptual implementation complexity.

Capacity eviction is different from TTL expiration: LRU uses recency, not age or a freshness deadline. This model has no TTL, concurrent clients, writes, persistence, backing-store latency or freshness guarantees. LRU can thrash when the working set exceeds capacity and does not predict future accesses.