玉林市网站建设_网站建设公司_搜索功能_seo优化

Java版LeetCode热题100之「LRU 缓存」详解

本文约9200字，全面深入剖析 LeetCode 第146题《LRU 缓存》。涵盖题目解析、哈希表+双向链表解法、复杂度分析、面试高频问答、实际开发应用场景、相关题目推荐等，助你彻底掌握缓存淘汰算法的核心实现技巧。

一、原题回顾

题目描述：
请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。

实现LRUCache类：

• LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存
• int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回 -1
• void put(int key, int value)
  • 如果关键字key已经存在，则变更其数据值value
  • 如果不存在，则向缓存中插入该组key-value
  • 如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字

约束条件：

• 函数get和put必须以O(1) 的平均时间复杂度运行

示例：

输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10⁵
• 最多调用2 * 10⁵次get和put

二、原题分析

LRU（Least Recently Used）缓存是一种经典的缓存淘汰策略，核心思想是：当缓存满时，优先淘汰最久未使用的数据。

核心挑战：

1. 快速查找：需要 O(1) 时间判断 key 是否存在
2. 快速更新使用顺序：每次访问都要将数据标记为"最近使用"
3. 快速淘汰：当容量超限时，快速找到并删除最久未使用的数据
4. O(1) 时间复杂度：所有操作必须在常数时间内完成

关键观察：

• 哈希表：提供 O(1) 的 key 查找能力
• 双向链表：提供 O(1) 的节点移动和删除能力
• 组合使用：哈希表存储 key → 节点的映射，双向链表维护使用顺序

📌为什么需要双向链表？

• 单向链表无法 O(1) 删除任意节点（需要前驱指针）
• 双向链表可以 O(1) 删除任意位置的节点

三、答案构思

核心数据结构设计

1. 双向链表节点定义：

