LFU Cache: HashMap plus frequency map plus LinkedHashSet buckets

• LFU Cache – a fixed-capacity key-value store that evicts the entry with the lowest access count when full.
• Tie-breaking – among entries with equal frequency, the least recently used (oldest) is evicted first.
• Key-to-node map – maps each key to its value and current frequency for O(1) lookup.
• Frequency-to-bucket map – maps each frequency to a LinkedHashSet of keys at that frequency; insertion order gives LRU tie-breaking.
• Minimum frequency – a single integer tracking the current lowest frequency for O(1) eviction.
• All O(1) – every get and put operation runs in constant time.

What is an LFU Cache?

LFU (Least Frequently Used) is a cache eviction policy that removes the entry accessed the fewest times when the cache is full. Unlike LRU, which only considers recency, LFU considers total usage count. A consistently popular entry survives even if it has not been touched in the last few moments, as long as its total count is high.

package com.bank.cache;

public interface Cache<K, V> {
    V get(K key);
    void put(K key, V value);
}

How is LFU different from LRU?

LRU evicts the least recently used entry. LFU evicts the least frequently used entry. The difference matters when a popular entry is briefly idle: LRU would evict it, but LFU keeps it because its total access count is high.

| Feature | LRU | LFU |
|---|---|---|
| Eviction criterion | Least recently used | Lowest access count |
| Tie-breaking | Natural (insertion order) | LRU among equal frequency |
| Data structures | HashMap + doubly linked list | HashMap + freq map + LinkedHashSet |
| Advantage | Simple, good for recency | Keeps consistently popular entries |

What three data structures does the O(1) LFU use?

The O(1) design uses three structures working together.

1. keyMap: Map mapping each key to [value, frequency] for O(1) lookup and update.
2. freqMap: Map> mapping each frequency to the set of keys at that frequency. LinkedHashSet preserves insertion order for LRU tie-breaking.
3. minFreq: a single int tracking the current minimum frequency so eviction knows which bucket to access.

package com.bank.cache;

import java.util.*;

public class LFUCache {
    private final int capacity;
    private int minFreq;
    private final Map<Integer, int[]> keyMap;        // key -> [value, freq]
    private final Map<Integer, LinkedHashSet<Integer>> freqMap; // freq -> keys

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
    }
}

How does get work?

On get(key), if the key is absent, return -1 (cache miss). If present, read the value, then promote its frequency: remove the key from its current frequency bucket, increment the frequency in keyMap, and add it to the next frequency bucket. If the old bucket was the minFreq bucket and is now empty, increment minFreq.

public int get(int key) {
    if (!keyMap.containsKey(key)) return -1;
    int[] node = keyMap.get(key);
    int value = node[0];
    int freq = node[1];

    // Remove from current frequency bucket
    freqMap.get(freq).remove(key);
    if (freqMap.get(freq).isEmpty()) {
        freqMap.remove(freq);
        if (minFreq == freq) minFreq++;
    }

    // Promote to next frequency
    node[1] = freq + 1;
    freqMap.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);

    return value;
}

How does put work?

On put(key, value), if the key already exists, update the value and promote its frequency (same as get). If the key is new and the cache is at capacity, evict: go to the minFreq bucket, remove the first key (oldest among least frequent), and delete it from keyMap. Then insert the new key with frequency 1, add it to the frequency-1 bucket, and reset minFreq to 1.

public void put(int key, int value) {
    if (capacity <= 0) return;

    if (keyMap.containsKey(key)) {
        keyMap.get(key)[0] = value;
        get(key); // promote frequency
        return;
    }

    // Evict if at capacity
    if (keyMap.size() >= capacity) {
        LinkedHashSet<Integer> minBucket = freqMap.get(minFreq);
        int evictKey = minBucket.iterator().next(); // oldest in bucket
        minBucket.remove(evictKey);
        if (minBucket.isEmpty()) freqMap.remove(minFreq);
        keyMap.remove(evictKey);
    }

    // Insert new key at frequency 1
    keyMap.put(key, new int[]{value, 1});
    freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
    minFreq = 1; // new key always starts at freq 1
}

Why does minFreq reset to 1 on every new insertion?

A brand-new key has frequency 1, which is the smallest possible frequency. No existing key can have a frequency lower than 1. So after inserting a new key, the minimum frequency in the cache is guaranteed to be 1, regardless of what it was before.

// After inserting a new key:
minFreq = 1;
// Correct because the new key has freq=1
// and 1 is the smallest possible frequency

Why LinkedHashSet and not plain HashSet?

LinkedHashSet preserves insertion order, which gives deterministic LRU tie-breaking for free. When two keys have the same frequency, the one inserted into the bucket first (the older one) appears first in iteration order, so iterator().next() returns the oldest key. A plain HashSet has no ordering guarantee, making tie-breaking non-deterministic.

// LinkedHashSet: insertion order preserved
LinkedHashSet<Integer> bucket = new LinkedHashSet<>();
bucket.add(101);  // first
bucket.add(202);  // second
bucket.iterator().next(); // 101 (oldest, deterministic)

// Plain HashSet: no order guarantee
HashSet<Integer> plain = new HashSet<>();
plain.add(101);
plain.add(202);
plain.iterator().next(); // unpredictable

What are edge cases?

Edge cases include capacity zero (never store anything), put on an existing key (update value and promote), and get on a missing key (return -1). The eviction path must handle the case where minFreq bucket becomes empty after eviction.

LFUCache cache = new LFUCache(2);
cache.put(1, 100);   // freq=1
cache.put(2, 200);   // freq=1
cache.get(1);        // freq of key 1 becomes 2
cache.put(3, 300);   // evicts key 2 (freq=1, oldest)
cache.get(2);        // -1 (evicted)

What should a senior engineer know?

A senior engineer explains why all three structures are needed for O(1) operations, contrasts LFU with LRU (which needs only two structures), and notes that LFU can suffer from cache pollution: an entry that was popular in the past but is now cold stays resident because of its high count. Some implementations add frequency decay to address this.