LFU 缓存 图解题解

这道题到底在问什么

容量

capacity = 2

操作序列

put(1,1) put(2,2) get(1) put(3,3) get(2) get(3) put(4,4) get(1) get(3) get(4)

返回

[ , , 1, , -1, 3, , -1, 3, 4]

最优解：一步一步想明白

1. 3如果每次淘汰都从头扫一遍找「频次最小」的键,缓存一大就慢成一团。我们要的是O(1) 直接拿到该淘汰谁。
2. 4三张表配合:① 键→值 ② 键→频次 ③ 频次→该频次的键队列(LRU 顺序)。再加一个 minFreq。这样取「该淘汰谁」永远是 O(1)。
3. 5接下来上排格子代表容量为 2 的两个槽,格子里写键;下方哈希表是频次桶。盯住 minFreq 和桶里的排队顺序。
4. 6新键 freq=1 · minFreq=1放入新键 1,值 1。新键频次从 1 起步,丢进 freq 1 桶。当前只有它,minFreq = 1。另一个槽还空着(灰)。
5. 7再来个 freq=1 · 排它后面再放键 2,频次也是 1,排进 freq 1 桶,排在 1 的后面(它更新)。两个槽都满了。
6. 8命中!准备给频次 +1get(1):键 1 在缓存里,返回它的值 1。但访问算一次使用,接下来要把它的频次 +1。
7. 9键1 离开 freq1 桶键 1 升级:从 freq 1 桶移出,放进新的 freq 2 桶。freq1 桶现在只剩键 2。
8. 10freq1 桶非空 → minFreq 不动要不要更新 minFreq?freq1 桶还有键 2,所以 minFreq 仍然是 1。记住:只有最小桶被搬空时 minFreq 才上移。
9. 11要淘汰 → 看 minFreq 桶put(3,3):缓存已满,得先淘汰。看 minFreq = 1 桶,取它的队头(最久未用)—— 正是键 2。
10. 12键2 出局,槽位空出键 2 被淘汰出局,腾出一个槽。freq1 桶被搬空了,整桶删掉。现在最低频次的桶是 freq2。
11. 13新键 freq=1 · minFreq 重置 1放入新键 3,频次从 1 起步,进 freq1 桶。关键:任何新键都让 minFreq 立刻重置为 1(因为它就是最低频)。
12. 14已被淘汰 · 返回 -1get(2):键 2 刚被淘汰了,缓存里找不到 → 返回 -1。这一步什么都不改。
13. 15命中!返回值 3get(3):命中,返回值 3。和 get(1) 一样,接下来给它频次 +1。
14. 16freq1 桶被搬空!键 3 从 freq1 移到 freq2 桶,排在键 1 后面(3 更新)。这下 freq1 桶空了,而且它正是 minFreq 桶 → minFreq 上移到 2!
15. 17minFreq=2 桶里有俩 → 比谁久put(4,4):又满了。这次 minFreq = 2 桶里有两个键(1 和 3,频次都是 2)。频次平手,就看谁最久没碰 —— 队头是键 1(3 刚被 get 过)。
16. 18键1 出局(最久未用)淘汰队头键 1(它和键 3 频次都是 2,但更久没被访问)。freq2 桶现在只剩键 3。这一步就是 LFU 里藏的 LRU 规则。
17. 19新键 freq=1 · minFreq 重置 1放入新键 4,频次 1,进 freq1 桶,minFreq 又重置为 1。注意:键 3 还稳稳待在 freq2 桶里没动。
18. 20已被淘汰 · 返回 -1get(1):键 1 上一步被淘汰了 → 返回 -1。
19. 21命中 · 频次 2 → 3get(3):命中返回 值 3,频次升到 3,移到 freq3 桶。freq1 桶还有键 4,所以 minFreq 仍是 1。
20. 22命中 · 频次 1 → 2get(4):命中返回 值 4,频次升到 2,freq1 桶又被搬空 → minFreq 上移到 2。全程返回值依次是 1, -1, 3, -1, 3, 4。
21. 23返回序列 = 1,-1,3,-1,3,4整串操作走完,缓存里留下用得多的键 3 和键 4。get 的返回序列正是 1, -1, 3, -1, 3, 4 —— 和官方答案一致。
22. 24满了 · minFreq=2 桶 = [4]再加一手 put(5,5) 看个反直觉点:虽然键 4 是最近才 get 过的,但它频次(2)比键 3(3)低 —— LFU 先看频次,所以照样淘汰键 4。
23. 25频次低者先走 · minFreq=1键 4 被淘汰,键 5 入桶 freq1,minFreq 重置为 1。频次最高的键 3 反而留了下来 —— 这正是 LFU 和 LRU 的本质区别:LRU 会保留最近用的键 4,LFU 保留用得最多的键 3。
24. 29minFreq 卡在 2 → 淘汰错键假如插入新键 4(频次 1)后没把 minFreq 重置为 1,minFreq 还停在 2。下次淘汰就会从 freq2 桶踢掉频次更高的键 3 —— 把用得多的反而淘汰了,大错。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import defaultdict, OrderedDict
class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.minFreq = 0
        self.kv = {}                     # key -> value
        self.kf = {}                     # key -> freq
        self.fk = defaultdict(OrderedDict)  # freq -> {key: None}
    def _touch(self, key):                # 频次 +1,挪桶
        f = self.kf[key]
        del self.fk[f][key]
        if not self.fk[f]:
            del self.fk[f]
            if self.minFreq == f: self.minFreq += 1
        self.kf[key] = f + 1
        self.fk[f + 1][key] = None
    def get(self, key):
        if key not in self.kv: return -1
        self._touch(key)
        return self.kv[key]
    def put(self, key, value):
        if self.cap == 0: return
        if key in self.kv:
            self.kv[key] = value; self._touch(key); return
        if len(self.kv) >= self.cap:                  # 淘汰
            old, _ = self.fk[self.minFreq].popitem(last=False)
            del self.kv[old]; del self.kf[old]
        self.kv[key] = value; self.kf[key] = 1
        self.fk[1][key] = None; self.minFreq = 1

