数据结构==LRU Cache ==

一、基础知识铺垫

（一）缓存的基础概念

1. 缓存定义：缓存是一种高速数据存储层，用于临时存储频繁访问的数据，减少对底层慢速存储（如数据库、磁盘）的访问，从而提升系统性能。
2. 缓存的核心需求：
   • 快速访问：读取数据的时间复杂度尽可能低（理想为 O (1)）。
   • 快速更新：插入、删除、修改数据的时间复杂度尽可能低（理想为 O (1)）。
   • 容量限制：缓存空间有限，当容量满时需通过缓存替换算法淘汰部分数据。
3. 缓存的常见应用：Redis 缓存、CPU 缓存、浏览器缓存、MyBatis 一级缓存等。

（二）常见缓存替换算法（对比理解 LRU）

（三）核心数据结构基础（哈希表 + 双向链表）

1. 哈希表（HashMap，Java）

• 特性：基于哈希表实现，存储键值对（key-value），支持查找、插入、删除操作，时间复杂度均为 O (1)（理想情况，无哈希冲突）。
• 局限性：无序性，无法记录数据的访问顺序，单独使用无法实现 LRU 策略。

2. 单向链表

• 特性：有序结构，可记录数据顺序，插入 / 删除操作在已知节点时为 O (1)。
• 局限性：
  • 查找节点需遍历链表，时间复杂度 O (n)。
  • 删除节点时需找到前驱节点，时间复杂度 O (n)。

3. 双向链表

• 特性：在单向链表基础上增加prev指针，可直接获取前驱节点。
• 优势：删除 / 移动节点时，通过prev指针直接定位前驱，时间复杂度 O (1)。
• 局限性：查找节点仍需遍历链表，时间复杂度 O (n)。

二、LRU Cache 核心原理（重点）

（一）核心目标

实现一个支持O (1) 时间复杂度的查找、插入、删除、移动操作的缓存，且遵循 “最近最少使用” 的淘汰策略。

（二）数据结构选型：哈希表 + 双向链表（核心重点）

1. 组合逻辑：
   • 哈希表：存储key -> 双向链表节点的映射，实现O (1) 查找节点。
   • 双向链表：存储节点的访问顺序，实现O (1) 插入、删除、移动节点。
2. 组合优势：弥补单一数据结构的局限性，满足 LRU Cache 的所有性能需求。
3. 链表节点的顺序规则：
   • 双向链表的尾部存储 ** 最近使用（MRU）** 的节点。
   • 双向链表的头部存储 ** 最近最少使用（LRU）** 的节点。
   • 访问 / 更新节点时，将节点移到链表尾部；容量满时，删除链表头部节点。

三、LRU Cache 代码实现（Java 版）与模块解析

（一）完整代码（带详细注释）

java

运行

