LFU Cache

A cache that evicts the least-frequently-used entry, favoring items accessed often over items accessed merely recently.

Frequency over recency

Least-frequently-used (LFU) caching tracks how many times each entry has been accessed and evicts the entry with the smallest count. It suits workloads where popularity is stable and a small set of hot items dominates, whereas LRU favors recency.

O(1) implementation

Kronos motion — classical

A constant-time LFU keeps a hash map from key to node, a second map from frequency to a doubly linked list of nodes at that frequency, and a running minimum frequency. On access, a node moves from its current frequency list to the next; on eviction, the front of the min-frequency list is removed. All updates are O(1).

Structure

python

class LFUCache:
    def __init__(self, cap):
        self.cap = cap
        self.key_to = {}          # key -> (val, freq)
        self.freq_to = {}         # freq -> ordered keys
        self.min_freq = 0
    def _bump(self, key):
        val, f = self.key_to[key]
        self.freq_to[f].pop(key)
        if not self.freq_to[f] and f == self.min_freq:
            self.min_freq += 1
        self.key_to[key] = (val, f+1)
        self.freq_to.setdefault(f+1, OrderedDict())[key] = None

The aging problem

Old items with a high historical count can resist eviction long after they stop being useful.
Window LFU and decay counters reduce old counts over time to stay adaptive.
TinyLFU uses an approximate frequency sketch (a count-min-like filter) as an admission policy in front of an LRU eviction list.
ARC and W-TinyLFU blend recency and frequency to avoid the weaknesses of each.

Choosing between LFU and LRU

Prefer LFU when access frequencies are stable and skewed; prefer LRU when the working set shifts over time. Modern caches often combine both, using a frequency sketch for admission and a recency list for eviction.