Often several keys share the lowest use count, and the scan has to pick one. LFU breaks that tie the LRU way - among the least-frequently-used, evict the one used least recently. Today you add the recency tie-breaker.
When several keys share the minimum frequency, evict the least-recently-used among them.
A pure frequency count is not a total order - lots of keys sit at frequency 1, or 2, or 3 - so eviction needs a tie-breaker, and the standard choice folds LRU into LFU: among the keys with the lowest frequency, evict the one used least recently. It is the best of both signals - frequency first, recency as the decider - and it is exactly what the real O(1) LFU design encodes structurally.
To know “least recently used” you need a recency stamp, so add a rising clock to
the cache and a tick to each entry, writing the current clock onto an entry on
every use: its insert, a Get hit, and a Put update. Then the scan takes two
keys into account - smallest frequency wins, and on a tie the smallest tick (the
oldest use) wins. Prove it decides the outcome by swapping the two Gets: the same
frequencies, a different recency, and the victim flips. This recency-within-frequency
rule is the behaviour the next lessons must preserve while making eviction O(1).
// give each entry a "last used" stamp from a rising countertype entry struct { key, val, freq, tick int }// bump c.clock and store it on every use (insert, Get hit, Put update)// evict: pick the lowest freq; among equal freq, the smallest tick// if e.freq < min || (e.freq == min && e.tick < bestTick) { ... }