💾 缓存置换算法
在有限空间内智能管理数据，最大化缓存命中率，提升系统性能
🔄 LRU
最近最少使用，基于时间局部性。最经典的缓存算法，广泛应用。
📊 LFU
最不经常使用，基于频率统计。适合热点数据明显的场景。
📥 FIFO
先进先出，最简单直接。实现成本低，但性能一般。
🕐 MRU
最近最多使用，特殊场景适用。适合循环访问模式。
⏰ Clock
时钟算法，LRU 的近似实现。性能与成本的平衡选择。
💡 缓存核心原理
🎯 时间局部性
最近访问的数据可能再次被访问
📍 空间局部性
访问某个数据时，附近数据也可能被访问
📈 命中率优化
最大化缓存命中，最小化未命中
⚡ 降低延迟
减少从慢速存储读取数据的次数
🔄 1. LRU - 最近最少使用
算法原理
LRU 算法基于"最近使用的条目在未来更可能被使用"的假设。当缓存满时，淘汰最长时间未被访问的数据。
🏗️ LRU 数据结构：哈希表 + 双向链表
📖 哈希表
O(1) 查找
key → 链表节点
O(1) 查找
key → 链表节点
🔗 双向链表
维护访问顺序
头→最新，尾→最老
维护访问顺序
头→最新，尾→最老
LRU 缓存状态示意：
┌─────────┐ head ─────────────────────────────────── tail ┐
│ │ │
│ HashMap │ HEAD TAIL
│─────────│ ↓ ↓
│ A: node1 │ [A] ↔ [B] ↔ [C] ↔ [D] ↔ [E] (最近使用顺序)
│ B: node2 │ ↑ ↑
│ C: node3 │ 最新访问 最老访问
│ D: node4 │ ↓ 被淘汰
│ E: node5 │
└─────────┘
查询
O(1)
插入
O(1)
删除
O(1)
✅ 优点
- 实现简单，容易理解
- 不存在 Belady 异常
- 适合大多数实际场景
- 时间复杂度最优
❌ 缺点
- 需要维护访问顺序
- 循环访问模式性能差
- 冷启动时需要预热
- 内存开销较大
代码实现
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
this.cache.set(key, value);
}
}
// 测试
const lru = new LRUCache(3);
lru.put(1, 'A');
lru.put(2, 'B');
lru.put(3, 'C');
console.log(lru.get(1)); // 'A'
lru.put(4, 'D'); // 淘汰 2
console.log(lru.get(2)); // -1from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# 测试
lru = LRUCache(3)
lru.put(1, 'A')
lru.put(2, 'B')
lru.put(3, 'C')
print(lru.get(1)) # 'A'
lru.put(4, 'D') # 淘汰 2
print(lru.get(2)) # -1package main
import (
"container/list"
"fmt"
)
type LRUCache struct {
capacity int
cache map[int]*list.Element
lruList *list.List
}
type entry struct {
key int
value interface{}
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
capacity: capacity,
cache: make(map[int]*list.Element),
lruList: list.New(),
}
}
func (c *LRUCache) Get(key int) interface{} {
if elem, ok := c.cache[key]; ok {
c.lruList.MoveToFront(elem)
return elem.Value.(*entry).value
}
return -1
}
func (c *LRUCache) Put(key int, value interface{}) {
if elem, ok := c.cache[key]; ok {
c.lruList.MoveToFront(elem)
elem.Value.(*entry).value = value
return
}
if c.lruList.Len() >= c.capacity {
back := c.lruList.Back()
if back != nil {
evict := back.Value.(*entry)
delete(c.cache, evict.key)
c.lruList.Remove(back)
}
}
newEntry := &entry{key: key, value: value}
elem := c.lruList.PushFront(newEntry)
c.cache[key] = elem
}
func main() {
lru := NewLRUCache(3)
lru.Put(1, "A")
lru.Put(2, "B")
lru.Put(3, "C")
fmt.Println(lru.Get(1)) // A
lru.Put(4, "D") // 淘汰 2
fmt.Println(lru.Get(2)) // -1
}📊 2. LFU - 最不经常使用
算法原理
LFU 算法基于"使用频率低的数据在未来使用的可能性也低"的假设。当缓存满时，淘汰访问频率最低的数据。
LFU 数据结构示意：
┌─────────────────────────────────────────────────┐
│ freq=1: [A] ←→ [B] │
│ freq=2: [C] ←→ [D] │
│ freq=3: [E] │
└─────────────────────────────────────────────────┘
哈希表：{A: node, B: node, C: node, ...}
minFreq = 1
查询
O(1)
插入
O(log n)
删除
O(1)
✅ 优点
- 保留热点数据
- 适合频率差异大的场景
- 长期性能稳定
❌ 缺点
- 实现复杂度高
- 存在"饥饿"问题
- 需要频率衰减机制
代码实现
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.minFreq = 0;
this.cache = new Map();
this.freqMap = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this._updateFreq(node);
return node.value;
}
put(key, value) {
if (this.capacity <= 0) return;
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.value = value;
this._updateFreq(node);
} else {
if (this.cache.size >= this.capacity) {
this._evict();
}
const node = { key, value, freq: 1 };
this.cache.set(key, node);
if (!this.freqMap.has(1)) {
this.freqMap.set(1, new Set());
}
this.freqMap.get(1).add(node);
this.minFreq = 1;
}
}
_updateFreq(node) {
const oldFreq = node.freq;
this.freqMap.get(oldFreq).delete(node);
if (this.freqMap.get(oldFreq).size === 0) {
this.freqMap.delete(oldFreq);
if (this.minFreq === oldFreq) this.minFreq++;
}
node.freq++;
if (!this.freqMap.has(node.freq)) {
this.freqMap.set(node.freq, new Set());
}
this.freqMap.get(node.freq).add(node);
}
_evict() {
const minFreqSet = this.freqMap.get(this.minFreq);
const firstKey = minFreqSet.values().next().value.key;
minFreqSet.delete(firstKey);
this.cache.delete(firstKey);
}
}
// 测试
const lfu = new LFUCache(3);
lfu.put(1, 'A');
lfu.put(2, 'B');
lfu.put(3, 'C');
lfu.get(1); lfu.get(2);
lfu.put(4, 'D'); // 淘汰 C
console.log(lfu.get(3)); // -1from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.min_freq = 0
self.cache = {}
self.freq_map = defaultdict(OrderedDict)
def get(self, key):
if key not in self.cache:
return -1
value, freq = self.cache[key]
self._update_freq(key, freq)
return value
def put(self, key, value):
if self.capacity <= 0:
return
if key in self.cache:
old_freq = self.cache[key][1]
self.cache[key][0] = value
self._update_freq(key, old_freq)
else:
if len(self.cache) >= self.capacity:
self._evict()
self.cache[key] = [value, 1]
self.freq_map[1][key] = value
self.min_freq = 1
def _update_freq(self, key, old_freq):
del self.freq_map[old_freq][key]
if not self.freq_map[old_freq]:
del self.freq_map[old_freq]
if self.min_freq == old_freq:
self.min_freq += 1
new_freq = old_freq + 1
self.cache[key][1] = new_freq
self.freq_map[new_freq][key] = self.cache[key][0]
def _evict(self):
min_freq_keys = self.freq_map[self.min_freq]
evict_key = next(iter(min_freq_keys))
del min_freq_keys[evict_key]
if not min_freq_keys:
del self.freq_map[self.min_freq]
del self.cache[evict_key]
# 测试
lfu = LFUCache(3)
lfu.put(1, 'A')
lfu.put(2, 'B')
lfu.put(3, 'C')
lfu.get(1)
lfu.get(2)
lfu.put(4, 'D')
print(lfu.get(3)) # -1package main
import (
"container/list"
"fmt"
)
type LFUCache struct {
capacity int
minFreq int
cache map[int]*list.Element
freqMap map[int]*list.List
}
type lfuEntry struct {
key int
value interface{}
freq int
}
func NewLFUCache(capacity int) *LFUCache {
return &LFUCache{
capacity: capacity,
cache: make(map[int]*list.Element),
freqMap: make(map[int]*list.List),
}
}
func (c *LFUCache) Get(key int) interface{} {
if elem, ok := c.cache[key]; ok {
c.updateFreq(elem)
return elem.Value.(*lfuEntry).value
}
return -1
}
func (c *LFUCache) Put(key int, value interface{}) {
if c.capacity <= 0 {
return
}
if elem, ok := c.cache[key]; ok {
elem.Value.(*lfuEntry).value = value
c.updateFreq(elem)
return
}
if len(c.cache) >= c.capacity {
c.evict()
}
entry := &lfuEntry{key: key, value: value, freq: 1}
if c.freqMap[1] == nil {
c.freqMap[1] = list.New()
}
elem := c.freqMap[1].PushBack(entry)
c.cache[key] = elem
c.minFreq = 1
}
func (c *LFUCache) updateFreq(elem *list.Element) {
entry := elem.Value.(*lfuEntry)
oldFreq := entry.freq
c.freqMap[oldFreq].Remove(elem)
if c.freqMap[oldFreq].Len() == 0 {
delete(c.freqMap, oldFreq)
if c.minFreq == oldFreq {
c.minFreq++
}
}
entry.freq++
if c.freqMap[entry.freq] == nil {
c.freqMap[entry.freq] = list.New()
}
newElem := c.freqMap[entry.freq].PushBack(entry)
c.cache[entry.key] = newElem
}
func (c *LFUCache) evict() {
if c.freqMap[c.minFreq] == nil {
return
}
front := c.freqMap[c.minFreq].Front()
if front != nil {
entry := front.Value.(*lfuEntry)
c.freqMap[c.minFreq].Remove(front)
if c.freqMap[c.minFreq].Len() == 0 {
delete(c.freqMap, c.minFreq)
}
delete(c.cache, entry.key)
}
}
func main() {
lfu := NewLFUCache(3)
lfu.Put(1, "A")
lfu.Put(2, "B")
lfu.Put(3, "C")
fmt.Println(lfu.Get(1)) // A
fmt.Println(lfu.Get(2)) // B
lfu.Put(4, "D")
fmt.Println(lfu.Get(3)) // -1
}📊 算法对比与选择
缓存算法对比
🔄 LRU
- 基于访问时间
- O(1) 复杂度
- 无 Belady 异常
- 通用场景首选
📊 LFU
- 基于访问频率
- O(log n) 复杂度
- 保留热点数据
- 频率差异大场景
📥 FIFO
- 基于进入时间
- O(1) 复杂度
- 实现最简单
- 性能一般
⏰ Clock
- LRU 近似
- O(1) 复杂度
- 空间效率高
- 操作系统常用
应用场景推荐
🌐 Web 缓存
- LRU：页面缓存
- LFU：静态资源
- CDN：地理分布
🗄️ 数据库缓存
- LRU：InnoDB 缓冲池
- Clock：页面置换
- LRU-K：查询缓存
💾 操作系统
- Clock：页面置换
- LRU：文件缓存
- MRU：特殊场景
🎯 算法选择指南
- 通用场景：LRU（简单高效，无异常）
- 热点明显：LFU（保留高频数据）
- 资源受限：FIFO/Clock（实现简单）
- 循环访问：MRU（特殊场景）
- 操作系统：Clock（性能与成本平衡）
- 数据库缓存：LRU/LRU-K（成熟稳定）