Hi Pythonistas!
Last post we learned what caching is.Cache hit. Cache miss. TTL. Eviction policies.But I left one question unanswered.
How does LRU actually find the least recently used item instantly?
How does LFU track frequencies without slowing down?
The answer is data structures.The right data structure is what makes a cache fast.Not the concept.The implementation.Let's build each one from scratch.The Goal - O(1) Everything Before we start - why does the data structure matter so much?
A cache handles millions of requests per second.Every get and put must be:O(1) → constant time Not O(n). Not O(log n). O(1).
Doesn't matter if cache has 100 items or 10 million.Same speed. That constraint is what forces specific data structure choices.
LRU - Least Recently Used
LRU needs to answer two questions instantly:
1. Is this key in cache? → O(1)
2. Which item was least recently used? → O(1)
A plain hashmap answers question 1 in O(1).But can't answer question 2.A plain linked list answers question 2.But can't answer question 1 fast.Neither alone works.So LRU uses both together.HashMap + Doubly Linked List.
The Structure
HashMap: key → pointer to node in linked list
Doubly Linked List:
Most Recent ←→ [node] ←→ [node] ←→ [node] ←→ Least Recent
HEAD TAIL
Every time an item is accessed: move it to the front (HEAD).
Item at the TAIL = least recently used.
When cache is full → remove TAIL.
How Operations Work
GET:
1. HashMap lookup → O(1) → find node
2. Move node to HEAD → O(1) (doubly linked, direct pointer)
3. Return value
PUT:
1. Already exists?
→ update value
→ move to HEAD
2. New item?
→ add node at HEAD
→ add to HashMap
→ if full → remove TAIL → remove from HashMap
Everything O(1).No searching. No sorting.Direct pointer operations.
Implementation
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
# move to end = most recent
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
# remove first = least recent
self.cache.popitem(last=False)OrderedDict maintains insertion order internally.Uses a doubly linked list under the hood.
move_to_end → O(1).popitem(last=False) → remove oldest → O(1).
cache = LRUCache(3)
cache.put('user:1', 'Afsal')
cache.put('user:2', 'Pythonista')
cache.put('user:3', 'Kerala')
# Cache: [user:1, user:2, user:3]
cache.get('user:1')
# user:1 accessed → moves to front
# Cache: [user:2, user:3, user:1]
cache.put('user:4', 'New User')
# Cache full → evict least recent → user:2
# Cache: [user:3, user:1, user:4]
print(cache.get('user:2')) # -1 (evicted)
print(cache.get('user:3')) # 'Kerala' (still there)LFU - Least Frequently Used
LFU is harder.
Needs to answer:
1. Is this key in cache? → O(1)
2. Which item has lowest frequency? → O(1)
3. Among same frequency — which is oldest? → O(1)
Three questions. All O(1).
Needs three data structures together:
key_to_val = {} # key → value
key_to_freq = {} # key → frequency count
freq_to_keys = {} # frequency → OrderedDict of keys
# (OrderedDict preserves insertion order)
min_freq = 0 # track current minimum frequency
How Operations Work
GET:
1. key_to_val lookup → get value → O(1)
2. Increment frequency in key_to_freq → O(1)
3. Move key from freq bucket to freq+1 bucket → O(1)
4. Update min_freq if needed → O(1)
PUT:
If full:
1. Look at min_freq bucket
2. Remove oldest key in that bucket → O(1) (OrderedDict)
3. Remove from key_to_val, key_to_freq
Insert new:
1. Add to key_to_val → O(1)
2. Set frequency to 1 in key_to_freq → O(1)
3. Add to freq_to_keys[1] → O(1)
4. Set min_freq = 1
Implementation
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.min_freq = 0
self.key_to_val = {}
self.key_to_freq = {}
self.freq_to_keys = defaultdict(OrderedDict)
def get(self, key):
if key not in self.key_to_val:
return -1
self._increment_freq(key)
return self.key_to_val[key]
def put(self, key, value):
if self.capacity <= 0:
return
if key in self.key_to_val:
self.key_to_val[key] = value
self._increment_freq(key)
return
if len(self.key_to_val) >= self.capacity:
# evict least frequent, oldest among ties
evict_key, _ = self.freq_to_keys[self.min_freq].popitem(
last=False
)
del self.key_to_val[evict_key]
del self.key_to_freq[evict_key]
# insert new item
self.key_to_val[key] = value
self.key_to_freq[key] = 1
self.freq_to_keys[1][key] = None
self.min_freq = 1
def _increment_freq(self, key):
freq = self.key_to_freq[key]
self.key_to_freq[key] = freq + 1
# remove from current freq bucket
del self.freq_to_keys[freq][key]
# update min_freq if bucket now empty
if not self.freq_to_keys[freq] and freq == self.min_freq:
self.min_freq += 1
# add to next freq bucket
self.freq_to_keys[freq + 1][key] = None
cache = LFUCache(3)
cache.put('user:1', 'Afsal')
cache.put('user:2', 'Pythonista')
cache.put('user:3', 'Kerala')
cache.get('user:1') # freq: user:1=2, user:2=1, user:3=1
cache.get('user:1') # freq: user:1=3, user:2=1, user:3=1
cache.get('user:2') # freq: user:1=3, user:2=2, user:3=1
cache.put('user:4', 'New User')
# Cache full
# min_freq = 1 → user:3 is least frequent
# user:3 evicted
print(cache.get('user:3')) # -1 (evicted)
print(cache.get('user:1')) # 'Afsal' (still there)FIFO - First In First Out
Simplest of all.Just a HashMap + Queue.
from collections import deque
class FIFOCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.queue = deque()
def get(self, key):
return self.cache.get(key, -1)
def put(self, key, value):
if key not in self.cache:
if len(self.cache) >= self.capacity:
# remove oldest
oldest = self.queue.popleft()
del self.cache[oldest]
self.queue.append(key)
self.cache[key] = valueQueue tracks insertion order.Evict from front (oldest).No reordering needed.O(1) for everything.
Random Eviction
Simplest possible.Just a HashMap.
import random
class RandomCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
def get(self, key):
return self.cache.get(key, -1)
def put(self, key, value):
if len(self.cache) >= self.capacity:
random_key = random.choice(list(self.cache.keys()))
del self.cache[random_key]
self.cache[key] = valuePick any key randomly.Evict it.No tracking needed.Surprisingly effective in practice.
Side by Side
Policy Data Structure Get Put
──────────────────────────────────────────────────────
LRU HashMap + Doubly Linked List O(1) O(1)
LFU 3x HashMap + OrderedDict O(1) O(1)
FIFO HashMap + Queue O(1) O(1)
Random HashMap O(1) O(1)
All O(1).
Different policies. Different data structures. Same performance.
Mental Model
O(1) → constant time regardless of cache size
HashMap → O(1) lookup by key
Doubly linked list → O(1) move any node to front or back
OrderedDict → Python's built-in doubly linked list hashmap
LRU → HashMap + Doubly Linked List
LFU → key_to_val + key_to_freq + freq_to_keys
FIFO → HashMap + Queue
Random → HashMap only
Dummy nodes → simplify edge cases in linked list
min_freq → LFU tracks current minimum frequency
What Changed for Me
Before this:LRU was just a concept."Remove the least recently used item."
After this:
LRU is a HashMap pointing into a doubly linked list.Every access moves a node.Every eviction removes a tail.
O(1) because of pointer operations.Not magic.Data structures.
What's Coming Next
Now your system has:multiple servers.load balancing.caching.
But static files -images, CSS, JavaScript are still served from your server.User in the US hits your server in India.200ms just for the network.
CDN - Content Delivery Network.How to serve files from everywhere on earth as if your server is next door.
