缓存算法 #02：LFU（最少使用频率）

LFU（Least Frequently Used）淘汰访问频率最低的缓存条目（频率相同时淘汰最久未用的）。相比 LRU 的"时间局部性"，LFU 利用"频率局部性"——高频访问的数据更值得保留。本文推导出 O(1) 实现，并深入分析 LFU 的老化问题与修复方案。

章节	说明
问题定义	LFU vs LRU 的根本差异
朴素实现与瓶颈	为什么最小堆不够
O(1) 数据结构设计	三层数据结构推导
完整伪代码	get / put 的每一步操作
执行追踪	逐步演示状态变化
复杂度分析	时间与空间
异常场景	minFreq 更新 / 容量边界
LFU 的老化问题	历史频率污染与修复

问题定义

与 LRU 相同的接口，但淘汰策略不同：

驱逐规则：
  LRU → 驱逐最长时间未访问的（无论访问了多少次）
  LFU → 驱逐访问次数最少的；次数相同时，驱逐最久未用的

示例（capacity=2）：
  put(1,A)  → freq[1]=1
  put(2,B)  → freq[2]=1
  get(1)    → freq[1]=2
  put(3,C)  → 容量满，freq[1]=2 freq[2]=1
               LRU 驱逐 key=2（最久未用）
               LFU 驱逐 key=2（频率最低，freq=1）
               （这里结果相同，接着看区别）
  get(2)    → LRU：key=2 已驱逐，miss
              LFU：key=2 已驱逐，miss
  put(4,D)  → LRU 驱逐 key=3（最近访问了 key=1 和 key=3）
              LFU 驱逐 key=3（freq[3]=1）

区别体现在：某个 key 被访问 100 次后再也不访问，
LRU 会很快驱逐它（最久未用），
LFU 会让它长期占据缓存（频率高）→ 这正是 LFU 的老化问题

朴素实现与瓶颈

朴素方案：HashMap<key,freq> + 最小堆（按 freq 排序）

get(key)：HashMap 查 freq，堆中更新 freq → O(log N)  ← 不满足 O(1)
put(key)：堆顶取最小 freq 的 key 驱逐     → O(log N)  ← 不满足 O(1)

问题：堆的 decrease-key 操作是 O(log N)
     无法在 O(1) 内完成 get 时的频率更新

O(1) 数据结构设计

核心思路：不用堆维护顺序，改用按频率分桶的双向链表。

lfu structure

三层数据结构：

层 1：keyMap   HashMap<key, Node>
       key → 节点（含 value 和 freq）
       作用：O(1) 找到节点

层 2：freqMap  HashMap<freq, LinkedHashSet<key>>
       freq → 该频率下的 key 集合（按插入顺序，最久插入的在前）
       作用：O(1) 找到某频率下最久未用的 key

层 3：minFreq  int
       当前最小频率（用于 O(1) 找到驱逐目标）
       作用：直接定位 freqMap[minFreq] 的最旧 key

为什么用 LinkedHashSet 而不是普通 Set？
  LinkedHashSet = HashMap + 双向链表，保证有序（按插入时间）
  同频率的 key 中，LinkedHashSet.iterator().next() 就是最久未访问的
  插入、删除、按序访问：均 O(1)（摊销）

完整伪代码

class LFUCache:
    capacity: int
    size:     int
    minFreq:  int
    keyMap:   HashMap<int, Node>              // key → {value, freq}
    freqMap:  HashMap<int, LinkedHashSet<int>> // freq → ordered set of keys

    init(capacity):
        self.capacity = capacity
        self.size     = 0
        self.minFreq  = 0
        self.keyMap   = {}
        self.freqMap  = {}

内部辅助：increaseFreq(key)

// 将 key 的频率 +1，维护所有数据结构
increaseFreq(key):
    node     = keyMap[key]
    oldFreq  = node.freq
    newFreq  = oldFreq + 1

    // 1. 从旧频率桶中移除
    freqMap[oldFreq].remove(key)
    if freqMap[oldFreq] is empty:
        del freqMap[oldFreq]
        if minFreq == oldFreq:
            minFreq = newFreq  // 旧最小桶空了，最小频率+1

    // 2. 加入新频率桶
    if newFreq not in freqMap:
        freqMap[newFreq] = LinkedHashSet()
    freqMap[newFreq].add(key)   // 加到末尾（最新的）

    // 3. 更新节点频率
    node.freq = newFreq

get(key)

get(key):
    if key not in keyMap:
        return -1

    increaseFreq(key)           // freq +1，移动到新桶
    return keyMap[key].value

put(key, value)

put(key, value):
    if capacity == 0:
        return

    if key in keyMap:
        // key 已存在：更新值，频率 +1
        keyMap[key].value = value
        increaseFreq(key)

    else:
        // key 不存在：新建

        if size == capacity:
            // 驱逐：freqMap[minFreq] 中最旧的那个 key
            evictKey = freqMap[minFreq].first()  // LinkedHashSet 的头部
            freqMap[minFreq].remove(evictKey)
            if freqMap[minFreq] is empty:
                del freqMap[minFreq]
            del keyMap[evictKey]
            size -= 1

        // 插入新节点，freq=1
        keyMap[key] = Node(value=value, freq=1)
        if 1 not in freqMap:
            freqMap[1] = LinkedHashSet()
        freqMap[1].add(key)
        minFreq = 1       // 新节点 freq=1，必然是最小频率
        size += 1

