LRU Cache

A fixed-capacity cache that evicts the least-recently-used entry, giving O(1) get and put with a hash map and linked list.

The eviction policy

When a cache reaches capacity, it must choose an entry to discard. Least-recently-used (LRU) evicts the item that has gone longest without access, betting that recently used data will be used again soon (temporal locality). It is the default policy in many CPU caches, database buffer pools, and application caches.

O(1) design

Kronos motion — classical

The standard implementation combines a hash map from key to node with a doubly linked list ordered by recency. Get moves the accessed node to the front; put inserts at the front and, on overflow, removes the tail. Both the map lookup and the list splice are O(1), so every operation is constant time.

Compact version

python

from collections import OrderedDict

class LRUCache:
    def __init__(self, cap):
        self.cap = cap
        self.d = OrderedDict()
    def get(self, key):
        if key not in self.d:
            return -1
        self.d.move_to_end(key)
        return self.d[key]
    def put(self, key, val):
        if key in self.d:
            self.d.move_to_end(key)
        self.d[key] = val
        if len(self.d) > self.cap:
            self.d.popitem(last=False)  # evict LRU

Limitations and variants

A single large scan can flush useful entries (scan pollution); segmented LRU and ARC mitigate this.
Clock (second-chance) approximates LRU with a reference bit and a circular buffer, cheaper for OS page replacement.
LRU-K considers the K-th most recent access to distinguish frequency from recency.
For frequency-biased workloads prefer LFU.

Why recency works

LRU is a good heuristic because many access patterns exhibit locality: a page touched now is likely touched again soon. It is provably competitive within a factor of its size against the offline optimal (Belady) policy under the standard competitive-analysis model, an amortized-style guarantee on worst-case behavior.