#include <unordered_map>
#include <list>
using namespace std;
class LFUCache {
    int cap, minFreq;
    unordered_map<int,int> kv, kf;            // key->val, key->freq
    unordered_map<int,list<int>> fk;          // freq->keys(LRU)
    unordered_map<int,list<int>::iterator> it; // key->位置
    void touch(int key) {
        int f = kf[key];
        fk[f].erase(it[key]);
        if (fk[f].empty()) { fk.erase(f); if (minFreq==f) minFreq++; }
        kf[key] = f + 1;
        fk[f+1].push_back(key); it[key] = --fk[f+1].end();
    }
public:
    LFUCache(int capacity): cap(capacity), minFreq(0) {}
    int get(int key) {
        if (kv.find(key) == kv.end()) return -1;
        touch(key); return kv[key];
    }
    void put(int key, int value) {
        if (cap == 0) return;
        if (kv.find(key) != kv.end()) { kv[key]=value; touch(key); return; }
        if ((int)kv.size() >= cap) {                 // 淘汰
            int old = fk[minFreq].front(); fk[minFreq].pop_front();
            kv.erase(old); kf.erase(old); it.erase(old);
        }
        kv[key]=value; kf[key]=1;
        fk[1].push_back(key); it[key]=--fk[1].end(); minFreq=1;
    }
};

import java.util.HashMap;
import java.util.LinkedHashSet;
class LFUCache {
    private int cap;
    private int minFreq;
    private HashMap<Integer, Integer> kv = new HashMap<Integer, Integer>();
    private HashMap<Integer, Integer> kf = new HashMap<Integer, Integer>();
    private HashMap<Integer, LinkedHashSet<Integer>> fk =
        new HashMap<Integer, LinkedHashSet<Integer>>();   // freq->keys(LRU)
    public LFUCache(int capacity) { this.cap = capacity; this.minFreq = 0; }
    private void touch(int key) {                    // 频次 +1,挪桶
        int f = kf.get(key);
        fk.get(f).remove(key);
        if (fk.get(f).isEmpty()) { fk.remove(f); if (minFreq == f) minFreq++; }
        kf.put(key, f + 1);
        fk.computeIfAbsent(f + 1, k -> new LinkedHashSet<Integer>()).add(key);
    }
    public int get(int key) {
        if (!kv.containsKey(key)) return -1;
        touch(key);
        return kv.get(key);
    }
    public void put(int key, int value) {
        if (cap == 0) return;
        if (kv.containsKey(key)) { kv.put(key, value); touch(key); return; }
        if (kv.size() >= cap) {                       // 淘汰
            int old = fk.get(minFreq).iterator().next();
            fk.get(minFreq).remove(old); kv.remove(old); kf.remove(old);
        }
        kv.put(key, value); kf.put(key, 1);
        fk.computeIfAbsent(1, k -> new LinkedHashSet<Integer>()).add(key);
        minFreq = 1;
    }
}

复杂度

面试官可能追问