LFU缓存淘汰算法原理与实现

问题描述
LFU（Least Frequently Used）是一种缓存淘汰策略，当缓存容量达到上限时，它会淘汰最不经常使用的数据项。与LRU（最近最少使用）关注访问时效性不同，LFU关注的是访问频率。实现一个高效的LFU缓存是系统设计中的常见需求。

核心挑战

• 需要快速获取当前访问频率最低的项（用于淘汰）
• 某个键被访问时，需要快速更新其频率
• 当多个键具有相同频率时，通常需要维护这些键的时序（如按LRU顺序），以便在相同频率键中淘汰最久未使用的

解决方案演进

步骤1：基础思路分析
最简单的想法是：

• 用哈希表存储键值对（实现O(1)查找）
• 每个键关联一个频率计数器
• 淘汰时扫描所有键找到频率最小的

问题：淘汰操作需要O(n)时间，无法满足高效需求。

步骤2：频率索引优化
引入"频率桶"概念，将相同频率的键组织在一起：

• 使用哈希表keyToFreq记录键到频率的映射
• 使用哈希表freqToKeys记录频率到键集合的映射
• 维护一个最小频率变量minFreq

操作逻辑：

• 访问键：将其从当前频率桶移除，加入更高频率桶，更新minFreq
• 淘汰键：从minFreq对应的桶中移除一个键

问题：当多个键频率相同时，无法确定淘汰顺序。

步骤3：时序维护优化
在每个频率桶内使用双向链表维护键的访问时序：

• 新访问的键添加到链表头部
• 淘汰时从链表尾部移除（最久未访问）
• 需要同时维护键到链表节点的映射

数据结构设计：

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val = {}  # 键到值的映射
        self.key_to_freq = {}  # 键到频率的映射
        self.freq_to_keys = {}  # 频率到双向链表的映射

步骤4：双向链表实现细节
每个频率对应一个双向链表，需要实现：

• add_to_head(node): 在链表头部添加节点
• remove_node(node): 删除指定节点
• remove_tail(): 删除尾部节点并返回键

链表节点包含键、值和前后指针。

步骤5：完整操作流程

get操作：

1. 键不存在时返回-1
2. 键存在时：
   • 从当前频率链表移除该键
   • 如果当前频率链表为空且频率等于min_freq，则min_freq++
   • 频率加1，将键添加到新频率链表头部
   • 返回值

put操作：

1. 如果键已存在：更新值，然后执行get操作更新频率
2. 如果键不存在：
   • 如果缓存已满：淘汰min_freq链表的尾部节点
   • 创建新节点，频率设为1
   • 将节点添加到频率1的链表头部
   • min_freq = 1（因为新节点频率最低）

步骤6：时间复杂度分析

• get操作：O(1)
• put操作：O(1)
  所有哈希操作和链表操作都是常数时间，满足高效需求。

实际应用场景
LFU适用于访问模式相对稳定的场景，如：

• 内容分发网络（CDN）的热点内容缓存
• 数据库查询结果缓存
• 操作系统页面置换算法

与LRU相比，LFU更能准确识别长期热点数据，但对访问模式变化适应性较差。在实际系统中常采用LFU和LRU的混合策略。