1. 缓存淘汰算法基础概念
在计算机系统中，缓存是一种用空间换时间的设计策略。当缓存空间被占满时，我们需要决定哪些数据应该被保留，哪些数据可以被淘汰——这就是缓存淘汰算法要解决的问题。LRU（Least Recently Used）和LFU（Least Frequently Used）是两种最经典的缓存淘汰策略，它们在各类系统中有着广泛应用。
缓存淘汰算法的核心矛盾在于：如何在有限的内存空间内，最大化缓存命中率。这就像图书馆的书架空间有限，我们需要决定哪些书应该保留在触手可及的位置。
1.1 LRU算法原理
LRU算法的核心思想是"最近最少使用"。它假设最近被访问过的数据，在不久的将来更有可能再次被访问。实现LRU通常需要以下组件：
- 哈希表：提供O(1)时间复杂度的键值查找
- 双向链表：维护数据的访问顺序
当访问一个键时：
- 如果键存在，将其移动到链表头部（表示最近使用）
- 如果键不存在且缓存已满，则淘汰链表尾部的键（最久未使用）
- 新插入的键总是放在链表头部
class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head1.2 LFU算法原理
LFU算法则关注"使用频率"，它认为被访问次数更多的数据应该被保留。LFU的实现比LRU更复杂，需要维护：
- 键到值的映射（类似LRU）
- 键到访问频率的映射
- 频率到键列表的映射（通常按最近访问时间排序）
当缓存满时，LFU会：
- 找到当前最小频率
- 在该频率对应的键列表中淘汰最久未使用的键
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 = defaultdict(OrderedDict)2. LeetCode 146题：LRU缓存实现
2.1 问题描述
设计并实现一个满足LRU缓存约束的数据结构。需要支持以下操作：
get(key)：如果键存在则返回值，否则返回-1put(key, value)：如果键不存在则插入；当缓存达到容量时，淘汰最久未使用的键
要求get和put操作的时间复杂度都是O(1)。
2.2 数据结构选择
要实现O(1)时间复杂度，我们需要：
- 哈希表：提供快速的键值查找
- 双向链表：维护访问顺序，支持快速移动和删除节点
这种组合被称为"哈希链表"。哈希表存储键到链表节点的映射，链表维护键的访问顺序。
2.3 完整实现代码
class Node: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head self.size = 0 def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self.move_to_head(node) return node.value def put(self, key: int, value: int) -> None: if key in self.cache: node = self.cache[key] node.value = value self.move_to_head(node) else: node = Node(key, value) self.cache[key] = node self.add_to_head(node) self.size += 1 if self.size > self.capacity: removed = self.remove_tail() del self.cache[removed.key] self.size -= 1 def add_to_head(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def remove_node(self, node): node.prev.next = node.next node.next.prev = node.prev def move_to_head(self, node): self.remove_node(node) self.add_to_head(node) def remove_tail(self): node = self.tail.prev self.remove_node(node) return node2.4 复杂度分析
- 时间复杂度：get和put都是O(1)
- 哈希表操作：O(1)
- 链表操作：添加、删除、移动都是O(1)
- 空间复杂度：O(capacity)
- 哈希表和链表都最多存储capacity个元素
3. LeetCode 460题：LFU缓存实现
3.1 问题描述
设计并实现一个满足LFU缓存约束的数据结构。需要支持以下操作：
get(key)：如果键存在则返回值，否则返回-1put(key, value)：如果键不存在则插入；当缓存达到容量时，淘汰使用频率最低的键（频率相同时淘汰最久未使用的）
同样要求get和put操作的时间复杂度都是O(1)。
3.2 数据结构设计
要实现O(1)的LFU，我们需要三层结构：
key_to_val：键到值的映射key_to_freq：键到频率的映射freq_to_keys：频率到键列表的映射（使用OrderedDict维护插入顺序）
此外，还需要维护当前最小频率min_freq，避免每次从所有频率中查找最小值。
3.3 完整实现代码
from collections import defaultdict, OrderedDict 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 = defaultdict(OrderedDict) def get(self, key: int) -> int: if key not in self.key_to_val: return -1 self._update_freq(key) return self.key_to_val[key] def put(self, key: int, value: int) -> None: if self.capacity == 0: return if key in self.key_to_val: self.key_to_val[key] = value self._update_freq(key) else: if len(self.key_to_val) >= self.capacity: self._evict() self.key_to_val[key] = value self.key_to_freq[key] = 1 self.freq_to_keys[1][key] = None self.min_freq = 1 def _update_freq(self, key): freq = self.key_to_freq[key] self.freq_to_keys[freq].pop(key) if not self.freq_to_keys[freq] and freq == self.min_freq: self.min_freq += 1 self.key_to_freq[key] += 1 self.freq_to_keys[freq+1][key] = None def _evict(self): key, _ = self.freq_to_keys[self.min_freq].popitem(last=False) del self.key_to_val[key] del self.key_to_freq[key]3.4 复杂度分析
- 时间复杂度：get和put都是O(1)
- 所有字典操作都是O(1)
- OrderedDict的popitem和插入都是O(1)
- 空间复杂度：O(capacity)
- 三个字典都最多存储capacity个元素
4. LRU与LFU的对比与应用场景
4.1 性能特点对比
| 特性 | LRU | LFU |
|---|---|---|
| 淘汰策略 | 最近最少使用 | 最不经常使用 |
| 实现复杂度 | 相对简单 | 较为复杂 |
| 内存开销 | 较小 | 较大 |
| 热点数据 | 短期热点表现好 | 长期热点表现好 |
| 突发流量 | 适应快 | 可能污染缓存 |
| 时间局部性 | 强 | 弱 |
| 频率局部性 | 弱 | 强 |
4.2 典型应用场景
LRU适用场景：
- 操作系统页面置换
- 数据库查询缓存
- 大多数web应用缓存（如Redis默认使用近似LRU）
- 浏览器缓存
LFU适用场景：
- 内容分发网络(CDN)
- 广告推荐系统
- 长期热点数据缓存
- 需要识别并保留热门内容的系统
4.3 生产环境中的变种算法
实际系统中很少使用纯LRU或LFU，而是它们的变种：
- LRU-K：考虑最近K次访问记录，平衡LRU和LFU的特点
- 2Q：使用两个队列分别管理冷热数据
- ARC：自适应替换缓存，动态调整LRU和LFU的比例
- TinyLFU：使用计数布隆过滤器近似LFU，减少内存开销
在Java生态中，Caffeine缓存库就使用了Window TinyLFU算法，结合了LRU和LFU的优点，是Guava Cache的现代替代品。
5. 面试中的常见问题与优化
5.1 高频面试问题
为什么LRU需要双向链表？单链表不行吗？
- 双向链表支持O(1)时间删除任意节点，单链表删除需要遍历
LFU中为什么要维护min_freq？
- 避免每次淘汰时遍历所有频率寻找最小值，保证O(1)时间淘汰
如何测试缓存实现的正确性？
- 设计测试用例覆盖：缓存未满、缓存已满、交替访问、连续访问相同键等场景
如果缓存值很大，如何优化内存？
- 使用指针或引用代替实际值
- 考虑分片存储
- 使用压缩算法
5.2 性能优化技巧
内存优化：
- 使用更紧凑的数据结构，如用数组模拟链表
- 对于整数键，可以考虑使用开放寻址法哈希表
并发优化：
- 读写锁分离：读操作共享锁，写操作独占锁
- 分段锁：将缓存分成多个段，减少锁竞争
- 无锁设计：使用CAS操作（实现复杂）
分布式环境：
- 一致性哈希分配缓存键
- 考虑缓存副本与一致性协议
- 多级缓存设计（本地+远程）
# 简单的线程安全LRU实现示例（使用锁） import threading class ThreadSafeLRUCache(LRUCache): def __init__(self, capacity): super().__init__(capacity) self.lock = threading.RLock() def get(self, key): with self.lock: return super().get(key) def put(self, key, value): with self.lock: super().put(key, value)5.3 实际工程中的考量
- 缓存预热：系统启动时预先加载热点数据
- 缓存穿透：对不存在的键也进行短暂缓存，避免反复查询数据库
- 缓存雪崩：设置不同的过期时间，避免同时失效
- 监控指标：缓存命中率、平均加载时间、内存使用量等
- 淘汰策略组合：可以结合LRU和LFU，如主缓存用LRU，热点缓存用LFU
在实现生产级缓存系统时，除了核心算法外，还需要考虑：
- 序列化与反序列化性能
- 内存分配策略
- 过期时间处理
- 统计与监控集成
- 与持久化存储的交互
缓存系统的设计往往需要在一致性、可用性和性能之间做出权衡，理解LRU和LFU这些基础算法是构建更复杂缓存系统的基石。
