LRU 和 LFU 缓存怎么实现？

class Node: def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = {} # key → Node # 哨兵头尾 self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): node.prev.next = node.next node.next.prev = node.prev def _add_to_head(self, node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def _move_to_head(self, node): self._remove(node) self._add_to_head(node) def _remove_tail(self): node = self.tail.prev self._remove(node) return node def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self._move_to_head(node) # 移到头部 return node.val def put(self, key, value): if key in self.cache: node = self.cache[key] node.val = value self._move_to_head(node) else: node = Node(key, value) self.cache[key] = node self._add_to_head(node) if len(self.cache) > self.cap: removed = self._remove_tail() del self.cache[removed.key]

# Java LinkedHashMap 实现 LRU class LRUCache extends LinkedHashMap<Integer, Integer> { private int capacity; public LRUCache(int capacity) { # accessOrder=true: 按访问顺序排序 super(capacity, 0.75f, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > capacity; } } # 原理： # LinkedHashMap 内部维护双向链表 # accessOrder=true → get/put 时将节点移到链表尾部 # removeEldestEntry → 链表头部是最久未使用的

class LFUCache: def __init__(self, capacity): self.cap = capacity self.min_freq = 0 self.key_to_val = {} # key → (val, freq) self.freq_to_keys = {} # freq → OrderedDict（按插入顺序） def _update_freq(self, key): val, freq = self.key_to_val[key] # 从旧频率中移除 del self.freq_to_keys[freq][key] if not self.freq_to_keys[freq]: del self.freq_to_keys[freq] if self.min_freq == freq: self.min_freq += 1 # 加入新频率 freq += 1 self.key_to_val[key] = (val, freq) if freq not in self.freq_to_keys: self.freq_to_keys[freq] = {} self.freq_to_keys[freq][key] = True def get(self, key): if key not in self.key_to_val: return -1 self._update_freq(key) return self.key_to_val[key][0] def put(self, key, value): if self.cap == 0: return if key in self.key_to_val: self.key_to_val[key] = (value, self.key_to_val[key][1]) self._update_freq(key) return if len(self.key_to_val) >= self.cap: # 淘汰最小频率中最久未使用的 old_key = next(iter(self.freq_to_keys[self.min_freq])) del self.freq_to_keys[self.min_freq][old_key] if not self.freq_to_keys[self.min_freq]: del self.freq_to_keys[self.min_freq] del self.key_to_val[old_key] self.key_to_val[key] = (value, 1) if 1 not in self.freq_to_keys: self.freq_to_keys[1] = {} self.freq_to_keys[1][key] = True self.min_freq = 1

# Redis 内存淘汰策略 # maxmemory-policy: # allkeys-lru: 所有 key 中淘汰 LRU（推荐） # volatile-lru: 有过期时间的 key 中淘汰 LRU # allkeys-lfu: 所有 key 中淘汰 LFU（Redis 4.0+） # volatile-lfu: 有过期时间的 key 中淘汰 LFU # 配置 maxmemory 256mb maxmemory-policy allkeys-lru # Redis LRU 近似实现 # 随机采样 N 个 key（默认 5），淘汰其中最久未使用的 # maxmemory-samples 10 # 提高精度但增加 CPU 开销