LFU 缓存怎样做到 get 和 put 都是 O(1)？和 LRU 有什么区别？

简答

LFU 是“最不经常使用”：每个键记一个使用次数，缓存满了就淘汰次数最少的那个。LeetCode 460 还规定，次数相同时淘汰其中最久没被用过的，而且新插入的键次数从 1 开始，get 和 put 命中都让次数加 1。

难点在 O(1)。如果每次淘汰都去扫一遍找最小次数，就是 O(n)。常用的办法是按次数分组：一个 Map 记每个键的值和次数，另一个 Map 把次数映射到“这个次数下的所有键”，组内按使用先后排好；再用一个变量 minFreq 记住当前最小次数。淘汰时直接去 minFreq 那一组拿最早的键。

每次访问一个键，就把它从次数为 f 的组挪到 f+1 的组。如果 f 那组空了，而 f 正好是 minFreq，minFreq 就加 1。插入新键时 minFreq 直接重置为 1。在 JavaScript 里，组可以用 Set 表示，因为 Set 按插入顺序遍历，取第一个元素就是组里最久没用的。

和 LRU 比，LRU 只看“最近一次什么时候用的”，LFU 看“一共用了多少次”。LFU 更能保住长期热门的数据，但一个键曾经被访问很多次，后来不再用了，它的高次数也会让它一直留在缓存里，这是 LFU 的主要缺点。

先看 LRU 和 LFU 淘汰谁

LRU 的写法见《如何利用 Map 实现固定容量的 LRU 缓存？》，它只需要一条按最近使用排序的队列。LFU 要多记一个维度：使用次数。比如容量为 2，先放入 a、b，然后读 a 两次，再读 b 一次，最后放入 c。LRU 会淘汰 a，因为 b 是更近被用到的；LFU 会淘汰 b，因为 a 用了 3 次，b 只用了 2 次。

所以 LFU 需要两层排序：先按次数，次数一样再按最近使用。直接用一个大数组排序做不到 O(1)，下面按次数分组来做。

用 Map 和 Set 实现

entries 记每个键的值和次数，groups 把次数映射到一个 Set，Set 里按使用先后存放这个次数下的键。

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.entries = new Map();
    this.groups = new Map();
    this.minFreq = 0;
  }

  touch(key) {
    const entry = this.entries.get(key);
    const group = this.groups.get(entry.freq);
    group.delete(key);
    if (group.size === 0) {
      this.groups.delete(entry.freq);
      // 只有最小次数那一组空了，最小次数才会变
      if (this.minFreq === entry.freq) this.minFreq += 1;
    }
    entry.freq += 1;
    if (!this.groups.has(entry.freq)) this.groups.set(entry.freq, new Set());
    this.groups.get(entry.freq).add(key);
  }

  get(key) {
    if (!this.entries.has(key)) return -1;
    this.touch(key);
    return this.entries.get(key).value;
  }

  put(key, value) {
    if (this.capacity === 0) return;
    if (this.entries.has(key)) {
      this.entries.get(key).value = value;
      this.touch(key);
      return;
    }
    if (this.entries.size === this.capacity) {
      const group = this.groups.get(this.minFreq);
      // Set 按插入顺序遍历，第一个就是这组里最久没用的
      const oldest = group.values().next().value;
      group.delete(oldest);
      if (group.size === 0) this.groups.delete(this.minFreq);
      this.entries.delete(oldest);
    }
    this.entries.set(key, { value, freq: 1 });
    if (!this.groups.has(1)) this.groups.set(1, new Set());
    this.groups.get(1).add(key);
    this.minFreq = 1;
  }
}

const cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 1
cache.put(3, 3);
console.log(cache.get(2)); // -1
console.log(cache.get(3)); // 3
cache.put(4, 4);
console.log(cache.get(1)); // -1
console.log(cache.get(3)); // 3
console.log(cache.get(4)); // 4

这组操作就是 LeetCode 460 的示例 1。放入 3 时，键 1 被读过一次，次数是 2，键 2 次数是 1，所以淘汰 2。放入 4 时，1 和 3 的次数都是 2，打平了，就看谁更久没用：3 刚被读过，1 更早，所以淘汰 1。

minFreq 为什么只在两处改？插入新键时，新键次数是 1，不可能有比它更小的，所以直接设成 1。访问已有的键时，键从 f 挪到 f+1，最小次数只可能在 f 那组被挪空、且 f 就是最小次数时变化，而且一定是变成 f+1，因为刚挪过去的键就在那里。淘汰发生在插入之前，淘汰后紧接着就把 minFreq 设成 1，所以淘汰时也不用重新找最小值。

为什么挪到新组时要先 delete 再 add？因为 Set 对已有元素再 add 不会改变它的位置。每次都放进一个新组的末尾，组内的顺序才能代表“最近一次使用的先后”。

复杂度

每个操作只做了常数次 Map 和 Set 的增删查。MDN 说明，规范只要求 Map 和 Set 的平均访问时间比线性快；按哈希表实现时平均是常数时间，所以面试里通常把这个写法算作题目要求的“平均 O(1)”。空间是 O(capacity)。

如果面试官要求不用 Set 的顺序特性，可以把每个组换成一条双向链表，再用一个 Map 从键找到链表节点，挪动时改几个指针，思路完全一样。

常见追问

capacity 为 0 时要注意什么？

这时什么都放不进去。如果不提前返回，put 会去 minFreq 那组淘汰元素，可是缓存是空的，那一组根本不存在，就会报错。所以 put 开头先判断容量为 0 直接返回。

LFU 的“缓存污染”是什么意思？怎么缓解？

某个键在一段时间里被访问了很多次，次数很高，后来不再被访问，可它的次数比新来的数据都高，就一直淘汰不掉。常见的缓解办法是让次数随时间衰减，或者给次数设上限。这些都是在 LeetCode 460 的规则之外做的改动。

为什么更新已有键的值也要让次数加 1？

这是 LeetCode 460 题面的规定：键被 get 或 put 操作到，使用次数都加 1。实际业务里可以按需要定义，但面试按题面实现。