LRU与LFU缓存淘汰算法详解与实现

1. 缓存淘汰算法基础概念在计算机系统中缓存是一种用空间换时间的设计策略。当缓存空间被占满时我们需要决定哪些数据应该被保留哪些数据可以被淘汰——这就是缓存淘汰算法要解决的问题。LRULeast Recently Used和LFULeast 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, key0, value0): 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[freq1][key] None def _evict(self): key, _ self.freq_to_keys[self.min_freq].popitem(lastFalse) 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 性能特点对比特性LRULFU淘汰策略最近最少使用最不经常使用实现复杂度相对简单较为复杂内存开销较小较大热点数据短期热点表现好长期热点表现好突发流量适应快可能污染缓存时间局部性强弱频率局部性弱强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这些基础算法是构建更复杂缓存系统的基石。