CoreConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

LFU Cache

Evicts the cache entry with the lowest access frequency count, breaking ties by least-recently-used order in O(1) time via frequency-keyed doubly linked lists.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Data Structures
Difficulty: Intermediate
Family: Cache Eviction & Indexing
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 1
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: Least Frequently Used Cache, O(1) Frequency-Bucket Cache, Window-TinyLFU Eviction

Overview

An LFU (Least Frequently Used) Cache tracks how many times each cached key has been accessed. By grouping keys of identical access frequency into doubly linked lists and tracking minFreq, get, put, and eviction all run in O(1) worst-case time while protecting consistently popular hot keys from one-off scan bursts.

Core Concepts

access frequency counterfrequency bucket listsminFreq pointerLRU tie-breaking

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(C)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for LFU Cache across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(1)

11 ns

Sub-microsecond~4

Est. Worst-Case TimeO(1)

11 ns

Sub-microsecond~4

Est. Working MemoryO(C)

1.53 MB

Standard Heap FitN=100,000

When to Use

Use LFU Cache when access popularity follows a stable power-law or Zipfian distribution and you want popular items kept in cache even during bursty sequential scans.
Use it when evicting by access frequency yields a higher hit ratio than pure recency (LRU).

When Not to Use

Avoid pure un-aged LFU when workload popularity shifts abruptly over time, because old high-frequency items can linger ('cache pollution') without frequency aging or ARC/W-TinyLFU decay.

What It Does

Maintains access frequency counts per cached key in O(1) time
Evicts the least frequently accessed item when capacity is full (breaking ties by LRU)

Use Cases

Caching skewed power-law / Zipfian workloads such as CDN assets, DNS records, and product catalog pages
Protecting hot long-term cache keys from being flushed by a sequential scan
Database buffer pool and key-value store frequency-aware eviction

Inputs

Cache capacity C and stream of get(key) / put(key, value) operations

Outputs

Cached value on hit or -1/null on miss, with automatic O(1) LFU eviction

Key Formulas (1)

Minimum Frequency Invariant

minFreq = min_{k in cache} freq(k), reset to 1 on new insertion

minFreq = min_{k in cache} freq(k), reset to 1 on new insertion

Tracks the lowest non-empty frequency bucket in O(1) time without scanning.

Pseudocode

1.Maintain keyMap: key -> (value, freq, listNode), freqMap: freq -> DoublyLinkedList, and minFreq = 0
2.On get(key): if key not in keyMap, return -1; move node from freqMap[freq] to freqMap[freq + 1]; if freqMap[minFreq] is empty, increment minFreq; return value
3.On put(key, val): if key in keyMap, update value and increment freq as in get(key)
4.Else if size == capacity: pop LRU tail from freqMap[minFreq] and remove from keyMap
5.Insert new node with freq = 1 into freqMap[1],keyMap and set minFreq = 1

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Maintain keyMap: key -> (value, freq, listNode), freqMap: freq -> DoublyLinkedList, and minFreq = 0
On get(key): if key not in keyMap, return -1; move node from freqMap[freq] to freqMap[freq + 1]; if freqMap[minFreq] is empty, increment minFreq; return value
On put(key, val): if key in keyMap, update value and increment freq as in get(key)
Else if size == capacity: pop LRU tail from freqMap[minFreq] and remove from keyMap
Insert new node with freq = 1 into freqMap[1],keyMap and set minFreq = 1

Canonical Example

Input: Capacity = 2: put(1,A), put(2,B), get(1), get(1), put(3,C)
Output: Evicts key 2 (freq=1 < key 1's freq=3); cache holds {1: A, 3: C}
Explanation: Key 1 was accessed 3 times while Key 2 had frequency 1, so inserting Key 3 evicts the lowest-frequency entry (Key 2).

Implementation Notes

Maintain keyToNode map, freqToList map of doubly linked lists, and an integer minFreq.

Common Pitfalls

Using a min-heap for frequency ordering (which costs O(log C) per access) instead of frequency-bucketed doubly linked lists with a minFreq integer.
Forgetting to reset minFreq = 1 when inserting a brand-new key after evicting.