classDLinkedNode{intkey;intvalue;DLinkedNodeprev;// 前驱指针DLinkedNodenext;// 后继指针}

2. 整体结构：

• 头部：最近使用的数据
• 尾部：最久未使用的数据
• 哈希表：Map<Integer, DLinkedNode>，快速定位节点

3. 操作流程：

get(key) 操作：

1. 哈希表查找 key
2. 不存在 → 返回 -1
3. 存在 → 将对应节点移动到头部 → 返回 value

put(key, value) 操作：

1. 哈希表查找 key
2. key 存在：
   • 更新 value
   • 移动节点到头部
3. key 不存在：
   • 创建新节点
   • 添加到头部
   • 添加到哈希表
   • 检查容量：
     • 超出 → 删除尾部节点 + 哈希表中对应项

辅助方法设计：

• addToHead(node)：添加节点到头部
• removeNode(node)：删除指定节点
• moveToHead(node)：移动节点到头部（删除 + 添加）
• removeTail()：删除尾部节点并返回

💡伪头尾节点技巧：使用 dummy head 和 dummy tail 简化边界处理

四、完整答案（Java 实现）

/** * LRU 缓存实现 */publicclassLRUCache{/** * 双向链表节点 */classDLinkedNode{intkey;intvalue;DLinkedNodeprev;DLinkedNodenext;publicDLinkedNode(){}publicDLinkedNode(intkey,intvalue){this.key=key;this.value=value;}}// 哈希表：key -> 节点privateMap<Integer,DLinkedNode>cache;// 当前缓存大小privateintsize;// 缓存容量privateintcapacity;// 伪头部和伪尾部节点privateDLinkedNodehead;privateDLinkedNodetail;/** * 构造函数 */publicLRUCache(intcapacity){this.size=0;this.capacity=capacity;this.cache=newHashMap<>();// 初始化伪头尾节点this.head=newDLinkedNode();this.tail=newDLinkedNode();head.next=tail;tail.prev=head;}/** * 获取缓存值 */publicintget(intkey){DLinkedNodenode=cache.get(key);if(node==null){return-1;}// 移动到头部（标记为最近使用）moveToHead(node);returnnode.value;}/** * 插入或更新缓存 */publicvoidput(intkey,intvalue){DLinkedNodenode=cache.get(key);if(node==null){// key 不存在，创建新节点DLinkedNodenewNode=newDLinkedNode(key,value);cache.put(key,newNode);addToHead(newNode);size++;// 检查容量限制if(size>capacity){// 删除尾部节点（最久未使用）DLinkedNodetailNode=removeTail();cache.remove(tailNode.key);size--;}}else{// key 存在，更新值并移动到头部node.value=value;moveToHead(node);}}/** * 添加节点到头部 */privatevoidaddToHead(DLinkedNodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}/** * 删除指定节点 */privatevoidremoveNode(DLinkedNodenode){node.prev.next=node.next;node.next.prev=node.prev;}/** * 移动节点到头部 */privatevoidmoveToHead(DLinkedNodenode){removeNode(node);addToHead(node);}/** * 删除尾部节点并返回 */privateDLinkedNoderemoveTail(){DLinkedNoderes=tail.prev;removeNode(res);returnres;}}

五、代码分析

1. 伪头尾节点的作用

// 初始化head=newDLinkedNode();tail=newDLinkedNode();head.next=tail;tail.prev=head;

优势：

• 避免空指针异常
• 统一处理插入/删除逻辑
• 无需特殊处理头尾边界情况

链表结构示意图：

head <-> [最近使用] <-> ... <-> [最久未使用] <-> tail

2. addToHead 方法详解

privatevoidaddToHead(DLinkedNodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}

执行步骤：

1. node.prev = head→ 节点前驱指向 head
2. node.next = head.next→ 节点后继指向原第一个数据节点
3. head.next.prev = node→ 原第一个数据节点的前驱指向新节点
4. head.next = node→ head 的后继指向新节点

效果：新节点成为第一个数据节点

3. removeNode 方法详解

privatevoidremoveNode(DLinkedNodenode){node.prev.next=node.next;node.next.prev=node.prev;}

执行步骤：

1. 前驱节点的 next 指向后继节点
2. 后继节点的 prev 指向前驱节点
3. 被删除节点从链表中断开

关键：双向链表才能实现 O(1) 删除任意节点

4. 容量控制逻辑

if(size>capacity){DLinkedNodetailNode=removeTail();cache.remove(tailNode.key);size--;}

淘汰策略：总是删除 tail.prev（最久未使用的数据）

六、时间复杂度和空间复杂度分析

空间复杂度：O(capacity)

• 哈希表最多存储capacity个键值对
• 双向链表最多存储capacity个节点
• 伪头尾节点占用常数空间

✅完全满足题目要求的 O(1) 时间复杂度！

七、常见问题解答（FAQ）

Q1：为什么不能只用哈希表？

答：
哈希表虽然提供 O(1) 查找，但无法维护使用顺序。
当需要淘汰数据时，无法知道哪个是最久未使用的。
必须配合链表来维护访问顺序。

Q2：为什么不能只用双向链表？

答：
双向链表虽然能维护顺序，但查找特定 key 需要 O(n) 时间遍历。
无法满足 O(1) 查找的要求。
必须配合哈希表来快速定位节点。

Q3：能否用 LinkedHashMap 实现？

答：可以，但不符合面试要求！

classLRUCacheextendsLinkedHashMap<Integer,Integer>{privateintcapacity;publicLRUCache(intcapacity){super(capacity,0.75F,true);// accessOrder = truethis.capacity=capacity;}@OverrideprotectedbooleanremoveEldestEntry(Map.Entry<Integer,Integer>eldest){returnsize()>capacity;}}

面试官期望：考察你对底层数据结构的理解，而不是 API 调用。

Q4：如果 key 为负数怎么办？

答：
题目已限定0 <= key <= 10000，所以无需考虑负数。
但在实际工程中，应该使用能处理任意整数的哈希表（Java HashMap 支持）。

八、优化思路

1. 线程安全版本

在多线程环境下，需要加锁：

publicsynchronizedintget(intkey){// ...}publicsynchronizedvoidput(intkey,intvalue){// ...}

缺点：性能下降
改进：使用读写锁或分段锁

2. 内存优化

• 使用LinkedHashMap的内部实现（但面试不推荐）
• 对于大量小对象，考虑对象池减少 GC 压力

3. 扩展功能

• TTL（Time To Live）：支持过期时间
• 统计信息：记录命中率、访问次数等
• 批量操作：支持批量 get/put

4. 工程化增强

// 输入校验publicvoidput(intkey,intvalue){if(capacity<=0){thrownewIllegalStateException("Capacity must be positive");}// ... 原逻辑}// 单元测试@TestvoidtestLRUCache(){LRUCachecache=newLRUCache(2);cache.put(1,1);cache.put(2,2);assertEquals(1,cache.get(1));cache.put(3,3);assertEquals(-1,cache.get(2));}

九、数据结构与算法基础知识点回顾

1. LRU 缓存原理

• 核心思想：最近使用的数据更可能再次被使用
• 淘汰策略：当缓存满时，淘汰最久未使用的数据
• 应用场景：操作系统页面置换、数据库缓存、Web 缓存

2. 哈希表（HashMap）

• 时间复杂度：平均 O(1) 查找/插入/删除
• 空间复杂度：O(n)
• Java 实现：基于数组 + 链表/红黑树

3. 双向链表

• 特点：每个节点有 prev 和 next 指针
• 优势：O(1) 插入/删除任意位置
• 劣势：额外的内存开销（prev 指针）

4. 伪节点技巧（Dummy Node）

• 作用：简化边界条件处理
• 应用：链表反转、合并、删除等操作
• 优势：避免大量 null 检查

十、面试官提问环节（模拟）

❓ 问题1：你的实现中，如果并发调用 get 和 put 会有什么问题？

回答：
会出现线程安全问题：

• 哈希表可能处于不一致状态
• 链表指针可能出现错乱
• size 计数可能不准确

解决方案：

1. 简单方案：给 get 和 put 方法加 synchronized
2. 优化方案：使用 ReadWriteLock，get 用读锁，put 用写锁
3. 高级方案：参考 ConcurrentHashMap 的分段锁思想

❓ 问题2：为什么选择双向链表而不是其他数据结构？

回答：
对比几种方案：

数据结构	查找	删除任意元素	移动到头部
数组	O(1)	O(n)	O(n)
单向链表	O(n)	O(n)	O(1)
双向链表	O(1)*	O(1)	O(1)

*配合哈希表实现 O(1) 查找

双向链表是唯一能同时满足 O(1) 删除任意元素和 O(1) 移动到头部的数据结构。

❓ 问题3：如果要求实现 LFU（最不经常使用）缓存，思路是什么？

回答：
LFU 需要维护每个 key 的访问频次，比 LRU 更复杂：

核心思路：

1. 哈希表1：key → (value, frequency)
2. 哈希表2：frequency → 双向链表（存储相同频次的 key）
3. 维护最小频次 minFreq

操作：

• get：频次+1，从旧频次链表移到新频次链表
• put：如果容量满，删除 minFreq 链表的尾部

时间复杂度：O(1)（需要精心设计数据结构）

❓ 问题4：你的实现空间复杂度真的是 O(capacity) 吗？

回答：
是的。具体分析：

• 哈希表：最多存储 capacity 个 entry
• 双向链表：最多存储 capacity 个数据节点 + 2 个伪节点
• 其他变量：常数空间

所以总空间复杂度是 O(capacity)，符合缓存的预期行为。

十一、这道算法题在实际开发中的应用

LRU 缓存是计算机科学中最经典、应用最广泛的算法之一：

1.操作系统 - 页面置换

• 虚拟内存管理中，当物理内存不足时，需要将某些页面换出到磁盘
• LRU 是常用的页面置换算法之一
• 虽然精确 LRU 实现代价高，但有近似算法（如 Clock 算法）

2.数据库系统 - Buffer Pool

• 数据库将磁盘页缓存在内存中
• 使用 LRU 或其变种（如 LRU-K）管理缓存页
• 提高查询性能，减少磁盘 I/O

3.Web 开发 - HTTP 缓存

• 浏览器缓存、CDN 缓存都使用 LRU 策略
• Redis、Memcached 等缓存系统内置 LRU 淘汰策略
• Spring Cache 也支持 LRU 缓存实现

4.移动开发 - 图片缓存

• Android 的 LruCache 类就是 LRU 缓存的标准实现
• 用于缓存 Bitmap，避免频繁加载图片导致 OOM
• Glide、Picasso 等图片加载库都基于 LRU 缓存

💡核心价值：理解时间和空间的权衡，这是系统设计的基础。

十二、相关题目推荐

掌握本题后，可挑战以下 LeetCode 题目：

建议先掌握基础数据结构操作，再挑战复杂的系统设计题。

十三、总结与延伸

✅ 本题核心收获

1. LRU 原理：最近最少使用淘汰策略
2. 数据结构组合：哈希表 + 双向链表的经典应用
3. O(1) 操作实现：通过精心设计数据结构达到性能要求
4. 伪节点技巧：简化链表操作的边界处理

🔮 延伸思考

• 近似 LRU：在大规模系统中，精确 LRU 代价太高，常用近似算法
• 分布式 LRU：如何在分布式环境中实现一致性 LRU 缓存？
• 硬件实现：CPU 缓存、TLB 等硬件缓存如何实现 LRU？

🌟 最后建议

• 手写代码：在白板上完整写出双向链表操作
• 讲清思路：面试时先解释 LRU 原理，再说明数据结构选择
• 主动讨论：提出线程安全、扩展性等工程考虑，展现深度

“缓存虽小，学问很大；LRU 之道，在于平衡。”
掌握本题，你就拥有了设计高效缓存系统的基础。继续前行，系统设计之路越走越宽！