本题采用哈希双向链表复合结构解决满足 LRU最近最少使用淘汰策略的缓存设计问题。其核心本质是将哈希表的高效查找特性与双向链表的高效节点物理平移特性相结合实现数据随机访问与时序置换流的完全解耦。当前提供的源码实现了在读写操作get 和 put平均时间复杂度均为 O(1) 且额外空间复杂度为 O(capacity) 条件下的全局最优内存管理最终走向是高效动态维护数据热度并自动逐出最久未使用的键值对。一、 问题本质与数据模型在固定容量的缓存系统中LRU 策略要求当存储空间达到上限时优先淘汰最久未被访问的数据。传统的单一数据结构无法同时满足该算法的性能指标数组或单链表维持时序需要 O(N) 的移动或查找损耗而标准哈希表虽能提供 O(1) 的查找却无法维护元素间的访问先后顺序。为了破除单结构功能单一的物理瓶颈算法引入了“哈希双向链表Hash-BiLinkedList复合模型”哈希映射层Map以键key为索引存储对应链表节点Node的内存引用。通过哈希散列算法将随机检索的时间复杂度降低至常数阶 O(1)。环形双向链表层Doubly Linked List利用节点的前驱指针pre和后继指针next维系数据的时间热度拓扑。靠近头部的节点代表最近被激活的热数据靠近尾部的节点代表最久未被使用的冷数据。环形哨兵简化模型Dummy Sentinel源码引入了单一dummy节点构建双向循环链表使dummy.next恒指向逻辑头部dummy.pre恒指向逻辑尾部。这种闭环拓扑设计消除了头尾节点为空的边界判断实现了控制流的归一化。二、 算法演进对比在实现 LRU 缓存结构时不同复合形态的效率对比如下解法名称读写时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷数组哈希表计数法O(1) 读 / O(N) 写O(capacity)哈希表存数据数组存键每次读写通过移动数组元素或更新全局时间戳来重排热度淘汰或更新数据时数组需要大范围物理搬移写入操作发生线性阶退化单链表哈希指针法O(1) 读 / O(1) 写O(capacity)哈希表存储目标节点的前驱节点地址通过前驱完成单链表节点的断开与前移拓扑结构脆弱更新指针时需要小心维护“前驱的前驱”逻辑极易发生断裂哈希双向链表当前解法O(1) 读 / O(1) 写O(capacity)利用 Map 锁定节点利用双向引用原地 O(1) 断开并插入头部尾部节点自动沦为待淘汰点节点内部指针域翻倍每个节点包含两个物理指针产生稍高的指针内存开销三、 核心分支控制逻辑与决策证明当前源码的控制流高度依赖于私有辅助方法remove(Node)、front(Node)与getNode(key)的状态转移其控制逻辑证明如下1. 节点热度跃升机制getNode(int key)内部控制执行当命中key时连续执行remove(node); front(node);。物理证明双向链表的特异性在于已知节点指针x时可以在 O(1) 时间内通过x.pre.next x.next和x.next.pre x.pre将其从当前链表矩阵中完全剥离无需遍历。随后将其插入到dummy与dummy.next之间。结论无论是执行get访问数据还是执行put修改已有数据该机制都能确保被激活的数据无损平移至逻辑头部最新使用位置。2. 尾部冷数据淘汰分支put(int key, int value)容量超限执行当map.size() capacity时执行Node last dummy.pre; map.remove(last.key); remove(last);。数学证明因为所有新插入或被访问的节点都会被置于dummy.next头部随着新数据的涌入未被访问的节点会在拓扑空间上被不断向后推移。在环形结构中dummy.pre承载的节点必然是距离头部最远、即最久未被使用的节点。结论直接定位dummy.pre即可在 O(1) 时间内准确捕获淘汰目标并同步清除映射表与链表中的物理残留。四、 算法执行状态机步进示例以容量capacity 2为例输入指令序列的状态机演进与链表拓扑变化如下表所示其中D代表dummy哨兵节点步骤执行操作map 映射状态链表拓扑序列从头至尾核心置换决策与动作说明初始LRUCache(2){}D - D初始化环形单哨兵拓扑结构1put(1, 1){1-Node1}D - 1 - D插入节点 1将其移至dummy后方2put(2, 2){1-N1, 2-N2}D - 2 - 1 - D插入节点 2 至头部节点 1 沦为尾部冷数据3get(1){1-N1, 2-N2}D - 1 - 2 - D命中 1将 1 提升至头部2 移至尾部返回 14put(3, 3){1-N1, 3-N3}D - 3 - 1 - D插入 3 至头部容量超出逐出尾部dummy.pre即节点 25get(2){1-N1, 3-N3}D - 3 - 1 - DMap 中不包含键 2直接终止并返回 -1五、 源码实现import java.util.HashMap; import java.util.Map; class LRUCache { // 静态内部类定义双向链表节点拓扑模型 private static class Node { int key; int val; Node pre; Node next; Node(int key, int val) { this.key key; this.val val; } } // 环形哨兵节点dummy.next 为最热数据头dummy.pre 为最冷数据尾 private final Node dummy new Node(0, 0); private final int capacity; // 哈希映射表实现从 key 到链表节点引用地址的 O(1) 检索 private final MapInteger, Node map new HashMap(); public LRUCache(int capacity) { this.capacity capacity; // 初始化单哨兵闭环结构自循环 dummy.next dummy; dummy.pre dummy; } public int get(int key) { Node node getNode(key); // 若命中则返回真实值否则返回标准未找到状态码 -1 return (node ! null) ? node.val : -1; } public void put(int key, int value) { Node node getNode(key); // 分支 1键已存在更新其数值getNode 内部已完成热度提升 if (node ! null) { node.val value; return; } // 分支 2键不存在实例化新节点并建立物理映射 node new Node(key, value); map.put(key, node); front(node); // 将全新节点推入逻辑头部 // 边界越界控制若触发容量上限自动逐出最久未使用的尾部节点 if (map.size() capacity) { Node last dummy.pre; // 环形拓扑中dummy.pre 恒指向最老数据 map.remove(last.key); // 从映射表中剔除 remove(last); // 从双向链表中彻底断开 } } // 私有辅助方法获取节点并重置其时间戳位置 private Node getNode(int key) { if (!map.containsKey(key)) { return null; } Node node map.get(key); remove(node); // 原地脱离当前拓扑断点 front(node); // 重新挂载至链表最前端 return node; } // 核心物理级操作原地断开目标节点的双向链接 private void remove(Node x) { x.pre.next x.next; x.next.pre x.pre; } // 核心物理级操作将节点插入到 dummy 哨兵之后逻辑头部 private void front(Node x) { x.pre dummy; x.next dummy.next; x.pre.next x; x.next.pre x; } }六、 复杂度分析1. 时间复杂度O(1)分析get 操作包含一次 HashMap 的containsKey与get分散检索以及remove和front两个涉及 4 次指针重定向的常数阶原子操作。由于链表的操作完全依赖已知引用的就地修改耗时恒定。put 操作在更新数据时逻辑与get一致在插入新数据时若触发淘汰机制定位尾部节点通过dummy.pre即可在 O(1) 步内完成同时哈希表的移除亦为常数阶。结论读写数据流的平均与最坏时间损耗均为严格的常数阶 O(1)满足题目约束。2. 空间复杂度O(capacity)分析算法运行期间动态内存的开销主要由哈希映射表map和双向链表节点的物理数量决定。由于存在顶层越界截断控制map.size() capacity系统内存储的键值对节点数量上限被严格锁定为capacity 1。结论整体外部存储空间的资源消耗与系统设定的缓存容量呈严格的线性正比关系。