LFU Cache: Implementation and Time Complexity Analysis

What is an LFU Cache?

LFU (Least Frequently Used) is a cache eviction policy that removes the item with the lowest access frequency when the cache reaches its capacity limit. Unlike LRU (Least Recently Used), which only cares about recency, LFU tracks how often each cached item is requested. Items with higher frequency counts are retained, making LFU especially effective when access patterns exhibit strong frequency skew—some items are genuinely "hot" and deserve to stay in the cache long-term.

Why LFU Matters

In systems with stable, long-lived popularity distributions (e.g., CDN edge caches, database query caches, or recommendation engines), LFU prevents cache thrashing by protecting frequently used data from being evicted by a burst of one-time accesses. LRU can easily evict a heavily used item if it hasn't been accessed for a short window, whereas LFU retains it based on accumulated usage. This leads to higher hit ratios for workloads where "frequency beats recency".

However, LFU comes with trade-offs. It requires maintaining frequency counters, which adds memory overhead. It can also suffer from "cache pollution" if a previously popular item goes cold but its high frequency count keeps it in the cache indefinitely. Modern implementations often incorporate a decay mechanism or a time-windowed frequency to counter this.

How an LFU Cache Works

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

At its core, an LFU cache associates a frequency counter with each cached entry. Every get() or put() hit increases that counter. When the cache is full and a new item must be inserted, the eviction algorithm finds the item (or items) with the smallest frequency count and removes one of them. In case of a tie (multiple items share the minimum frequency), a secondary tie-breaker is needed—most commonly the least recently used item among those with the same frequency (LFU-LRU hybrid).

Time Complexity Challenges

A naive implementation might use a priority queue (min-heap) ordered by frequency, yielding O(log N) for both get and put due to heap updates. For high-throughput caching, we need O(1) operations. Achieving true O(1) for LFU is trickier than for LRU because frequency increments change the ordering across many buckets.

Implementing an LFU Cache with O(1) Operations

