LFU频率置换算法全称Least Frequently Used，其核心思想是优先淘汰访问频率最低的数据。在实际缓存系统中，若只参考最近访问时间，短时突发流量可能让热点数据被误删，而LFU通过统计访问次数能更真实反映长期价值。基于变量计数淘汰策略，就是为每个缓存键维护一个计数器，每次访问自增，插入新数据初始化为1，空间不足时选出计数最小者删除。
LFU算法基础结构
实现LFU最简单的方式是使用一个映射保存键值，另一个映射保存键对应的频率。下文以Python为例展示最小可用版本。
# 简单的LFU缓存实现，基于变量计数淘汰
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.kv = {} # 存储键值对
self.cnt = {} # 存储键的访问计数
def get(self, key):
if key not in self.kv:
return -1
self.cnt[key] += 1
return self.kv[key]
def put(self, key, value):
if self.capacity <= 0:
return
if key in self.kv:
self.kv[key] = value
self.cnt[key] += 1
return
if len(self.kv) >= self.capacity:
# 找出计数最小的键进行淘汰
min_key = min(self.cnt, key=lambda k: self.cnt[k])
del self.kv[min_key]
del self.cnt[min_key]
self.kv[key] = value
self.cnt[key] = 1
cache = LFUCache(2)
cache.put('a', 1)
cache.put('b', 2)
cache.get('a')
cache.put('c', 3) # 此时b计数为1被淘汰
print(cache.kv)
变量计数策略的实战注意点
在真实业务里，单纯计数可能遇到以下问题：
- 旧键长期占用：早期高频但近期无访问的键计数高，难以淘汰。
- 计数溢出：超高频访问下整数膨胀，可定期衰减或采用对数计数。
- 同频取舍：多个键计数相同时，可结合插入时间或随机淘汰。
使用衰减优化计数
为避免历史热度误导，可每隔一段时间将所有计数减半，代码如下：
# 计数衰减示例
def decay(self):
for k in self.cnt:
self.cnt[k] = self.cnt[k] // 2
if self.cnt[k] == 0:
del self.kv[k]
del self.cnt[k]
与LRU的对比选择
当业务存在明显长期热点，如配置表、字典数据，LFU更合适；若数据时效性强、波动大，LRU或ARC等混合算法更好。下表列出基础差异：
| 维度 | LFU | LRU |
|---|---|---|
| 判断依据 | 访问频率 | 最近访问 |
| 抗突发流量 | 强 | 弱 |
| 实现复杂度 | 中 | 低 |
小结
基于变量计数的LFU实现轻量直观，适合嵌入本地缓存模块。生产环境建议加上过期时间与计数衰减，防止冷数据滞留。开发者可根据监控命中率动态调整容量与衰减周期，使淘汰策略贴合实际流量模型。