2. 环境准备与核心数据结构选型
LRU 缓存的工程实现依赖语言提供的有序容器或自建数据结构。本章对比三种主流选型，并给出节点与映射的通用设计规范，为后续容量控制与防泄漏代码打下基础。
2.1 三种实现路径概览
| 方案 | 核心容器 | 适用场景 | 复杂度 | 内存开销 |
|---|---|---|---|---|
| Java LinkedHashMap | HashMap + 双向链表 | 快速原型、单机轻量缓存 | O(1) | 中等（额外链表指针） |
| Python OrderedDict | 哈希表 + 双向链表 | 快速原型、数据处理管线 | O(1) | 中等（额外链表指针） |
| 自建双链表+哈希表 | 自定义 Node + HashMap | 高性能、细粒度控制、全平台 | O(1) | 低（节点复用，无额外抽象层） |
前两种方案利用语言标准库的 accessOrder / move_to_end 特性，在小型应用中可快速交付；自建方案则适合对缓存淘汰策略、内存分布、并发锁粒度有严格要求的场景。
2.2 节点与映射设计
无论采用哪种实现，LRU 缓存的核心数据模型始终围绕 节点（Node） 和 映射（Map） 展开。节点承载键值对与链表指针，映射提供 O(1) 定位。
2.2.1 节点结构
单向 vs 双向：LRU 需要在删除尾部节点后快速定位前一节点，因此必须使用双向链表。单向链表无法在 O(1) 完成尾部删除后的前驱更新。
以下为通用节点数据结构（伪代码，语言无关）：
class Node<K, V> {
K key;
V value;
Node prev; // 前驱指针
Node next; // 后继指针
}
Java 与 Python 标准库的内部节点更复杂（包含哈希桶链等），但核心字段一致。自建方案可直接暴露此结构，便于内存池复用。
2.2.2 哈希映射设计
映射的职责：从 Key 直接定位到链表节点，避免遍历链表。映射的值必须是节点引用，而非简单的布尔值或索引。
Map<K, Node<K, V>> cache = new HashMap<>(); // Java
cache: Dict[K, Node[K, V]] // Python 类型标注
常见错误：映射只存
Boolean 或 Integer 表示存在性，淘汰时只能遍历整个链表——这将使 get/put 退化到 O(n)，完全违背 LRU 初衷。
2.3 语言框架选型对比明细
| 特性 | Java LinkedHashMap | Python OrderedDict | 自建双链表+哈希表 |
|---|---|---|---|
| 链表方向 | 双向 | 双向 | 双向 |
| 访问顺序支持 | 构造参数 accessOrder=true | .move_to_end(key) | 手动移动到头 |
| 自动淘汰 | 重写 removeEldestEntry() | 无，需手动 popitem(last=False) | 无，自维护链表长度 |
| 线程安全 | 需外部同步 / Collections.synchronizedMap | 需外部锁 / threading.Lock | 可集成读写锁分段锁 |
| 迭代稳定性 | 头->尾按访问顺序 | 保持插入顺序或移动顺序 | 完全可控 |
| 空间开销（每节点） | 约 40 + 指针（JVM 依赖） | 约 72 + 指针（CPython 对象头） | 仅 key+value+2指针 |
选型建议：课程后续所有代码示例采用 自建双链表+哈希表 方案，因为该方案暴露完整实现细节，便于理解容量控制边界和内存泄漏根源。若你仅需快速集成，可参考对照表格切换到语言标准库方案。
2.4 数据结构完整关系图
下面 SVG 展示了自建方案中哈希表与双向链表的协作关系：哈希表存放 key→node 映射，链表维护访问顺序（表头为最近使用，表尾为最久未使用）。
2.5 初始化步骤清单
- 确定容量上限：整型
capacity，后续所有淘汰检查均基于该值。 - 创建哨兵节点：
head和tail，初始互相连接head.next = tail; tail.prev = head。 - 初始化空哈希映射：负载因子、初始容量按预期节点数设定，避免频繁 rehash 影响延迟。
- 可选：统计计数器：
hitCount/missCount用于后续调试。
2.6 防泄漏前置检查点
防泄漏红线：自建方案中，若删除节点后未同时从映射中移除 Key→Node 条目，该节点虽不在链表中，但仍在堆上被映射引用——内存泄漏。务必在删除节点时同步执行
map.remove(node.key)。Java LinkedHashMap / Python OrderedDict 的迭代器弱引用处理也有类似隐患，显式清理可根治。