Definition
- LFU – Least Frequently Used eviction policy that removes the entry accessed the fewest times when the cache is full.
- O(1) structure – a
HashMapfor lookup, aHashMapmapping frequency to a list of nodes, and aminFreqinteger. - Promotion – on access, a node moves from its current frequency list to the next, maintaining O(1) via doubly linked list removal.
- Frequency decay – periodically halves all frequencies so old popularity ages out and does not dominate forever.
- TTL – a per-entry expiry timestamp; expired entries are treated as cache misses on access.
Think of National Bank of India caching account balances to avoid database hits. The LFU cache keeps the most-requested balances. When full, it evicts the balance asked for the fewest times. Decay is like saying popularity from last month should not count forever. TTL is the rule that a cached balance is only trusted for thirty seconds before it must be refreshed from the ledger.
Understanding the Concepts
What is an LFU cache?
An LFU (Least Frequently Used) cache evicts the entry with the lowest access frequency when the cache is full. Unlike LRU, which evicts the least recently used, LFU keeps entries that are accessed most often, which works well when access patterns are stable.
How do you achieve O(1) get and put?
The trick is three data structures working together:
- A
HashMapfor O(1) key lookup. - A
HashMapmapping each frequency to the list of all nodes at that frequency. - An integer
minFreqtracking the smallest frequency present.
The doubly linked list per frequency allows O(1) removal from the middle (each node holds pointers to its neighbors) and O(1) addition to the head. Within the same frequency, nodes are ordered by recency.
package com.bank.cache;
import java.util.HashMap;
import java.util.Map;
public class LFUCache<K, V> {
private final int capacity;
private int minFreq;
private final Map<K, Node<K, V>> keyMap;
private final Map<Integer, DoublyLinkedList<K, V>> freqMap;
public LFUCache(int capacity) {
this.capacity = capacity;
this.minFreq = 0;
this.keyMap = new HashMap<>();
this.freqMap = new HashMap<>();
}
static class Node<K, V> {
K key;
V value;
int freq;
Node<K, V> prev, next;
Node(K key, V value) {
this.key = key;
this.value = value;
this.freq = 1;
}
}
static class DoublyLinkedList<K, V> {
Node<K, V> head, tail;
int size;
DoublyLinkedList() {
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
size = 0;
}
void addFirst(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
size++;
}
void remove(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
Node<K, V> removeLast() {
if (size == 0) return null;
Node<K, V> last = tail.prev;
remove(last);
return last;
}
}
public V get(K key) {
Node<K, V> node = keyMap.get(key);
if (node == null) return null;
promote(node);
return node.value;
}
public void put(K key, V value) {
if (capacity <= 0) return;
Node<K, V> node = keyMap.get(key);
if (node != null) {
node.value = value;
promote(node);
return;
}
if (keyMap.size() >= capacity) {
evict();
}
Node<K, V> newNode = new Node<>(key, value);
keyMap.put(key, newNode);
freqMap.computeIfAbsent(1, f -> new DoublyLinkedList<>())
.addFirst(newNode);
minFreq = 1;
}
private void promote(Node<K, V> node) {
int oldFreq = node.freq;
DoublyLinkedList<K, V> oldList = freqMap.get(oldFreq);
oldList.remove(node);
if (oldList.size == 0 && oldFreq == minFreq) {
minFreq++;
}
node.freq++;
freqMap.computeIfAbsent(node.freq, f -> new DoublyLinkedList<>())
.addFirst(node);
}
private void evict() {
DoublyLinkedList<K, V> minList = freqMap.get(minFreq);
Node<K, V> victim = minList.removeLast();
if (victim != null) {
keyMap.remove(victim.key);
}
}
}
How does get work step by step?
On get(key), if the key is missing you return null (cache miss). If present, you read the value and promote the node: remove it from its current frequency list, increment its frequency, and add it to the head of the next frequency list. If the old list is now empty and was at minFreq, increment minFreq.
package com.bank.service;
import com.bank.cache.LFUCache;
import java.math.BigDecimal;
public class CacheDemo {
public static void main(String[] args) {
LFUCache<String, BigDecimal> cache = new LFUCache<>(3);
cache.put("RAJESH-001", new BigDecimal("50000.00"));
cache.put("PRIYA-002", new BigDecimal("75000.00"));
cache.put("PANKAJ-003", new BigDecimal("100000.00"));
// Access Rajesh twice: frequency becomes 3
cache.get("RAJESH-001");
cache.get("RAJESH-001");
// Access Priya once: frequency becomes 2
cache.get("PRIYA-002");
// Put a new key: Pankaj (freq 1) is evicted (least frequent)
cache.put("NEHA-004", new BigDecimal("25000.00"));
System.out.println("Pankaj: " + cache.get("PANKAJ-003")); // null
System.out.println("Rajesh: " + cache.get("RAJESH-001")); // 50000.00
}
}
Pankaj: null
Rajesh: 50000.00
How does put work step by step?
On put(key, value), if the key exists, update the value and promote. If the key is new and the cache is at capacity, evict: go to the list at minFreq, remove its tail (least recent among least frequent), and delete it from the key map. Then insert the new node with frequency 1 and set minFreq to 1.
What is frequency decay and why does it matter?
Pure LFU suffers from cache pollution. A key that was extremely hot long ago keeps a high frequency count and never leaves, even though it is no longer accessed. Frequency decay periodically ages old counts.
A common approach is to halve every node's frequency periodically, or use a time-aware counter where recent accesses weigh more. Caffeine uses a frequency sketch with periodic aging.
public void decayAll() {
// Halve all frequencies periodically
for (Node<K, V> node : keyMap.values()) {
int oldFreq = node.freq;
DoublyLinkedList<K, V> oldList = freqMap.get(oldFreq);
if (oldList != null) oldList.remove(node);
node.freq = Math.max(1, node.freq / 2);
freqMap.computeIfAbsent(node.freq, f -> new DoublyLinkedList<>())
.addFirst(node);
}
// Recompute minFreq
minFreq = keyMap.values().stream()
.mapToInt(n -> n.freq).min().orElse(0);
}
How do you add TTL to the cache?
Store an expiry timestamp on each node. On access, check whether the entry has expired. If expired, treat it as a cache miss and remove the node. An optional background sweeper removes expired entries proactively.
static class Node<K, V> {
K key;
V value;
int freq;
long expiresAt; // System.nanoTime() + TTL
Node<K, V> prev, next;
Node(K key, V value, long ttlNanos) {
this.key = key;
this.value = value;
this.freq = 1;
this.expiresAt = System.nanoTime() + ttlNanos;
}
boolean isExpired() {
return System.nanoTime() > expiresAt;
}
}
How does this compare to LRU?
| Feature | LRU | LFU |
|---------|-----|-----|
| Eviction basis | Least recently used | Least frequently used |
| Strength | Adapts to shifting access patterns | Keeps genuinely popular entries |
| Weakness | One-time scan evicts hot entries | Old hot entries never leave (without decay) |
| Complexity | O(1) with HashMap + one DLL | O(1) with HashMap + frequency-bucketed DLLs |
| Production cache | LinkedHashMap, Guava | Caffeine (Window-TinyLFU hybrid) |
What about thread safety in a banking service?
The promote and evict operations are multi-step and not atomic. In a concurrent service, guard the structure with a lock or use a proven concurrent cache library.
package com.bank.cache;
import java.math.BigDecimal;
import com.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.Cache;
import java.time.Duration;
public class ProductionCache {
// Caffeine: Window-TinyLFU with frequency sketch + periodic aging
private static final Cache<String, BigDecimal> BALANCE_CACHE =
Caffeine.newBuilder()
.maximumSize(10_000)
.expireAfterWrite(Duration.ofSeconds(30))
.build();
public static BigDecimal getBalance(String accountId) {
return BALANCE_CACHE.get(accountId,
id -> fetchFromDatabase(id));
}
private static BigDecimal fetchFromDatabase(String accountId) {
return new BigDecimal("50000.00"); // Simulated DB call
}
}
What should a senior engineer know?
Pure LFU suffers from cache pollution, which is why real caches like Caffeine use Window-TinyLFU, a hybrid of recency and frequency with a frequency sketch and periodic aging, giving better hit rates and bounded memory. In a concurrent banking service, always use a proven library rather than hand-rolling a cache with external locking.
Visual Overview
LFU Cache Structure: keyMap: HashMap<K, Node> ┌─────────┬──────────┐ │ RAJESH │ Node(f=3)│──▶ in freqMap[3] │ PRIYA │ Node(f=2)│──▶ in freqMap[2] │ NEHA │ Node(f=1)│──▶ in freqMap[1] └─────────┴──────────┘ freqMap: HashMap<Integer, DoublyLinkedList> ┌───┬──────────────────────────┐ │ 1 │ head ↔ NEHA ↔ tail │ ← minFreq = 1 │ 2 │ head ↔ PRIYA ↔ tail │ │ 3 │ head ↔ RAJESH ↔ tail │ └───┴──────────────────────────┘ Eviction: remove tail of freqMap[minFreq] Promotion: move node from freqMap[f] to freqMap[f+1]
Key Takeaway
An LFU cache evicts the least frequently used entry when full. Making get and put O(1) requires three structures: a HashMap from key to node for constant-time lookup, a HashMap from frequency to a doubly linked list of nodes at that frequency, and a tracked minFreq integer. The doubly linked list per frequency allows O(1) removal from the middle, and nodes within the same frequency are ordered by recency to break ties.
Pure LFU has a well-known flaw called cache pollution: a key that was hot long ago keeps a high count forever. Frequency decay fixes this by periodically halving counts so old popularity ages out. TTL adds a time-based expiry so cached data is never trusted beyond a fixed lifetime, which is essential in banking where balances change in the ledger.
In banking at National Bank of India, Pankaj used this to cache account balances. The LFU policy kept the most-requested balances hot, decay stopped a festival spike from pinning an account forever, and a thirty-second TTL guaranteed every cached balance was refreshed from the database. In production, Caffeine's Window-TinyLFU gives better hit rates than hand-rolled LFU because it combines recency and frequency with a frequency sketch.
Remember one sentence: O(1) LFU uses a key map, frequency-bucketed doubly linked lists, and a min-frequency tracker, and production caches add decay and TTL to prevent stale-popularity pollution.
---