HashingHashing

LFU Cache

A fixed-capacity cache that evicts the entry with the lowest access count (ties broken by least recent), in O(1) using a map of frequency buckets.

Learn LFU Cache →
valuefreqlast used
(empty)———
Frequency buckets (LRU → MRU inside each)
empty
Recency (least → most recently used)
empty
1/17An empty LFU cache holding at most 3 entries. Rows are kept in eviction order — frequency first, then how long ago the entry was used — so the top row is always the key that would go next.
Entry touched by this operationNext victim (min frequency, least recently used)Also in the minimum-frequency bucketBeing evicted nowProtected by a higher frequency
PseudocodeLearn LFU Cache →
1get(key):
2  if key not cached: return -1                        # a miss changes nothing
3  freq[key] += 1; move key from bucket[f] to bucket[f+1]
4  if bucket[minFreq] is now empty: minFreq += 1
5put(key, value):
6  if key cached: overwrite value, then bump frequency as in get
7  else if size == capacity:
8    victim = least-recently-used key in bucket[minFreq]   # the tie-break
9  store key with freq = 1; minFreq = 1
Variables
capacity3
size0
minFreq—
hits0
misses0
evictions0
Complexity
access O(1)
search O(1)
insert O(1)
delete O(1)
Speed