LFU 缓存：历史学家

算法背后的故事：名人堂

想象一个只能容纳 5 座雕像的名人堂。

• 谁能获得一座雕像？不是那个昨天做了一件酷事的人（那是 LRU）。
• 雕像是留给那个在历史上做酷事次数最多的人的。

如果迈克尔·乔丹（频率：10,000）已经 10 年没打球了，他依然留在名人堂里。如果一个新秀（频率：1）昨晚刚刚砍下 50 分，他依然进不去。

这就是 LFU (最不经常使用)。它保护“经典”。它假设如果一条数据被请求了 500 次，那它本质上就是重要的，即使过去一小时没人问津。

为什么需要它？

• 静态资源： Google 的 Logo、CSS 重置文件、“首页”图标。这些东西被持续不断地访问。LRU 可能会在一次“扫描”（一次性突发流量）中意外驱逐它们。LFU 保护它们。
• CDN (内容分发网络)： 无论当前几点钟，始终把最受欢迎的视频缓存在边缘节点。

算法是如何“思考”的

在 $O(1)$ 时间内实现 LFU 出了名的难。你需要：

1. 追踪每个键的 频率。
2. 当缓存满时，找到 min(频率) 对应的键。
3. 如果平局（多个键频率都是 1），驱逐它们当中 最近最少使用 的那个。

$O(1)$ 的解法需要一个复杂的结构：双向链表的哈希映射。

• Map<频率, List<Node>>：“列表 1”装着所有频率为 1 的项。“列表 5”装着所有频率为 5 的项。
• min_freq：一个指针，永远指向当前非空的最小频率列表。

1. 访问 (Get)：

   • 找到节点。freq 变为 freq + 1。
   • 从 List[freq] 中移除节点。
   • 加入到 List[freq + 1] 中。
   • 如果 List[min_freq] 空了，更新 min_freq。

2. 插入 (Put)：

   • 如果是新的：加入 List[1]。min_freq 变为 1。
   • 如果满了：去 List[min_freq]。移除那个特定列表中的 LRU 节点。

工程决策：过去的幽灵

LFU 有一个致命缺陷：缓存污染 (Memory Pollution)。

• 问题： 想象一篇关于“2020 年奥运会”的新闻。它在两周内获得了 100 万次点击。它的频率极高。
• 后果： 三年后，没人关心了。但因为它的频率是 100 万，它永远坐在缓存里，占据着新内容的位置。
• 修复： 现代 LFU（如 Window-TinyLFU）使用“老化”或“衰减”机制。每隔一小时，将所有频率除以 2。这迫使旧日的英雄最终退休。

实现参考 (Python)

这是一个使用“列表映射”策略的简化版 $O(1)$ 实现。

import collections

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_node = {} # Map<Key, Node>
        self.freq_to_nodes = collections.defaultdict(collections.OrderedDict)

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        
        node = self.key_to_node[key]
        # 1. 晋升频率
        val = node.value
        self._update_freq(node)
        return val

    def _update_freq(self, node):
        # 从当前频率列表移除
        freq = node.freq
        del self.freq_to_nodes[freq][node.key]
        
        # 如果该列表空了且曾是最小频率，让 min_freq 递增
        if not self.freq_to_nodes[freq] and self.min_freq == freq:
            self.min_freq += 1
        
        # 加入下一个频率列表
        node.freq += 1
        self.freq_to_nodes[node.freq][node.key] = node

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0: return

        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.value = value
            self._update_freq(node)
            return

        if len(self.key_to_node) >= self.capacity:
            # 从 min_freq 列表中驱逐
            # popitem(last=False) 弹出第一项 (符合 FIFO/LRU 规则)
            k, v = self.freq_to_nodes[self.min_freq].popitem(last=False)
            del self.key_to_node[k]

        # 添加新节点
        new_node = Node(key, value)
        self.key_to_node[key] = new_node
        self.freq_to_nodes[1][key] = new_node
        self.min_freq = 1

小结

LFU 教会我们：忠诚很重要。通过看重长期热度而非短期潮流，它为“经典”创造了一个稳定的环境。但它也警告我们：永远不要让过去拖累未来。即使是传奇，最终也必须为新一代让位。