import java.util.HashMap; import java.util.Map; /** * LRU Cache 实现：哈希表 + 双向链表（哑节点优化） * 核心逻辑：哈希表保证O(1)查找，双向链表保证O(1)插入/删除/移动 */ public class LRUCache { // 1. 双向链表节点类（静态内部类，仅当前类使用） static class DLinkedNode { int key; // 存储key：删除节点时需同步从哈希表移除，必须保存key（重点） int value; DLinkedNode prev; // 前驱节点 DLinkedNode next; // 后继节点 // 无参构造 public DLinkedNode() {} // 带参构造：初始化key和value public DLinkedNode(int key, int value) { this.key = key; this.value = value; } } // 2. LRUCache核心属性 private final int capacity; // 缓存容量（不可变，final修饰） private int size; // 当前缓存数据个数 private final Map<Integer, DLinkedNode> cache; // 哈希表：key -> 节点 private final DLinkedNode head; // 哑头节点（哨兵）：避免空指针（难点） private final DLinkedNode tail; // 哑尾节点（哨兵）：避免空指针（难点） // 3. 构造方法：初始化缓存容量、哈希表、双向链表 public LRUCache(int capacity) { // 参数校验：避免容量为0或负数（边界条件，补充优化） if (capacity <= 0) { throw new IllegalArgumentException("缓存容量必须大于0！"); } this.capacity = capacity; this.size = 0; this.cache = new HashMap<>(); // 初始化哑节点：head <-> tail（解决tail.prev为空的空指针问题，难点） this.head = new DLinkedNode(); this.tail = new DLinkedNode(); head.next = tail; tail.prev = head; } // 4. 私有辅助方法：双向链表的核心操作（封装细节，提高复用性） /** * 移除双向链表中的指定节点（通用操作，O(1)） * @param node 要移除的节点 */ private void removeNode(DLinkedNode node) { // 步骤：将节点的前驱和后继直接相连，跳过当前节点 node.prev.next = node.next; node.next.prev = node.prev; } /** * 将节点添加到双向链表的尾部（最近使用的位置，O(1)，难点：四指针修改） * @param node 要添加的节点 */ private void addToTail(DLinkedNode node) { // 步骤：先关联node与tail的前驱，再关联node与tail node.prev = tail.prev; node.next = tail; tail.prev.next = node; tail.prev = node; } /** * 将指定节点移动到链表尾部（访问/更新节点时调用，O(1)） * @param node 要移动的节点 */ private void moveToTail(DLinkedNode node) { removeNode(node); // 先从原位置移除 addToTail(node); // 再添加到尾部 } /** * 移除双向链表的头部节点（最近最少使用的节点，O(1)） * @return 被移除的节点（用于同步从哈希表删除key） */ private DLinkedNode removeHead() { DLinkedNode delNode = head.next; // 哑头的下一个节点是真正的头节点 removeNode(delNode); // 移除该节点 return delNode; } // 5. 公有方法：外部调用的get和put（核心业务方法，重点） /** * 获取key对应的value（不存在则返回-1，存在则将节点移到尾部） * @param key 要查找的key * @return 对应的value，不存在则返回-1 */ public int get(int key) { DLinkedNode node = cache.get(key); // 情况1：key不存在，返回-1 if (node == null) { return -1; } // 情况2：key存在，将节点移到尾部（标记为最近使用） moveToTail(node); return node.value; } /** * 插入/更新key-value对（核心逻辑：处理key存在/不存在，容量超限） * @param key 要插入/更新的key * @param value 对应的value */ public void put(int key, int value) { DLinkedNode node = cache.get(key); // 情况1：key不存在，新建节点 if (node == null) { DLinkedNode newNode = new DLinkedNode(key, value); // 步骤1：将新节点存入哈希表 cache.put(key, newNode); // 步骤2：将新节点添加到链表尾部 addToTail(newNode); // 步骤3：当前大小+1 size++; // 步骤4：判断是否超出容量，超出则移除最近最少使用的节点（头部） if (size > capacity) { DLinkedNode delNode = removeHead(); // 同步从哈希表删除该节点的key（必须用节点的key，重点） cache.remove(delNode.key); // 当前大小-1 size--; } } else { // 情况2：key存在，更新value并将节点移到尾部 node.value = value; moveToTail(node); } } // 辅助测试方法：打印缓存链表（调试用） public void printCache() { DLinkedNode cur = head.next; while (cur != tail) { System.out.print("(" + cur.key + ":" + cur.value + ") -> "); cur = cur.next; } System.out.println("null"); } // 主方法测试：验证LRU逻辑 public static void main(String[] args) { LRUCache lruCache = new LRUCache(2); // 容量为2 lruCache.put(1, 1); lruCache.printCache(); // 输出：(1:1) -> null lruCache.put(2, 2); lruCache.printCache(); // 输出：(1:1) -> (2:2) -> null System.out.println(lruCache.get(1)); // 输出：1，此时1移到尾部 lruCache.printCache(); // 输出：(2:2) -> (1:1) -> null lruCache.put(3, 3); // 容量满，移除最近最少使用的2 lruCache.printCache(); // 输出：(1:1) -> (3:3) -> null System.out.println(lruCache.get(2)); // 输出：-1（已被移除） lruCache.put(4, 4); // 容量满，移除最近最少使用的1 lruCache.printCache(); // 输出：(3:3) -> (4:4) -> null System.out.println(lruCache.get(1)); // 输出：-1（已被移除） System.out.println(lruCache.get(3)); // 输出：3，移到尾部 lruCache.printCache(); // 输出：(4:4) -> (3:3) -> null System.out.println(lruCache.get(4)); // 输出：4，移到尾部 lruCache.printCache(); // 输出：(3:3) -> (4:4) -> null } }

（二）模块解析（基础知识点）

1. 节点类（DLinkedNode）：静态内部类，存储key、value、prev、next，是双向链表的基本单元。
2. 核心属性：
   • capacity：缓存容量（final 修饰，保证不可变）。
   • size：当前缓存数据个数。
   • cache：哈希表，映射 key 到节点。
   • head/tail：哑头 / 哑尾节点，简化链表操作。
3. 构造方法：初始化属性，将哑头和哑尾相互指向，解决空指针问题。
4. 辅助方法：封装双向链表的移除、添加、移动、删除头部节点操作，提高代码复用性。
5. 业务方法：get（获取数据）、put（插入 / 更新数据），实现 LRU 核心逻辑。
6. 测试方法：printCache（打印链表）、main（验证逻辑）。

四、重难点专项拆解（重点 + 难点标注）

（一）重点知识点（必须掌握）

1. 数据结构组合的必要性（核心重点）

• 问题：为什么必须用哈希表 + 双向链表？
  • 单一哈希表：无法记录访问顺序，无法实现 LRU 淘汰策略。
  • 单一双向链表：查找节点需遍历（O (n)），性能不足。
  • 组合后：哈希表实现 O (1) 查找，双向链表实现 O (1) 插入 / 删除 / 移动，满足 LRU 性能需求。

2. 节点中存储key的必要性（易忽略重点）

• 原因：当缓存容量满时，需要删除链表头部节点，同时同步从哈希表中删除对应的 key。如果节点只存储value，无法获取 key，哈希表的删除操作无法完成。
• 代码体现：DLinkedNode类中的int key属性，removeHead()方法返回节点后，通过delNode.key删除哈希表中的键值对。

3.get/put方法的核心逻辑（业务重点）

（1）get方法逻辑

• 步骤 1：通过哈希表查找节点，不存在则返回 -1。
• 步骤 2：存在则将节点移到链表尾部（标记为最近使用），返回 value。
• 关键：访问节点后必须移动到尾部，否则淘汰策略失效。

（2）put方法逻辑

• 场景 1：key 不存在
  1. 新建节点，存入哈希表。
  2. 将节点添加到链表尾部。
  3. 大小size++。
  4. 若size > capacity，删除链表头部节点，同步删除哈希表中的 key，size--。
• 场景 2：key 存在
  1. 更新节点的 value。
  2. 将节点移到链表尾部。
• 关键：步骤顺序不能颠倒（如先存哈希表再添加到链表，避免数据不一致）。

4. 时间 / 空间复杂度分析（性能重点）

• 时间复杂度：get/put方法的所有操作均为 O (1)（哈希表操作 + 链表操作）。
• 空间复杂度：O (capacity)（哈希表和链表存储的节点数不超过容量）。

（二）难点知识点（易出错、理解困难）

1. 哑节点（哨兵节点）的设计与使用（核心难点）

• 问题背景：若直接使用真实节点作为头 / 尾，链表为空时，head/tail为null，调用head.next或tail.prev会触发空指针异常（如会议中提到的addToTail方法中tail.prev为空的问题）。
• 解决方案：定义head（哑头）和tail（哑尾）两个虚拟节点，初始化时让head.next = tail、tail.prev = head，真实节点均在两者之间。
• 优势：无需处理链表为空的边界情况，所有真实节点的操作逻辑统一，避免空指针异常。

2. 双向链表的四指针修改（addToTail方法，操作难点）

• 问题：将节点添加到链表尾部时，需要修改四个指针，顺序错误会导致链表断裂。
• 正确步骤（代码注释已标注）：
  1. node.prev = tail.prev;（节点的前驱指向 tail 的前驱）。
  2. node.next = tail;（节点的后继指向 tail）。
  3. tail.prev.next = node;（tail 的前驱的后继指向节点）。
  4. tail.prev = node;（tail 的前驱指向节点）。
• 记忆技巧：先关联节点与原有链表的节点，再修改原有链表的指针。

3. 边界条件处理（调试难点）

• 边界 1：缓存容量为 1
  • 测试点：每次新增节点都会淘汰唯一的旧节点，验证淘汰策略是否正确。
• 边界 2：缓存容量为 0 / 负数
  • 解决方案：在构造方法中添加参数校验，抛出非法参数异常（代码中已补充）。
• 边界 3：重复插入相同 key
  • 解决方案：put方法中判断 key 存在时，更新 value 并移动节点（代码中已处理）。
• 边界 4：链表为空 / 只有一个节点
  • 解决方案：哑节点的存在，使得这些情况的处理逻辑与普通情况一致，无需额外判断。

五、拓展知识与实战思考（扩充内容）

（一）Java 自带的 LRU 实现：LinkedHashMap

1. LinkedHashMap 特性：继承自 HashMap，底层是哈希表 + 双向链表，支持按插入顺序或按访问顺序遍历。
2. 实现 LRU 的核心：重写removeEldestEntry方法，当方法返回true时，LinkedHashMap 会自动删除最久未使用的节点。
3. 示例代码：

   java

   运行

   import java.util.LinkedHashMap; import java.util.Map; public class LRUCacheByLinkedHashMap extends LinkedHashMap<Integer, Integer> { private final int capacity; public LRUCacheByLinkedHashMap(int capacity) { // 初始化：初始容量16，负载因子0.75，按访问顺序排序（第三个参数为true） super(16, 0.75f, true); this.capacity = capacity; } // 重写方法：当节点数超过容量时，返回true，自动删除最久未使用的节点 @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; } // 测试 public static void main(String[] args) { LRUCacheByLinkedHashMap lru = new LRUCacheByLinkedHashMap(2); lru.put(1, 1); lru.put(2, 2); System.out.println(lru.get(1)); // 访问1，移到尾部 lru.put(3, 3); // 容量满，删除2 System.out.println(lru.get(2)); // 返回null（或-1，可封装） } }

4. 注意：LinkedHashMap 是非线程安全的，多线程环境下需加锁或使用Collections.synchronizedMap包装。

（二）线程安全问题（实战难点）

• 问题：上述手写 LRUCache 代码在多线程环境下会出现数据不一致（如size计数错误、链表断裂、哈希表并发修改异常）。
• 解决方案：
  1. 简单方案：在get/put方法上加synchronized关键字（缺点：性能较低，同一时间只能有一个线程访问）。
  2. 优化方案：使用ConcurrentHashMap替代HashMap，结合ReentrantLock锁（分段锁，性能更高）。
  3. 工业方案：使用 Redis 的 LRU 缓存（Redis 内置了 LRU 淘汰策略，且支持分布式、线程安全）。

（三）LRU 的局限性与优化（拓展重点）

• 局限性：对突发的大量新数据访问不友好（如缓存穿透、缓存污染），可能导致常用数据被淘汰。
• 优化方案：
  1. LRU-K：记录节点的 K 次访问历史，淘汰最近 K 次访问中最久未访问的节点（K 通常取 2）。
  2. Two-Level LRU（2LRU）：将缓存分为活跃区和非活跃区，减少常用数据被淘汰的概率。
  3. LFU + LRU 混合：结合访问频率和访问时间，优化淘汰策略。

六、总结

LRU Cache 是算法与开发中的高频考点，核心在于哈希表 + 双向链表的组合使用，重点掌握数据结构的协同逻辑、get/put方法的业务逻辑，难点在于哑节点的设计和双向链表的指针操作。在实战中，需注意线程安全和边界条件处理，也可利用 Java 自带的 LinkedHashMap 快速实现 LRU，或使用 Redis 等中间件实现分布式缓存。