因为deque不支持O(1)查找，单独使用会导致get/put退化为O(n)；需配合dict实现键值映射与快速定位，deque仅维护key访问顺序，二者协同达成平均O(1)。
为什么不用 collections.deque 直接实现 LRU？
因为 deque 本身不支持 O(1) 查找——LRU 的核心操作是「访问时移到队首」，这要求能快速定位某个 key 在队列中的位置。而 deque 查找是 O(n)，直接遍历移除再追加会退化成 O(n) 每次操作，失去 LRU 缓存的性能意义。
所以手写的关键不是“只用 deque”，而是「用 deque 存键顺序 + 用 dict 做键值映射和快速查找」——两者配合才能达成平均 O(1)。
如何用 deque + dict 实现 get / put 的 O(1)？
核心思路：用 dict 存 {key: value}，用 deque 存 key 的访问顺序（最新访问的在左端）。每次 get(key) 时，先查 dict，再把该 key 从 deque 中删掉并重插到左端；put(key, value) 类似，但要额外处理容量超限——当 len(dict) == capacity 且 key 不存在时，需从 deque 右端弹出最久未用的 key，并从 dict 中删除它。
注意：deque.remove(x) 是 O(n)，但只要缓存容量不大（比如几百以内），实际影响有限；若追求严格 O(1)，就得换链表+哈希，但题目明确要求“用 deque 手写”，这就已是合理妥协。
实操建议：
-
deque只存 key，不存 value，避免重复存储 - 每次
get成功后，先self.keys.remove(key)再self.keys.appendleft(key) -
put时若 key 已存在，只需更新dict值 + 调整deque中 key 位置，不删不增 - 若 key 不存在且已满，先
tail = self.keys.pop()，再del self.cache[tail]
deque.remove() 的坑：KeyError 和性能抖动
如果调用 remove() 时 key 不在 deque 中（比如因并发或逻辑错乱导致 dict 和 deque 状态不一致），会抛 ValueError: deque.remove(x): x not in deque。这不是 KeyError，容易误捕。
更隐蔽的问题是：即使你确保 key 存在，remove() 仍要遍历 deque 找匹配项。当缓存容量大（如 >10000）、且频繁 get/put 时，这部分开销会明显拖慢吞吐。这不是 bug，是设计使然。
规避建议：
- 不做「先 remove 再 appendleft」，改用「记录索引 + rotate」？不行——
deque不支持随机索引访问 - 接受 O(n) remove，但加一层保护：用
if key in self.keys:判断（注意：这个 in 对 deque 也是 O(n)，但比 remove 少一次遍历） - 真正高负载场景，应直接放弃纯 deque 方案，改用
OrderedDict或自定义双向链表
一个可直接跑的最小可行版本
以下代码满足题设“用 deque 手写”，无第三方依赖，兼容 Python 3.6+：
from collections import deque
<p>class LRUCache:
def <strong>init</strong>(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> value
self.keys = deque() # 从左到右：最新 → 最旧</p><pre class="brush:php;toolbar:false;">def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 移动 key 到队首
self.keys.remove(key)
self.keys.appendleft(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache[key] = value
self.keys.remove(key)
self.keys.appendleft(key)
else:
if len(self.cache) == self.capacity:
tail = self.keys.pop()
del self.cache[tail]
self.cache[key] = value
self.keys.appendleft(key)
这段代码没做线程安全、没压缩冗余逻辑，但它清晰暴露了 deque 在 LRU 中的真实角色：一个带顺序的、可手动维护的 key 栈。复杂点不在结构，而在「remove 后必须 appendleft」这个两步操作不能断；容易被忽略的是：哪怕只是 get，也得动 deque——否则顺序就错了。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
