Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

LFU caches: evict by frequency, then recency

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An LFU cache tracks how often each resident key has been accessed. When full, it evicts a key from the smallest frequency group; within that group, it chooses the least recently accessed or written key. This implementation keeps a key-to-value-and-frequency map and an ordered key set for each active frequency. Reading a present key promotes it to the next group. Updating an existing key replaces its value and counts as one access. Inserting a new key starts at frequency one. Empty frequency groups are removed, and the minimum active frequency is kept explicitly. A miss returns None and does not alter counts. Capacity zero stores nothing. The cache is single-process and has no frequency aging or expiry policy.

Operational case

An incident dashboard stores pump-47 and valve-19 in a cache with capacity two. Reading pump-47 increases its frequency. Inserting sensor-61 evicts valve-19, the only key still at the minimum frequency. Pump-47 remains available and valve-19 is absent. The internal ordered sets also decide a tie: if both keys had frequency one, the earlier member of that group would leave first. An update to a resident key is explicitly treated as an access, which differs from implementations that update without promotion. The policy must be chosen before comparing observed evictions with a reference model.

Working Python program

python
from collections import OrderedDict, defaultdict


class IncidentLFUCache:
    def __init__(self, capacity):
        if capacity < 0:
            raise ValueError("capacity cannot be negative")
        self.capacity = capacity
        self.entries = {}
        self.by_frequency = defaultdict(OrderedDict)
        self.minimum_frequency = 0

    def _promote(self, key):
        value, frequency = self.entries[key]
        del self.by_frequency[frequency][key]
        if not self.by_frequency[frequency]:
            del self.by_frequency[frequency]
            if self.minimum_frequency == frequency:
                self.minimum_frequency = frequency + 1
        self.entries[key] = (value, frequency + 1)
        self.by_frequency[frequency + 1][key] = None

    def get(self, key):
        if key not in self.entries:
            return None
        value = self.entries[key][0]
        self._promote(key)
        return value

    def put(self, key, value):
        if self.capacity == 0:
            return None
        if key in self.entries:
            _, frequency = self.entries[key]
            self.entries[key] = (value, frequency)
            self._promote(key)
            return None
        evicted = None
        if len(self.entries) == self.capacity:
            evicted, _ = self.by_frequency[self.minimum_frequency].popitem(last=False)
            del self.entries[evicted]
            if not self.by_frequency[self.minimum_frequency]:
                del self.by_frequency[self.minimum_frequency]
        self.entries[key] = (value, 1)
        self.by_frequency[1][key] = None
        self.minimum_frequency = 1
        return evicted


if __name__ == "__main__":
    cache = IncidentLFUCache(2)
    cache.put("pump-47", "active")
    cache.put("valve-19", "review")
    cache.get("pump-47")
    print("evicted=", cache.put("sensor-61", "active"), sep="")
    print("pump=", cache.get("pump-47"), sep="")
    print("valve=", cache.get("valve-19"), sep="")

Output

Output
evicted=valve-19
pump=active
valve=None

Time, space, and tradeoff

For capacity C, expected lookup, promotion, insertion, and eviction are O(1) using hash maps and ordered dictionaries. Resident entries and their frequency-group membership use O(C) space, while the number of active groups is at most C. These are expected hash-operation bounds, not real-time guarantees. Frequencies grow without decay, so an old hot entry can resist eviction after the workload changes; production caches may age or reset counts. An LRU cache needs only one recency order and can be simpler. This LFU example does not bound retained Python integer frequency width, add thread synchronization, distinguish a stored None from a miss, or combine eviction with time-to-live.

Common Mistakes

  • Do not evict the newest key when frequencies tie; this policy uses least recent.
  • Do not leave an empty minimum-frequency group behind after promotion.
  • Do not change counts on a miss.
  • Do not call lifetime access counts an aging frequency policy.

Connected lessons

Compare its invariant with Expiry heaps: invalidate stale TTL records on replacement, Generational slots: reject stale handles after reuse, D-ary heaps: trade shallower ascent for wider extraction, then run the retention and dispatch audit and operation quiz.

Misra–Gries: find frequent-item candidates in one pass adds a bounded stream contract.

Segmented LRU: separate probation from protected reuse extends the retention comparison.

Frequency admission: compare an arrival with an eviction victim extends the retention comparison.

All-one frequency buckets: increment, decrement, and read both extremes examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details