LRU caches and composite structures

Combining a hash map with a doubly linked list for O(1) eviction, the TTL and LFU variants, thread-safety concerns, and the metrics that tell you whether the cache helps.

Hash map plus doubly linked list

An LRU cache needs two things at once: find an entry by key in constant time, and know which entry was used least recently. No single structure does both, so it layers them — a map from key to node, and a list ordered by recency.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()          # insertion order tracks recency

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)         # mark as most recently used
        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:
            self.data.popitem(last=False)  # evict the oldest

• Map lookup is O(1) expected; list splice is O(1) with a doubly linked list.
• Both operations are needed on every read, which is why hand-rolled versions skip the list update and become FIFO by accident.
• Storing the list node inside the map value avoids a second lookup during eviction.
• Eviction order and TTL are orthogonal: a cache can be both LRU and expiring.

Choosing an eviction policy

import time

class TTLCache:
    """LRU plus a deadline per entry."""
    def __init__(self, capacity, ttl_seconds):
        self.capacity, self.ttl = capacity, ttl_seconds
        self.data, self.expires = OrderedDict(), {}

    def get(self, key):
        if key not in self.data or self.expires[key] <= time.monotonic():
            self.data.pop(key, None)
            self.expires.pop(key, None)
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.expires[key] = time.monotonic() + self.ttl
        if len(self.data) > self.capacity:
            old, _ = self.data.popitem(last=False)
            self.expires.pop(old, None)

Making a cache you can trust

• Stampedes — when a hot key expires, every caller recomputes it. Coalesce concurrent misses behind a per-key lock.
• Negative caching — cache misses too, with a shorter TTL, or a missing key is queried on every request.
• Invalidation — a cache without a delete path is a bug source. Make invalidation part of the write path, not an afterthought.
• Thundering herd on start — an empty cache after a deploy sends a burst to the database. Warm it or add jitter.
• Thread safety — the map plus list combination is not atomic. Guard it with one lock, or use a sharded concurrent implementation.

FAQ

Related

Sets, maps and the abstract data type view Benchmarking and testing your data structure

Last refreshed 2026-09-18.