执行追踪

capacity=3，依次：put(1,A) put(2,B) put(3,C) get(1) get(1) get(2) put(4,D) get(3)

put(1,A)：
  keyMap  = {1:(A,1)}
  freqMap = {1:{1}}
  minFreq = 1，size=1

put(2,B)：
  keyMap  = {1:(A,1), 2:(B,1)}
  freqMap = {1:{1,2}}
  minFreq = 1，size=2

put(3,C)：
  keyMap  = {1:(A,1), 2:(B,1), 3:(C,1)}
  freqMap = {1:{1,2,3}}
  minFreq = 1，size=3

get(1)：increaseFreq(1)
  oldFreq=1，newFreq=2
  freqMap = {1:{2,3}, 2:{1}}   ← 1 从桶1移到桶2
  minFreq=1（桶1还有 {2,3}，不空）
  返回 A

get(1)：increaseFreq(1)
  oldFreq=2，newFreq=3
  freqMap = {1:{2,3}, 3:{1}}
  minFreq=1，返回 A

get(2)：increaseFreq(2)
  oldFreq=1，newFreq=2
  freqMap = {1:{3}, 2:{2}, 3:{1}}
  minFreq=1（桶1还有 {3}，不空）
  返回 B

put(4,D)：size=3=capacity，需要驱逐
  minFreq=1，freqMap[1]={3}，first()=3
  驱逐 key=3，del keyMap[3]，del freqMap[1]
  插入 4：keyMap={1:(A,3),2:(B,2),4:(D,1)}
  freqMap={2:{2},3:{1},1:{4}}
  minFreq=1，size=3

get(3)：key=3 已被驱逐 → 返回 -1 ✅

此时状态：
  key=1 频率最高(3)，保留最久
  key=2 频率中等(2)
  key=4 刚插入(1)，下次驱逐候选

复杂度分析

操作	时间复杂度	原因
`get`	O(1)	keyMap 查找 + LinkedHashSet 操作均 O(1)
`put`	O(1)	新建/驱逐/increaseFreq 均 O(1)
空间	O(capacity)	keyMap + freqMap 各存 capacity 个

关键细节：LinkedHashSet 的 first()（取最旧元素）是 O(1)，因为内部维护了双向链表头指针。

异常场景

minFreq 更新时机

minFreq 只在两种情况下改变：

情况1：get/put 调用 increaseFreq，旧桶变空 AND 旧桶 = minFreq
  → minFreq = oldFreq + 1

情况2：put 插入新 key
  → minFreq = 1（新 key 的 freq 永远是 1，1 一定是最小）

错误写法：驱逐后立刻去找最小 freq（遍历 freqMap）→ O(N)
正确写法：利用上面两条规则，O(1) 维护 minFreq

capacity = 0

put 任何 key：直接 return（缓存容量为 0，不存任何东西）
get 任何 key：返回 -1

需要在 put 开头加 guard：
    if capacity == 0: return

put 相同 key 多次

put(1,A)   → keyMap[1]=(A,1), freqMap={1:{1}}, minFreq=1
put(1,B)   → key=1 已存在，走更新分支
              keyMap[1].value=B，increaseFreq(1)
              keyMap[1]=(B,2), freqMap={2:{1}}, minFreq=2

注意：更新时 size 不变，但 minFreq 可能因为 freqMap[1] 变空而更新

驱逐时 freqMap[minFreq] 为空

理论上不会发生：
  minFreq 始终指向一个非空桶
  proof：
    increaseFreq 中，只有桶变空且等于 minFreq 才更新 minFreq
    put 新 key 后 minFreq=1，此时 freqMap[1] 至少有新 key（非空）
    因此进入驱逐逻辑时，freqMap[minFreq] 一定非空

LFU 的老化问题

问题：历史频率污染

场景：
  系统运行初期，key=A 被访问了 10000 次（热点）
  系统运行中期，key=A 不再被访问
  系统运行后期，key=B 是新热点，被访问了 50 次
  key=C 是最新插入，被访问了 30 次

LFU 的状态：
  freq[A]=10000，freq[B]=50，freq[C]=30
  → 下次驱逐候选是 key=C（freq 最低）
  → key=A 虽然很久没用，但因历史频率高，霸占缓存

这就是"频率老化"（Frequency Aging）问题：
  过去的高频访问被无限期记忆，新兴热点难以进入缓存

修复方案

方案	原理	代价
时间衰减（Decay）	定期将所有 freq 减半（aging）	需要周期性操作，实现复杂
滑动窗口 LFU	只统计最近 N 次访问的频率	窗口需要额外空间
W-TinyLFU（Caffeine）	Sketch + Window 分区，近似频率 + 新数据保护区	最优，见 W-TinyLFU 与 Caffeine
LRU + LFU 混合（ARC）	同时维护 LRU 链和 LFU 链，自适应切换	见 ARC（自适应替换缓存）

结论：纯 LFU 在工程中很少单独使用，通常配合衰减机制或替换为 W-TinyLFU。

参考资料

LeetCode 460. LFU Cache

Shah, K. et al. (2010). An O(1) algorithm for implementing the LFU cache eviction scheme

Caffeine GitHub Wiki: https://github.com/ben-manes/caffeine/wiki