题目重点：从 O(1) recency 更新到多线程锁范围，说明 AI 生成代码如何验证而不是只看能运行。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版固定非负 capacity，get 命中返回值并刷新最近使用、未命中返回 None；put 更新/插入后超过容量淘汰最久未用，capacity=0 永远为空。题目未明确缺失哨兵或 null value 语义。
- 训练代码用 OrderedDict+RLock 展示原子边界；若面试要求从零写 HashMap+双链表，应将同样锁范围包住 map 与 link 变动。
解题路线
- 单线程基线：map key→node、双链表按 recency 排序。get 命中需把节点从原位摘下插到尾端，put 更新也移动，满时删头端 LRU；每个动作平均 O(1)。
- 多线程 get 实际修改链表，不是纯读。至少需要一个锁覆盖‘查 map→摘/插节点’全过程；put 的查重、插入和淘汰也在同一锁。只给 map 上锁而链表无锁会破坏指针。
- 粗粒度互斥锁先保证单操作线性化，容量和 map/link 不变量在锁释放时一致。若读写竞争真成为瓶颈，再按 key 分片缓存；但全局精确 LRU 跨分片难维护，可能退化成每分片近似 LRU。
- AI 生成代码需独立验收：容量 0/1、重复 put、get 更新顺序、未命中、并发压力与不变量；AI 找 API 文档不等于验证实现。训练示例用 OrderedDict 省去链表模板，重点验证锁范围。
- 复合操作 `if get(k) is None: put(k,v)` 由两个原子方法组成，整体仍可能竞态；要提供 compute-if-absent 或调用者更高层锁。
手动走一遍
容量 2：put A、put B、get A、put C 后淘汰 B。若两个线程同时 get A 与 put C，锁保证每个操作完整排序；最终哪一个先发生由锁取得顺序决定，但内部容量始终≤2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import OrderedDict
from threading import RLock
class ThreadSafeLRU:
"""Each get/put is atomic; caller must coordinate multi-operation transactions."""
def __init__(self, capacity: int):
if capacity < 0:
raise ValueError("negative capacity")
self.capacity = capacity
self.data = OrderedDict()
self.lock = RLock()
def get(self, key):
with self.lock:
if key not in self.data:
return None
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
with self.lock:
if self.capacity == 0:
return
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
def snapshot(self):
with self.lock:
return list(self.data.items())
复杂度
平均 get/put O(1) 字典/链表操作，空间 O(C)；单锁下并发吞吐受临界区串行化限制，延迟可能受锁等待影响。训练代码 3,000 组顺序随机 oracle 与 8 线程容量不变量压力通过；该压力测试不构成严格线性化证明。
易错点与追问
容易失分的边界
- get 命中不刷新 recency。
- 只锁 put，不锁会移动链表的 get。
- 淘汰 map 与链表操作分开上锁。
- 容量 0 时仍插入。
- 多线程测试没有失败就宣称完整线性化证明。
继续深挖
- cache value 可为 None 时 miss 怎么表示？
- get-then-put 复合操作如何原子化？
- 如何减少单锁竞争？
- AI 生成代码有哪些最小独立测试必须跑？