The classic O(1) design (used in LeetCode's LFU Cache problem) relies on three core components:

Frequency-to-Keys mapping: A map where each frequency points to a LinkedHashSet of keys that have that frequency. The linked nature preserves insertion order, giving us LRU ordering within the same frequency bucket at no extra cost.
Key-to-Node mapping: A map from key to its value and current frequency (or a node holding both).
Minimum frequency tracker: A variable minFreq that always points to the smallest non-empty frequency bucket. It is updated incrementally—never requiring a full scan.

Data Structures in Detail

Let's define the required maps and variables:

// Java example (pseudo-typed)
Map<Integer, LinkedHashSet<Integer>> freqKeys;   // freq -> set of keys (LRU order)
Map<Integer, Node> cache;                      // key -> (value, freq)
int minFreq;                                   // current minimum frequency among cached items
int capacity;                                  // max number of items

The Node can simply be a pair (value, frequency). Alternatively, we can store the frequency inside the cache map and avoid a separate node class. The implementation below uses a small inner class for clarity.

Algorithm Walkthrough

get(key)

If key is absent, return -1.
Get the node, record its current frequency f.
Remove the key from freqKeys.get(f).
If f == minFreq and the set at frequency f becomes empty, increment minFreq by 1 (because the next minimum frequency among remaining items must be f+1 or higher).
Add the key to freqKeys.get(f+1) (create the set if needed).
Update node frequency to f+1 and return its value.

put(key, value)

If key exists: update its value and then perform the same logic as get() to increment its frequency (reuse code).
If key does not exist:
- If cache size == capacity: evict the least frequently used item.
  - Obtain the LinkedHashSet for minFreq.
  - Remove and retrieve the first (least recently inserted) key from that set.
  - Delete that key from cache.
  - If the set becomes empty, do not immediately update minFreq here—we are about to insert a new item with frequency 1, so minFreq will be set to 1 shortly.
- Insert the new key with value, frequency = 1.
- Add key to freqKeys.get(1) (create if needed).
- Set minFreq = 1.

Time Complexity Analysis

Every operation consists of a handful of HashMap and LinkedHashSet operations, all of which are O(1) on average:

HashMap lookups/insertions – O(1).
LinkedHashSet add, remove, and iteration of first element – O(1) because it maintains a doubly linked list along with a hash set.
Minimum frequency update – O(1) because minFreq only increments when the bucket for that frequency becomes empty. It never requires scanning frequency buckets. The only scenario where it could theoretically jump multiple steps is if a bucket becomes empty due to eviction while inserting a new item, but the insertion then resets minFreq to 1, so no scan occurs.

Thus both get and put run in strictly O(1) time, independent of cache size, making this implementation highly efficient for production use.

Complete Code Example (Java)

Below is a production‑ready LFU cache implementation with O(1) operations. It uses LinkedHashSet to maintain insertion order for LRU tie-breaking and a minFreq variable to avoid scanning.

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

public class LFUCache {
    private final int capacity;
    private int minFreq;
    
    // key -> (value, frequency)
    private Map<Integer, Node> cache;
    // frequency -> set of keys (ordered by insertion = LRU within same frequency)
    private Map<Integer, LinkedHashSet<Integer>> freqKeys;
    
    private static class Node {
        int value;
        int freq;
        Node(int value, int freq) {
            this.value = value;
            this.freq = freq;
        }
    }
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        cache = new HashMap<>();
        freqKeys = new HashMap<>();
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        int oldFreq = node.freq;
        // remove key from current frequency set
        LinkedHashSet<Integer> oldSet = freqKeys.get(oldFreq);
        oldSet.remove(key);
        // if oldSet was the minFreq bucket and it's now empty, increment minFreq
        if (oldFreq == minFreq && oldSet.isEmpty()) {
            minFreq++;
        }
        // increase frequency
        int newFreq = oldFreq + 1;
        node.freq = newFreq;
        // add to new frequency set (create if absent)
        freqKeys.computeIfAbsent(newFreq, k -> new LinkedHashSet<>()).add(key);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) return;
        
        if (cache.containsKey(key)) {
            // update value and bump frequency (reuse get logic but without return)
            Node node = cache.get(key);
            node.value = value;
            // increment frequency (same as get)
            int oldFreq = node.freq;
            freqKeys.get(oldFreq).remove(key);
            if (oldFreq == minFreq && freqKeys.get(oldFreq).isEmpty()) {
                minFreq++;
            }
            int newFreq = oldFreq + 1;
            node.freq = newFreq;
            freqKeys.computeIfAbsent(newFreq, k -> new LinkedHashSet<>()).add(key);
        } else {
            // eviction needed if full
            if (cache.size() == capacity) {
                LinkedHashSet<Integer> minSet = freqKeys.get(minFreq);
                int evictKey = minSet.iterator().next(); // first inserted = LRU
                minSet.remove(evictKey);
                cache.remove(evictKey);
                // no need to update minFreq here; insertion below sets minFreq=1
            }
            // insert new node with frequency 1
            Node newNode = new Node(value, 1);
            cache.put(key, newNode);
            freqKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFreq = 1; // reset minimum frequency to 1 (new item always freq=1)
        }
    }
}

Note: For thread-safety, wrap the public methods in synchronized blocks or use concurrent data structures with atomic updates. For extremely high concurrency, consider a lock-free design or a proven library like Caffeine (which uses a modern W‑TinyLFU policy).

Best Practices and Considerations

Apply frequency decay – Pure LFU can retain items that were popular hours ago but are no longer relevant. Introduce a global aging factor (e.g., halve counters periodically, or use a logarithmic counter like Redis’s LFU implementation) to let cold items eventually fade out.
Monitor hit ratio – Track hits / (hits + misses). LFU excels when a small set of items dominates traffic. If your workload is mostly random, LRU may be simpler and just as effective.
Capacity tuning – LFU needs enough capacity to hold the “working set” of frequently used items. Too small a capacity can cause thrashing even among popular items.
Memory overhead – The frequency-to-keys map creates a LinkedHashSet per frequency bucket. For large frequency ranges, this can be heavy. Consider capping the maximum tracked frequency and using a probabilistic counter (HyperLogLog style) to reduce storage.
Eviction tie-breaking – The LRU tie-breaker is crucial to avoid starving newer items that happen to have the same low frequency. Ensure your LinkedHashSet (or equivalent) preserves insertion order correctly.
Integration with existing caches – Many frameworks (e.g., Guava Cache, Caffeine) offer LFU‑based or frequency‑augmented policies out of the box. Prefer these over building from scratch unless you have very specific requirements.

Conclusion

The LFU cache is a powerful eviction strategy for workloads where access frequency is a stronger signal than recency. By maintaining frequency counters and using a clever O(1) data structure—maps of LinkedHashSets and a rolling minFreq variable—you can achieve constant‑time operations suitable for high‑performance caching layers. Remember to account for frequency saturation and cold‑item retention through decay mechanisms. When applied correctly, LFU significantly boosts cache hit ratios, reduces backend load, and delivers consistent performance in frequency‑skewed environments.