Introduction to LFU Cache
The Least Frequently Used (LFU) cache is an eviction policy that removes the least-accessed items first when the cache reaches its capacity. Unlike LRU (Least Recently Used), which only considers recency, LFU tracks how often each item is accessed and evicts the one with the lowest frequency count. When multiple items share the same lowest frequency, LFU typically evicts the least recently used among them.
This tutorial walks you through implementing an LFU cache in JavaScript from scratch, covering the underlying data structures, the algorithm, edge cases, and best practices. By the end, you'll have a production-ready implementation and a clear understanding of how it works.
What Is an LFU Cache?
An LFU cache is a key-value store with a fixed capacity. Every time a key is accessed—either through a get or put operation—its frequency counter increments. When the cache is full and a new item must be inserted, the item with the smallest frequency is evicted. If there's a tie, the least recently accessed item among those is removed.
The two core operations are:
get(key)— Returns the value associated with the key (or -1/undefined if not present) and increments its frequency.put(key, value)— Inserts or updates the key-value pair. If the cache is at capacity and the key is new, evicts the LFU item first.
The challenge is making both operations run in O(1) time. A naive approach—scanning all entries to find the minimum frequency—would be O(n), which is too slow for high-throughput systems.
Why LFU Matters
LFU is particularly useful in scenarios where access patterns are skewed—some items are accessed far more often than others. Examples include:
- Database query caching — Frequently executed queries stay cached longer.
- CDN content caching — Popular assets remain available while cold content is evicted.
- API response caching — Heavily used endpoints benefit from persistent caching.
- Browser resource caching — Scripts and stylesheets accessed repeatedly are retained.
Compared to LRU, LFU is better at keeping genuinely popular items in cache, even if they weren't accessed recently. However, LFU can suffer from "cache pollution"—items that were popular in the past but no longer accessed can linger. Many production systems use hybrid policies like LFU with aging or W-TinyLFU to address this.
Data Structures for O(1) Operations
To achieve constant-time get and put, we combine three data structures:
- Key-node map — A
Mapfrom key to node, giving O(1) lookup. - Frequency map — A
Mapfrom frequency integer to a doubly linked list of nodes with that frequency. The linked list maintains insertion/access order, so the head is the least recently used within that frequency. - Minimum frequency tracker — An integer tracking the current minimum frequency, so we know which list to evict from without scanning.
Each node stores the key, value, and its current frequency. The doubly linked list lets us remove a node in O(1) when we need to move it to a higher-frequency list.
The Node and Doubly Linked List
First, let's define a node and a minimal doubly linked list with O(1) insertion at the tail and O(1) removal of any node.
class Node {
constructor(key, value, freq = 1) {
this.key = key;
this.value = value;
this.freq = freq;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
// Sentinel head and tail simplify edge cases
this.head = new Node(null, null, 0);
this.tail = new Node(null, null, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
this.size = 0;
}
// Insert a node at the tail (most recently used position)
append(node) {
const prev = this.tail.prev;
prev.next = node;
node.prev = prev;
node.next = this.tail;
this.tail.prev = node;
this.size++;
}
// Remove a specific node from the list
remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
this.size--;
}
// Remove and return the head node (least recently used in this frequency)
popHead() {
if (this.size === 0) return null;
const node = this.head.next;
this.remove(node);
return node;
}
}
Implementing the LFU Cache
Now we combine the structures into the LFUCache class. The key insight is that whenever a node's frequency increases, we move it from its current frequency list to the next frequency's list, appending it at the tail (making it the most recently used within that new frequency).
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.minFreq = 0;
this.keyMap = new Map(); // key -> Node
this.freqMap = new Map(); // freq -> DoublyLinkedList
}
_getFreqList(freq) {
if (!this.freqMap.has(freq)) {
this.freqMap.set(freq, new DoublyLinkedList());
}
return this.freqMap.get(freq);
}
get(key) {
if (!this.keyMap.has(key)) return -1;
const node = this.keyMap.get(key);
this._increaseFreq(node);
return node.value;
}
put(key, value) {
if (this.capacity <= 0) return;
// If key exists, update value and bump frequency
if (this.keyMap.has(key)) {
const node = this.keyMap.get(key);
node.value = value;
this._increaseFreq(node);
return;
}
// Evict if at capacity
if (this.keyMap.size >= this.capacity) {
const minList = this.freqMap.get(this.minFreq);
const evicted = minList.popHead();
this.keyMap.delete(evicted.key);
}
// Insert new node with frequency 1
const node = new Node(key, value, 1);
this.keyMap.set(key, node);
this._getFreqList(1).append(node);
this.minFreq = 1;
}
_increaseFreq(node) {
const oldFreq = node.freq;
const oldList = this.freqMap.get(oldFreq);
oldList.remove(node);
// If we emptied the min frequency list, bump minFreq
if (oldList.size === 0 && this.minFreq === oldFreq) {
this.minFreq++;
this.freqMap.delete(oldFreq);
}
node.freq = oldFreq + 1;
this._getFreqList(node.freq).append(node);
}
}
How the Algorithm Works
Let's trace through an example to see the mechanics:
const cache = new LFUCache(2);
cache.put(1, 10); // cache: {1: freq=1}
cache.put(2, 20); // cache: {1: freq=1, 2: freq=1}, minFreq=1
console.log(cache.get(1)); // returns 10, key 1 freq -> 2
// cache: {2: freq=1, 1: freq=2}, minFreq=1
cache.put(3, 30); // capacity full, evict LFU (key 2, freq=1)
// cache: {1: freq=2, 3: freq=1}, minFreq=1
console.log(cache.get(2)); // returns -1 (evicted)
console.log(cache.get(3)); // returns 30, key 3 freq -> 2
// cache: {1: freq=2, 3: freq=2}, minFreq=2
cache.put(4, 40); // capacity full, evict LFU. Both freq=2,
// evict LRU among them -> key 1
// cache: {3: freq=2, 4: freq=1}, minFreq=1
console.log(cache.get(1)); // returns -1 (evicted)
console.log(cache.get(3)); // returns 30
console.log(cache.get(4)); // returns 40
Notice how when both keys 1 and 3 had frequency 2, the put(4, 40) operation evicted key 1 because it was the least recently used within the frequency-2 list (key 3 was accessed more recently via get(3)).
Testing the Implementation
Thorough testing is essential for cache implementations. Here's a test suite covering common scenarios:
function runTests() {
// Test 1: Basic get and put
let cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.assert(cache.get(1) === 1, "Test 1.1 failed");
cache.put(3, 3); // evicts key 2
console.assert(cache.get(2) === -1, "Test 1.2 failed");
console.assert(cache.get(3) === 3, "Test 1.3 failed");
// Test 2: Update existing key
cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.put(1, 10); // update, freq of key 1 becomes 2
cache.put(3, 3); // evicts key 2 (freq=1)
console.assert(cache.get(1) === 10, "Test 2.1 failed");
console.assert(cache.get(2) === -1, "Test 2.2 failed");
// Test 3: Zero capacity
cache = new LFUCache(0);
cache.put(1, 1);
console.assert(cache.get(1) === -1, "Test 3.1 failed");
// Test 4: Tie-breaking by recency
cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);
cache.get(2);
cache.get(1); // key 1 freq=3, key 2 freq=2
cache.put(3, 3); // evicts key 2 (lower freq)
console.assert(cache.get(1) === 1, "Test 4.1 failed");
console.assert(cache.get(2) === -1, "Test 4.2 failed");
console.assert(cache.get(3) === 3, "Test 4.3 failed");
// Test 5: Single capacity
cache = new LFUCache(1);
cache.put(1, 1);
cache.put(2, 2); // evicts key 1
console.assert(cache.get(1) === -1, "Test 5.1 failed");
console.assert(cache.get(2) === 2, "Test 5.2 failed");
console.log("All tests passed!");
}
runTests();
Best Practices
Handle Edge Cases Explicitly
Always guard against zero or negative capacity, as shown in the put method. Also consider what happens when get is called on an empty cache—it should return a sentinel value like -1 or undefined, never throw.
Choose the Right Eviction Policy
LFU isn't always the best choice. If your workload has temporal locality (recently accessed items are likely to be accessed again soon) but no long-term popularity skew, LRU may perform better. For mixed workloads, consider hybrid policies. Benchmark with your actual access patterns before committing.
Consider Memory Overhead
The frequency map and linked lists add memory overhead per entry. For very large caches, this matters. If memory is tight, you might use a simpler O(log n) approach with a priority queue, or an approximate LFU that uses sampling.
Add TTL Support for Real-World Use
In production, entries often need time-to-live (TTL) expiration. You can extend the node to store an expiration timestamp and check it during get. A background sweep or lazy expiration on access both work—lazy is simpler, active sweeps prevent memory leaks from stale entries.
class TTLNode extends Node {
constructor(key, value, freq, ttlMs) {
super(key, value, freq);
this.expiresAt = ttlMs ? Date.now() + ttlMs : Infinity;
}
isExpired() {
return Date.now() >= this.expiresAt;
}
}
// In LFUCache.get():
get(key) {
if (!this.keyMap.has(key)) return -1;
const node = this.keyMap.get(key);
if (node.isExpired()) {
this._removeNode(node);
return -1;
}
this._increaseFreq(node);
return node.value;
}
Make It Thread-Safe If Needed
JavaScript is single-threaded in the browser and in Node.js's main event loop, so the basic implementation is safe there. However, if you use worker threads or share the cache across async contexts with interleaved awaits, consider wrapping operations in a mutex or using a queue to serialize access.
Expose Metrics for Observability
For production caches, tracking hit rate, eviction count, and size helps tune capacity. Add counters and a method to retrieve stats:
class LFUCache {
constructor(capacity) {
// ... existing fields ...
this.hits = 0;
this.misses = 0;
this.evictions = 0;
}
get(key) {
if (!this.keyMap.has(key)) {
this.misses++;
return -1;
}
this.hits++;
const node = this.keyMap.get(key);
this._increaseFreq(node);
return node.value;
}
// In put(), when evicting:
// this.evictions++;
stats() {
const total = this.hits + this.misses;
return {
size: this.keyMap.size,
capacity: this.capacity,
hits: this.hits,
misses: this.misses,
evictions: this.evictions,
hitRate: total === 0 ? 0 : this.hits / total
};
}
}
Common Pitfalls
- Forgetting to update minFreq on eviction — When you insert a new key, always reset
minFreqto 1, since new entries start at frequency 1. - Not cleaning up empty frequency lists — Leaving empty lists in
freqMapcauses memory leaks and can break minFreq tracking. Always delete them when they become empty. - Breaking list invariants during removal — When moving a node between frequency lists, remove it from the old list before appending to the new one, and update its frequency after removal.
- Using arrays instead of linked lists — Removing from the middle of an array is O(n). Stick with doubly linked lists for O(1) removal.
Performance Analysis
The implementation above achieves the following complexity:
get(key)— O(1): Map lookup, O(1) list removal and append, O(1) minFreq update.put(key, value)— O(1): Same operations plus optional eviction, all O(1).- Space — O(n) where n is the capacity, storing one node per entry plus list overhead.
This matches the theoretical lower bound for cache operations. The constant factors are small because we use native Map and simple pointer manipulation.
Conclusion
Implementing an LFU cache in JavaScript with O(1) operations requires careful coordination between a key map, a frequency-to-list map, and a minimum frequency tracker. By using doubly linked lists to maintain recency order within each frequency bucket, we avoid scanning and keep both get and put constant time. The implementation handles tie-breaking naturally—when multiple items share the minimum frequency, the least recently used among them is evicted. With the additions of TTL support, metrics, and proper edge-case handling, this pattern forms a solid foundation for caching in real-world JavaScript applications. Whether you're optimizing database queries, API responses, or computed results, understanding LFU gives you a powerful tool for managing bounded memory while prioritizing the data your users actually need.