LFU Cache
Evicts the Least Frequently Used item instead of the least recent. Needs a frequency count per key plus, for true O(1) operations, buckets of keys grouped by frequency.
An LFU cache tracks how many times each key has been accessed and evicts the lowest-frequency key when full (ties broken by recency). This protects items that are accessed constantly but happened not to be touched in the last few operations — exactly the case where LRU would wrongly evict them.
A naive version keeps a frequency count and scans for the minimum on eviction — O(n). The O(1) version keeps a hash map of key → (value, frequency) alongside frequency buckets: each bucket holds an ordered set of keys sharing that frequency, and a pointer tracks the current minimum frequency. Incrementing a key's count moves it to the next bucket; eviction pops from the min-frequency bucket.
The trade-off is complexity: LFU's bookkeeping is heavier than LRU's, and it adapts slower to shifting access patterns (yesterday's popular key can linger). Many production caches use LFU variants with decay, halving frequencies periodically so old popularity fades.
Operations
| Operation | Complexity |
|---|---|
| get(key) | O(1) with buckets |
| put(key, value) | O(1) with buckets |
| evict LFU | O(1) with buckets |
| space | O(capacity) |
Where it's used
Caches where access frequency matters more than recency — CDN content ranking, database query caches, recommendation systems.