cache替换策略LFU

### LFU 缓存替换策略解释 LFU (Least Frequently Used) 是一种基于频率的缓存淘汰算法，旨在保留访问频次较高的数据项。每当新条目加入或现有条目被访问时，其对应的计数器都会增加。当缓存达到容量上限并需移除项目时，具有最低访问次数的数据会被优先删除。 为了有效管理这些操作，在实际应用中通常采用哈希表配合双向链表来存储键值对及其元数据（如访问频率）。这种结构允许快速查找、更新以及按顺序排列节点[^1]。 #### 实现细节 以下是 Python 中的一个简单版本： ```python from collections import defaultdict, OrderedDict class LFUCache: def __init__(self, capacity: int): self.capacity = capacity self.key_to_freq = {} self.freq_to_keys = defaultdict(OrderedDict) self.min_frequency = 0 def get(self, key: int) -> int: if key not in self.key_to_freq: return -1 freq = self.key_to_freq[key] value = self.freq_to_keys[freq][key] del self.freq_to_keys[freq][key] if not self.freq_to_keys[freq]: del self.freq_to_keys[freq] if self.min_frequency == freq: self.min_frequency += 1 new_freq = freq + 1 self.key_to_freq[key] = new_freq self.freq_to_keys[new_freq][key] = value return value def put(self, key: int, value: int) -> None: if self.capacity <= 0: return if key in self.key_to_freq: old_value = self.get(key) self.freq_to_keys[self.key_to_freq[key]][key] = value return elif len(self.key_to_freq) >= self.capacity: evict_key, _ = next(iter(self.freq_to_keys[self.min_frequency].items())) del self.freq_to_keys[self.min_frequency][evict_key] del self.key_to_freq[evict_key] if not self.freq_to_keys[self.min_frequency]: del self.freq_to_keys[self.min_frequency] self.key_to_freq[key] = 1 self.freq_to_keys[1][key] = value self.min_frequency = 1 ``` 此代码片段展示了如何创建一个基本版的 LFU 缓存类 `LFUCache` ，其中包含了获取 (`get`) 和放置 (`put`) 方法用于处理缓存中的读写请求。该实现利用了字典和有序字典以支持高效的插入、检索及频率统计功能[^2]。