Is LFU strictly better than LRU since it tracks more information?

No — LFU has its own failure mode: a key that was extremely popular yesterday but hasn't been touched since can sit at a high frequency count forever, permanently blocking eviction even though it's now cold. Real LFU implementations often add frequency decay over time to fix this; the version here doesn't, to keep the comparison to LRU clean.

Why does LFU's eviction pick the alphabetically-first key when frequencies tie?

It doesn't, intentionally — `min()` with a `key` function returns the first item it encounters with the minimum value, which in this implementation happens to be insertion order, not alphabetical order. That's a real, easy-to-miss implementation detail, not a documented tie-breaking rule a caller should rely on.

What is 'scan resistance' and why does it matter?

It's a cache's ability to survive a one-time burst of unique keys without evicting the genuinely popular ones — a batch job or a crawler scanning many records once is a realistic event, and it's a scenario where LRU loses a hot key to the scan while LFU, tracking real access frequency instead of recency, keeps it.

Which one would a real production cache actually use?

It depends on the access pattern, which is exactly why this lesson doesn't declare a winner. Redis supports both (allkeys-lru and allkeys-lfu as eviction policies) precisely because different workloads favor different tradeoffs — recency-heavy traffic favors LRU, popularity-skewed traffic favors LFU.

Cache Eviction: When LRU and LFU Actually Disagree

LRU asks “what haven’t I touched in a while?” and LFU asks “what do I touch the least?” — those are different questions, and they can point at different keys.

Same operations, different eviction

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            evicted, _ = self.data.popitem(last=False)
            print(f"  [LRU] evicted {evicted!r}")

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}
        self.freq = {}

    def get(self, key):
        if key not in self.data:
            return None
        self.freq[key] += 1
        return self.data[key]

    def put(self, key, value):
        if key not in self.data and len(self.data) >= self.capacity:
            evicted = min(self.freq, key=self.freq.get)
            del self.data[evicted]
            del self.freq[evicted]
            print(f"  [LFU] evicted {evicted!r}")
        self.data[key] = value
        self.freq[key] = self.freq.get(key, 0) + 1

print("LRU cache (capacity 2):")
lru = LRUCache(2)
lru.put("A", 1)
lru.put("B", 2)
lru.get("A")
lru.get("A")
lru.get("A")
lru.get("B")
lru.put("C", 3)

print()
print("LFU cache (capacity 2), same operation sequence:")
lfu = LFUCache(2)
lfu.put("A", 1)
lfu.put("B", 2)
lfu.get("A")
lfu.get("A")
lfu.get("A")
lfu.get("B")
lfu.put("C", 3)

$ python lru_vs_lfu.py
LRU cache (capacity 2):
  [LRU] evicted 'A'

LFU cache (capacity 2), same operation sequence:
  [LFU] evicted 'B'

By the time C needs room, B was the most recently touched key (the last get before the new put), so LRU evicts A. But A was accessed 3 times to B’s 1, so LFU evicts B — the exact opposite decision, from the exact same sequence of operations, because the two policies are measuring different things.

Practice

1. Increase capacity to 3 and confirm the same sequence causes no eviction at all.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            evicted, _ = self.data.popitem(last=False)
            print(f"  evicted {evicted!r}")

print("LRU cache (capacity 3), same 5 puts as before plus one more:")
lru = LRUCache(3)
lru.put("A", 1)
lru.put("B", 2)
lru.get("A")
lru.get("A")
lru.get("A")
lru.get("B")
lru.put("C", 3)
print(f"final contents: {list(lru.data.keys())}")

$ python capacity_three.py
LRU cache (capacity 3), same 5 puts as before plus one more:
final contents: ['A', 'B', 'C']

No evicted line prints at all — with room for 3 keys and only 3 ever inserted, the eviction branch in put is never triggered.

2. Simulate a one-time scan of unrelated keys and see which policy protects a "hot" key from it.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            evicted, _ = self.data.popitem(last=False)
            print(f"  [LRU] evicted {evicted!r}")

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}
        self.freq = {}

    def get(self, key):
        if key not in self.data:
            return None
        self.freq[key] += 1
        return self.data[key]

    def put(self, key, value):
        if key not in self.data and len(self.data) >= self.capacity:
            evicted = min(self.freq, key=self.freq.get)
            del self.data[evicted]
            del self.freq[evicted]
            print(f"  [LFU] evicted {evicted!r}")
        self.data[key] = value
        self.freq[key] = self.freq.get(key, 0) + 1

print("LRU cache (capacity 2) hit by a one-time scan:")
lru = LRUCache(2)
lru.put("H", "hot-data")
lru.get("H")
lru.get("H")
lru.get("H")
for scan_key in ["scan-1", "scan-2", "scan-3"]:
    lru.put(scan_key, "one-time-data")
print(f"  is 'H' still cached? {'H' in lru.data}")

print()
print("LFU cache (capacity 2), same scenario:")
lfu = LFUCache(2)
lfu.put("H", "hot-data")
lfu.get("H")
lfu.get("H")
lfu.get("H")
for scan_key in ["scan-1", "scan-2", "scan-3"]:
    lfu.put(scan_key, "one-time-data")
print(f"  is 'H' still cached? {'H' in lfu.data}")

$ python scan_resistance.py
LRU cache (capacity 2) hit by a one-time scan:
  [LRU] evicted 'H'
  [LRU] evicted 'scan-1'
  is 'H' still cached? False

LFU cache (capacity 2), same scenario:
  [LFU] evicted 'scan-1'
  [LFU] evicted 'scan-2'
  is 'H' still cached? True

H is the most-accessed key in both caches, yet LRU evicts it on the very first scan write — recency doesn’t care how popular a key was, only when it was last touched. LFU keeps H cached through the whole scan, since 3 accesses beats a scan key’s single access every time.

3. Query a key that was never inserted, and confirm it returns None instead of raising.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            evicted, _ = self.data.popitem(last=False)
            print(f"  evicted {evicted!r}")

cache = LRUCache(2)
cache.put("A", 1)
result = cache.get("Z")
print(f"get('Z') on a cache that never had it: {result}")

$ python missing_key.py
get('Z') on a cache that never had it: None

The if key not in self.data: return None guard at the top of get is what makes a cache miss a normal return value instead of a KeyError — a caller checks if result is None instead of wrapping every lookup in a try/except.

4. Force a tie in LFU's frequency counts and see which key actually gets evicted.

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}
        self.freq = {}

    def get(self, key):
        if key not in self.data:
            return None
        self.freq[key] += 1
        return self.data[key]

    def put(self, key, value):
        if key not in self.data and len(self.data) >= self.capacity:
            evicted = min(self.freq, key=self.freq.get)
            del self.data[evicted]
            del self.freq[evicted]
            print(f"  evicted {evicted!r}")
        self.data[key] = value
        self.freq[key] = self.freq.get(key, 0) + 1

lfu = LFUCache(2)
lfu.put("A", 1)
lfu.put("B", 2)
print(f"frequencies before third put (tied): {lfu.freq}")
lfu.put("C", 3)

$ python lfu_tie_break.py
frequencies before third put (tied): {'A': 1, 'B': 1}
  evicted 'A'

A and B are tied at frequency 1, and min() returns the first key it encounters with the minimum value — here that’s insertion order, so A loses the tie simply because it was put in first. Nothing in this implementation makes that a deliberate policy; a production LFU cache usually breaks ties with a secondary key (like recency) instead of leaving it to dict iteration order.

Same operations, different eviction

Practice

Frequently Asked Questions