Least Frequently Used (LFU) Cache

An LFU (Least Frequently Used) cache is a cache eviction algorithm that tracks how many times each item is accessed. When the cache reaches its maximum capacity, the item with the lowest access frequency is evicted. If multiple items share the same lowest frequency, the least recently used (LRU) item among them is typically evicted (tie-breaking via LRU).

LFU vs. LRU

Feature	LRU (Least Recently Used)	LFU (Least Frequently Used)
Eviction Metric	Time since last access (recency)	Number of accesses (frequency)
Data Structure	Hash Map + Single Doubly Linked List	Hash Map + Frequency Doubly Linked Lists
Time Complexity	O(1) get / put	O(1) get / put (or O(log N) with heaps)
Weakness	Vulnerable to scans/bursts of one-off reads	Vulnerable to historical items retaining high frequency ("frequency pollution")

Achieving O(1) Time Complexity

A naive LFU using a Min-Heap requires O(log N) per operation. An optimal O(1) LFU cache uses two hash maps and a set of doubly linked lists:

+--------------------------------------------------------------+
| key_map:   key -> Node(key, value, freq)                     |
|                                                              |
| freq_map:  frequency -> DoublyLinkedList of Nodes           |
|                                                              |
|   freq = 1:   [Node A] <-> [Node B]                          |
|   freq = 2:   [Node C]                                       |
|   freq = 5:   [Node D] <-> [Node E]                          |
|                                                              |
| min_freq:  1 (Tracks minimum frequency across active items)  |
+--------------------------------------------------------------+

Key Components

key_map: Maps each key to its corresponding Node(key, value, freq).
freq_map: Maps each frequency count f to a Doubly Linked List holding all nodes that have been accessed f times. Nodes within each list are ordered by recency.
min_freq: An integer pointer tracking the lowest frequency currently present in the cache.

Core Operations

get(key):
1. If key is absent, return -1.
2. Increase the node's frequency from f to f + 1.
3. Remove the node from freq_map[f] and append it to freq_map[f + 1].
4. If freq_map[f] is now empty and min_freq == f, increment min_freq = f + 1.
5. Return node.val.
put(key, value):
1. If key exists, update value and call get(key) to increment its frequency.
2. If key does not exist and cache is at capacity:
  - Pop the least recently used node from the list at freq_map[min_freq].
  - Delete that node from key_map.
3. Insert the new node with frequency 1, add to freq_map[1], and reset min_freq = 1.

Python Implementation (O(1))

class Node:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        self.freq = 1
        self.prev = None
        self.next = None

class DLinkedList:
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_node(self, node: Node):
        """Append node right before tail (most recent for this freq)."""
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        self.size += 1

    def remove_node(self, node: Node) -> Node:
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node

    def pop_first(self) -> Node:
        """Evict oldest item right after head."""
        return self.remove_node(self.head.next)

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.min_freq = 0
        self.key_map = {}   # key -> Node
        self.freq_map = {}  # freq -> DLinkedList

    def _update_freq(self, node: Node):
        f = node.freq
        self.freq_map[f].remove_node(node)
        if self.freq_map[f].size == 0 and self.min_freq == f:
            self.min_freq += 1

        node.freq += 1
        if node.freq not in self.freq_map:
            self.freq_map[node.freq] = DLinkedList()
        self.freq_map[node.freq].add_node(node)

    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        node = self.key_map[key]
        self._update_freq(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return

        if key in self.key_map:
            node = self.key_map[key]
            node.val = value
            self._update_freq(node)
            return

        if self.size >= self.capacity:
            evicted = self.freq_map[self.min_freq].pop_first()
            del self.key_map[evicted.key]
            self.size -= 1

        new_node = Node(key, value)
        self.key_map[key] = new_node
        if 1 not in self.freq_map:
            self.freq_map[1] = DLinkedList()
        self.freq_map[1].add_node(new_node)
        self.min_freq = 1
        self.size += 1

Real-World Engineering: Redis Approximated LFU

Maintaining full doubly linked lists and exact 64-bit frequency counters per key consumes significant memory. Redis instead implements an approximated LFU using just 24 bits inside each object header (robj.lru):

16 bits for Last Decrement Time (LDT): Encodes the timestamp of last access in minutes. Used to decay the frequency over time so old, unused hot keys gradually lose priority.
8 bits for Logarithmic Counter (LOG_C): A probabilistic counter scaled logarithmically from 0 to 255.

// Redis logarithmic counter increment
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand() / RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0 / (baseval * server.lfu_log_factor + 1);
    if (r < p) counter++;
    return counter;
}

With lfu_log_factor = 10:
- 100 hits ≈ counter value 10
- 1,000 hits ≈ counter value 18
- 100,000 hits ≈ counter value 142
- 1,000,000 hits ≈ counter value 255