### 使用 `OrderedDict` 实现 LRU 缓存 Python 的 `collections` 模块提供了 `OrderedDict` 类型，它是一个有序字典，可以记住键值对插入的顺序。利用这一特性，可以非常简洁地实现 LRU（Least Recently Used）缓存机制。 #### 原理说明 `OrderedDict` 通过维护一个双向链表来记录键值对的插入顺序，因此可以在 `O(1)` 时间复杂度内实现键的移动和删除操作。每次访问一个键时，可以将其移动到字典的末尾，表示该键为“最近使用”的键；而当缓存容量达到上限时，将字典中最前面的键删除，即移除“最久未使用”的键。 #### 示例代码 ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cache = OrderedDict() self.capacity = capacity def get(self, key: int) -> int: if key not in self.cache: return -1 else: # 将该键移动到末尾，表示最近使用过 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) -> None: if key in self.cache: # 更新值并移动到末尾 self.cache.move_to_end(key) self.cache[key] = value # 如果超出容量，删除最久未使用的项（即第一个项） if len(self.cache) > self.capacity: self.cache.popitem(last=False) ``` #### 使用说明 - `get(key)`：如果缓存中存在该键，返回其对应的值，并将其标记为最近使用；否则返回 `-1`。 - `put(key, value)`：如果键已存在，则更新其值并标记为最近使用；如果不存在，则添加新键值对。若缓存已满，则自动删除最久未使用的键（即字典中最前面的键）。 这种实现方式相比手动维护双向链表更加简洁，且代码可读性更强。同时，由于 `OrderedDict` 是标准库的一部分，因此具有良好的性能和稳定性。 #### 性能特点 - 时间复杂度：`get` 和 `put` 操作均为 `O(1)`。 - 空间复杂度：`O(capacity)`，取决于缓存的最大容量。 #### 适用场景 - 网络请求结果缓存 - 数据库查询优化 - 页面置换算法模拟 - 文件系统缓存管理