文章目录
- 1. 什么是 LRU？为什么需要它？
- 2. 标准版 LRU 实现 (LeetCode 146)
- 单 Dummy 节点环形链表
- 3. 进阶版：带过期时间 (TTL) 的 LRU 缓存
- 设计思路：惰性删除 (Lazy Expiration)
- Java 代码实现 (LRU Cache with TTL)
- 进阶思考：还有优化的空间吗？
- 4. 总结
1. 什么是 LRU？为什么需要它？
LRU（Least Recently Used）即“最近最少使用”淘汰算法。
缓存的容量通常是有限的，当缓存满了，我们需要决定删掉哪个数据来腾出空间。LRU 的核心思想是：“如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。”因此，当空间不足时，最久没有被访问的数据会被淘汰。
实现 LRU 缓存，我们需要保证get（查询）和put（写入）的时间复杂度都是O ( 1 ) O(1)O(1)。
2. 标准版 LRU 实现 (LeetCode 146)
为了达到O ( 1 ) O(1)O(1)的时间复杂度，我们需要结合两种数据结构：
- 哈希表 (HashMap)：保证O ( 1 ) O(1)O(1)的查找时间。
- 双向链表 (Doubly Linked List)：保证O ( 1 ) O(1)O(1)的节点移动和删除时间。将最近使用的节点移到链表头部，最久未使用的节点自然就被挤到了链表尾部。
单 Dummy 节点环形链表
在传统的做法中，往往需要定义head和tail两个虚拟节点。但我在这里采用了单 Dummy 节点构建环形双向链表的做法。dummy.prev就是链表的尾节点（最久未使用），dummy.next就是链表的头节点（最新使用）。这让插入和删除的代码极其简洁，完美避开了各种null指针的判断逻辑！
classLRUCache{// 定义双向链表节点classNode{intkey,value;Nodeprev,next;Node(intk,intv){this.key=k;this.value=v;}}privatefinalintcapacity;// 核心技巧：单一虚拟节点构建环形双向链表Nodedummy=newNode(0,0);Map<Integer,Node>map=newHashMap<>();publicLRUCache(intcapacity){this.capacity=capacity;// 初始化环形链表，自己指向自己dummy.prev=dummy;dummy.next=dummy;}publicintget(intkey){Nodenode=find(key);returnnode!=null?node.value:-1;}publicvoidput(intkey,intvalue){Nodenode=map.get(key);// 如果节点已存在，更新值，并把它移到头部if(node!=null){node.value=value;find(key);// 复用 find 方法中的移到头部逻辑return;}// 如果节点不存在，创建新节点并加入node=newNode(key,value);map.put(key,node);putFront(node);// 判断是否超容，超容则淘汰最久未使用的节点（即 dummy 的前驱节点）if(map.size()>capacity){Nodetemp=dummy.prev;// 环形链表的尾节点map.remove(temp.key);remove(temp);}}// 辅助方法：查找节点，并将其移动到链表头部（表示最近使用过）privateNodefind(intkey){if(!map.containsKey(key)){returnnull;}Nodetemp=map.get(key);remove(temp);// 先从原位置拔出putFront(temp);// 再插入到头部returntemp;}// 辅助方法：从双向链表中删除节点privatevoidremove(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}// 辅助方法：将节点插入到头部（dummy 之后）privatevoidputFront(Nodenode){node.prev=dummy;node.next=dummy.next;node.next.prev=node;node.prev.next=node;}}3. 进阶版：带过期时间 (TTL) 的 LRU 缓存
在实际的工程应用中（如 Redis），数据除了因为容量满了被淘汰，往往还需要支持过期时间 (Time-To-Live, TTL)。比如一个验证码只在 5 分钟内有效。
设计思路：惰性删除 (Lazy Expiration)
我们不启动后台线程去实时扫描过期数据（那样太消耗 CPU），而是采用类似于 Redis 的惰性删除策略：
- 在
Node中增加一个字段expireTime（绝对过期时间戳）。 - 每次
put元素时，指定该元素的存活时间。 - 每次
get元素时，先检查当前时间是否超过了expireTime。如果超过了，直接在 map 和链表中删除该节点，并返回-1（模拟找不到）。
Java 代码实现 (LRU Cache with TTL)
importjava.util.HashMap;importjava.util.Map;classLRUCacheWithTTL{classNode{intkey,value;longexpireTime;// 记录绝对过期时间戳（毫秒）Nodeprev,next;Node(intk,intv,longexpireTime){this.key=k;this.value=v;this.expireTime=expireTime;}}privatefinalintcapacity;Nodedummy=newNode(0,0,0);Map<Integer,Node>map=newHashMap<>();publicLRUCacheWithTTL(intcapacity){this.capacity=capacity;dummy.prev=dummy;dummy.next=dummy;}publicintget(intkey){Nodenode=map.get(key);if(node==null){return-1;}// 核心逻辑：检查是否过期if(System.currentTimeMillis()>node.expireTime){// 已过期，触发惰性删除remove(node);map.remove(key);return-1;// 当作没查到}// 没过期，按 LRU 规则移动到头部remove(node);putFront(node);returnnode.value;}// 存入数据时，需要传入存活时间 ttlMillis (毫秒)publicvoidput(intkey,intvalue,longttlMillis){longexpireTime=System.currentTimeMillis()+ttlMillis;Nodenode=map.get(key);if(node!=null){// 节点存在，更新值和过期时间，并移到头部node.value=value;node.expireTime=expireTime;remove(node);putFront(node);return;}// 插入新节点node=newNode(key,value,expireTime);map.put(key,node);putFront(node);// 如果超出容量，执行 LRU 淘汰策略if(map.size()>capacity){Nodetail=dummy.prev;// 拿到最久未使用的节点map.remove(tail.key);remove(tail);}}privatevoidremove(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}privatevoidputFront(Nodenode){node.prev=dummy;node.next=dummy.next;node.next.prev=node;node.prev.next=node;}}进阶思考：还有优化的空间吗？
目前的 TTL 版本在超容（size > capacity）淘汰时，只是盲目淘汰了最久未使用的节点。
在更完美的工程实现中，遇到超容时，可以先遍历一下链表尾部，看看有没有已经过期的节点优先清理掉，如果都没有，再严格淘汰 LRU 节点。这使得内存的利用率更加极致。
4. 总结
- 标准 LRU：核心是
HashMap保证访问速度，双向链表维持时间顺序。通过单 Dummy 环形链表可以大大简化代码。 - 带 TTL 的 LRU：核心是引入时间戳，并在
get操作时执行惰性删除，这也是理解工业级缓存组件（如 Redis 淘汰策略）的敲门砖。
