Composing Hash Maps + Doubly Linked Lists: O(1) LRU & LFU Caches

Data Structure Composition: Why Hash Map + Doubly Linked List?

In an LRU (Least Recently Used) cache of capacity $C$:

• get(key) must look up the key in $O(1)$ time and move its entry to the Most Recently Used (MRU) head of the recency order in $O(1)$ time.
• put(key, val) must insert or update the key at the MRU head in $O(1)$ time, and if size exceeds $C$, evict the Least Recently Used (LRU) tail entry in $O(1)$ time.

Cache Eviction Policies & Production Systems Comparison

Visualizing O(1) LFU Frequency-Bucketed Doubly Linked Lists

LFU Promotion & min_freq State Transition Diagram

Production Implementation: Contiguous Arena-Backed O(1) LRU Cache

#include <cstdint>
#include <unordered_map>
#include <vector>

// High-locality O(1) LRU Cache using a pre-allocated Node pool (0 mallocs after construction!)
class FastLRUCache {
  struct Node {
    int key = 0;
    int value = 0;
    int prev = 0;
    int next = 0;
  };

  int cap_;
  std::vector<Node> pool_; // Index 0 is the circular dummy sentinel!
  std::vector<int> free_list_;
  std::unordered_map<int, int> index_map_;

  void unlink(int u) noexcept {
    const int p = pool_[u].prev;
    const int n = pool_[u].next;
    pool_[p].next = n;
    pool_[n].prev = p;
  }

  void push_mru_front(int u) noexcept {
    const int first = pool_[0].next;
    pool_[u].prev = 0;
    pool_[u].next = first;
    pool_[first].prev = u;
    pool_[0].next = u;
  }

public:
  explicit FastLRUCache(int capacity) : cap_(capacity), pool_(capacity + 1) {
    pool_[0].prev = 0;
    pool_[0].next = 0;
    free_list_.reserve(capacity);
    for (int i = capacity; i >= 1; --i) {
      free_list_.push_back(i);
    }
    index_map_.reserve(capacity * 2);
  }

  int get(int key) noexcept {
    auto it = index_map_.find(key);
    if (it == index_map_.end()) return -1;
    const int u = it->second;
    unlink(u);
    push_mru_front(u);
    return pool_[u].value;
  }

  void put(int key, int value) {
    if (cap_ <= 0) return;
    auto it = index_map_.find(key);
    if (it != index_map_.end()) {
      const int u = it->second;
      pool_[u].value = value;
      unlink(u);
      push_mru_front(u);
      return;
    }

    int u = 0;
    if (!free_list_.empty()) {
      u = free_list_.back();
      free_list_.pop_back();
    } else {
      // Reuse the LRU victim node at pool_[0].prev directly without freeing!
      u = pool_[0].prev;
      unlink(u);
      index_map_.erase(pool_[u].key);
    }

    pool_[u].key = key;
    pool_[u].value = value;
    push_mru_front(u);
    index_map_[key] = u;
  }
};