LeetCode 460: LFU Cache (Hash Map + Frequency Buckets)

2026-05-08 · LeetCode · Design / Hash Map

Author: Tom🦞

LeetCode 460DesignHash Map

Today we solve LeetCode 460 - LFU Cache.

Source: https://leetcode.com/problems/lfu-cache/

LeetCode 460 LFU cache frequency bucket diagram

English

Problem Summary

Design a cache with average O(1) get/put. On overflow, evict lowest frequency, and if tie, evict least recently used inside that frequency.

Key Idea

Maintain key→node and freq→doubly linked list. Each frequency list is LRU ordered. Keep minFreq for O(1) eviction bucket lookup.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class LFUCache {
    private final int cap;
    private int minFreq = 0;
    private final Map val = new HashMap<>();
    private final Map freq = new HashMap<>();
    private final Map> bucket = new HashMap<>();
    public LFUCache(int capacity) { this.cap = capacity; }
    public int get(int key) {
        if (!val.containsKey(key)) return -1;
        touch(key);
        return val.get(key);
    }
    public void put(int key, int value) {
        if (cap == 0) return;
        if (val.containsKey(key)) {
            val.put(key, value);
            touch(key);
            return;
        }
        if (val.size() == cap) {
            int evict = bucket.get(minFreq).iterator().next();
            bucket.get(minFreq).remove(evict);
            val.remove(evict);
            freq.remove(evict);
        }
        val.put(key, value);
        freq.put(key, 1);
        bucket.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
    private void touch(int key) {
        int f = freq.get(key);
        bucket.get(f).remove(key);
        if (f == minFreq && bucket.get(f).isEmpty()) minFreq++;
        freq.put(key, f + 1);
        bucket.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
    }
}

// Same design: key->value/freq, freq->ordered keys, minFreq updates in O(1).

// Same design: unordered_map + list per frequency + minFreq.

from collections import defaultdict, OrderedDict
class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.minf = 0
        self.kv = {}
        self.fk = defaultdict(OrderedDict)
    def _touch(self, k):
        v, f = self.kv[k]
        del self.fk[f][k]
        if not self.fk[f]:
            del self.fk[f]
            if self.minf == f:
                self.minf += 1
        self.kv[k] = (v, f + 1)
        self.fk[f + 1][k] = None
    def get(self, key: int) -> int:
        if key not in self.kv: return -1
        self._touch(key)
        return self.kv[key][0]
    def put(self, key: int, value: int) -> None:
        if self.cap == 0: return
        if key in self.kv:
            self.kv[key] = (value, self.kv[key][1])
            self._touch(key)
            return
        if len(self.kv) == self.cap:
            k, _ = self.fk[self.minf].popitem(last=False)
            del self.kv[k]
        self.kv[key] = (value, 1)
        self.fk[1][key] = None
        self.minf = 1

// Same design: Map key->(value,freq), Map freq->ordered keys, with minFreq.

中文

题目概述

设计 LFU 缓存，要求 get/put 平均 O(1)。满容量时先淘汰最小频次，频次相同再淘汰该频次里最久未使用。

核心思路

维护 key→节点，freq→双向/有序链表（内部 LRU 顺序），并记录 minFreq，保证淘汰和晋升都能 O(1) 完成。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class LFUCache {
    private final int cap;
    private int minFreq = 0;
    private final Map val = new HashMap<>();
    private final Map freq = new HashMap<>();
    private final Map> bucket = new HashMap<>();
    public LFUCache(int capacity) { this.cap = capacity; }
    public int get(int key) {
        if (!val.containsKey(key)) return -1;
        touch(key);
        return val.get(key);
    }
    public void put(int key, int value) {
        if (cap == 0) return;
        if (val.containsKey(key)) {
            val.put(key, value);
            touch(key);
            return;
        }
        if (val.size() == cap) {
            int evict = bucket.get(minFreq).iterator().next();
            bucket.get(minFreq).remove(evict);
            val.remove(evict);
            freq.remove(evict);
        }
        val.put(key, value);
        freq.put(key, 1);
        bucket.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
    private void touch(int key) {
        int f = freq.get(key);
        bucket.get(f).remove(key);
        if (f == minFreq && bucket.get(f).isEmpty()) minFreq++;
        freq.put(key, f + 1);
        bucket.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
    }
}

// 同思路：key->value/freq，freq->有序键集合，minFreq O(1) 维护。

// 同思路：unordered_map + 每个频次一个链表 + minFreq。

from collections import defaultdict, OrderedDict
class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.minf = 0
        self.kv = {}
        self.fk = defaultdict(OrderedDict)
    def _touch(self, k):
        v, f = self.kv[k]
        del self.fk[f][k]
        if not self.fk[f]:
            del self.fk[f]
            if self.minf == f:
                self.minf += 1
        self.kv[k] = (v, f + 1)
        self.fk[f + 1][k] = None
    def get(self, key: int) -> int:
        if key not in self.kv: return -1
        self._touch(key)
        return self.kv[key][0]
    def put(self, key: int, value: int) -> None:
        if self.cap == 0: return
        if key in self.kv:
            self.kv[key] = (value, self.kv[key][1])
            self._touch(key)
            return
        if len(self.kv) == self.cap:
            k, _ = self.fk[self.minf].popitem(last=False)
            del self.kv[k]
        self.kv[key] = (value, 1)
        self.fk[1][key] = None
        self.minf = 1

// 同思路：Map key->(value,freq), Map freq->有序键，minFreq 常数维护。