他的回复:
O(1) 的关键是「查得快」和「挪得快」各用一个结构负责：哈希表负责 O(1) 定位，双向链表负责 O(1) 摘除与插入。少任何一个都退化成 O(n)。 一、为什么必须是双向链表单链表删除节点要先找到前驱，那是 O(n)；数组移动元素同样是 O(n)。双向链表每个节点存 prev/next，删除时直接改前后指针，O(1)。所以 get 命中后要把节点挪到表头（表示最近使用），put 超容量时从表尾淘汰最久未使用的那个。 二、最短实现（Python，生产可用）```pythonfrom collections import OrderedDictimport threading class LRUCache: def __init__(self, capacity: int): self.cap = max(capacity, 0) self.d = OrderedDict() self.lock = threading.RLock() # OrderedDict 本身不是线程安全的 def get(self, key): with self.lock: if key not in self.d: return None self.d.move_to_end(key) # 命中即提到最近使用端 return self.d[key] def put(self, key, value): if self.cap == 0: return with self.lock: if key in self.d: self.d.move_to_end(key) self.d[key] = value if len(self.d) > self.cap: self.d.popitem(last=False) # 淘汰最久未使用````move_to_end` + `popitem(last=False)` 都是 O(1)，整体就是 O(1)。 三、手写版本（面试常考，也便于嵌入不支持有序字典的语言）```pythonclass Node: __slots__ = ('k', 'v', 'prev', 'next') def __init__(self, k=None, v=None): self.k, self.v = k, v self.prev = self.next = None class LRU: def __init__(self, cap): self.cap, self.size = cap, 0 self.head, self.tail = Node(), Node() # 两个哨兵，省掉大量判空 self.head.next, self.tail.prev = self.tail, self.head self.map = {} def _remove(self, n): n.prev.next, n.next.prev = n.next, n.prev def _add_front(self, n): n.prev, n.next = self.head, self.head.next self.head.next.prev = n self.head.next = n def get(self, k): if k not in self.map: return -1 n = self.map[k] self._remove(n); self._add_front(n) return n.v def put(self, k, v): if self.cap = 0: return n = self.map.get(k) if n: n.v = v self._remove(n); self._add_front(n) return n = Node(k, v) self.map[k] = n self._add_front(n) self.size += 1 if self.size > self.cap: old = self.tail.prev self._remove(old) del self.map[old.k] self.size -= 1``` 四、四个容易踩的边界1. **get 也要写**：命中后不挪到表头，就变成了 FIFO，命中率会明显下降。这是最常被写错的一处。2. **put 已存在的 key 不算新元素**：要更新值并挪到表头，size 不变，否则会误淘汰。3. **capacity = 0 / 负数**：要显式处理，否则 `popitem` 会对空表抛异常。4. **线程安全**：Python 里 OrderedDict 的复合操作（判断 + 取值 + 移动）不是原子的，必须加锁；Java 单锁版可直接参考 `LinkedHashMap(accessOrder=true)` 覆写 `removeEldestEntry`，但高并发下锁竞争明显。 五、并发场景的现实取舍- **分段锁**：按 key 哈希分 N 个桶，各自一把锁+一条链表，锁竞争降到 1/N，代价是全局淘汰顺序不精确。Guava Cache 就是这么做的。- **近似 LRU**：Redis 的 `allkeys-lru` 并不维护全局链表，而是每次随机采样若干个 key，淘汰其中最久未用的，换取内存与吞吐。所以 Redis 的 LRU 是「近似」的，命中率略低于严格 LRU。- **读多写多会放大争用**：每次 get 都要改链表指针，本质是写操作。高 QPS 下可以考虑 CLOCK / 二次机会算法，用访问位替代链表移动。 六、怎么验证与调优- 单测至少覆盖：容量 0、重复 put、命中后顺序变化、连续淘汰。- 统计 `hits / (hits + misses)`，别只看平均值；把命中率和容量画成曲线，能判断容量该加到多少。- 缓存击穿要配「单飞」（同一 key 只放一个请求去回源），否则 O(1) 的 LRU 挡不住数据库被打穿。 一句话总结：哈希表管定位、双向链表管顺序、哨兵节点省判空、get 也要移动节点；容量、并发和淘汰精度才是真正决定线上效果的三个变量。
