链表：空
哈希表：空

LRU缓存淘汰算法详解 题目描述 LRU（Least Recently Used，最近最少使用）缓存淘汰算法是一种常用的缓存管理策略。当缓存空间不足时，它会优先淘汰最久未被访问的数据。请你详细讲解LRU算法的核心思想、数据结构设计、操作流程以及时间复杂度分析。 核心思想与场景 想象一个图书馆书架空间有限，新书不断购入。管理员会决定哪些旧书移走：最近被借阅过的书可能更受欢迎应保留，而最久没人碰的书可能先被清理。这就是LRU的思想——基于访问时间局部性原理，认为最近被访问的数据更可能在短期内再次被访问。 数据结构设计 高效实现LRU需结合两种数据结构： 双向链表 ：存储缓存项，节点按访问时间排序。最近访问的节点在头部，最久未访问的在尾部。双向链表支持O(1)时间内在任意位置插入或删除节点。 哈希表 ：以缓存项的键为key，指向链表中对应节点的指针为value。支持通过键快速定位节点，实现O(1)时间查询。 操作流程分步解析 假设缓存容量为3，初始状态如下（链表头部表最近访问）： 步骤1：插入数据（put操作） 插入键值对 (1, A) 创建新节点 [ key=1, value=A ] 将节点插入链表头部：链表 → [ 1,A ] 哈希表记录映射：{1 → 节点地址} 结果：链表 [ 1,A ]（头部），哈希表 {1: 节点} 插入 (2, B) 和 (3, C) 依次插入头部，链表变为 [ 3,C] ↔ [ 2,B] ↔ [ 1,A ]（尾部），哈希表 {1: 节点1, 2: 节点2, 3: 节点3} 步骤2：访问数据（get操作） 查询 key=2（get(2)） 通过哈希表找到节点 [ 2,B ] 的地址 将节点从链表中原位置移除（断开前后链接） 重新插入链表头部 结果：链表变为 [ 2,B] ↔ [ 3,C] ↔ [ 1,A ]，表示key=2是最近访问的 步骤3：缓存淘汰（容量不足时） 插入新数据 (4, D)，此时缓存已满（容量=3） 定位链表尾部节点 [ 1,A ]（最久未访问） 移除该节点，同时在哈希表中删除 key=1 将新节点 [ 4,D ] 插入链表头部 结果：链表 [ 4,D] ↔ [ 2,B] ↔ [ 3,C ]，哈希表 {2: 节点2, 3: 节点3, 4: 节点4} 关键细节 双向链表必要性 ：删除节点时，需知道其前驱节点才能更新链接。单向链表无法直接获取前驱。 线程安全考虑 ：多线程环境下需加锁，但可能成为性能瓶颈。工业级实现（如Java的LinkedHashMap）会提供并发控制选项。 时间复杂度分析 get操作：哈希表查询O(1) + 链表移动O(1) = O(1) put操作：哈希表插入O(1) + 链表头部插入O(1) + （若淘汰）尾部删除O(1) = O(1) 所有操作均保证常数时间复杂度，符合高效缓存要求。 实际应用场景 数据库缓冲池（如InnoDB Buffer Pool） Redis内存淘汰策略选项之一 CPU高速缓存替换策略 浏览器本地存储管理 通过以上步骤，LRU算法将"最近使用"转化为链表顺序，用哈希表保证快速访问，实现了高效缓存管理。