文章目录1. 什么是 LRU为什么需要它2. 标准版 LRU 实现 (LeetCode 146)单 Dummy 节点环形链表3. 进阶版带过期时间 (TTL) 的 LRU 缓存设计思路惰性删除 (Lazy Expiration)Java 代码实现 (LRU Cache with TTL)进阶思考还有优化的空间吗4. 总结1. 什么是 LRU为什么需要它LRULeast 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.keyk;this.valuev;}}privatefinalintcapacity;// 核心技巧单一虚拟节点构建环形双向链表NodedummynewNode(0,0);MapInteger,NodemapnewHashMap();publicLRUCache(intcapacity){this.capacitycapacity;// 初始化环形链表自己指向自己dummy.prevdummy;dummy.nextdummy;}publicintget(intkey){Nodenodefind(key);returnnode!null?node.value:-1;}publicvoidput(intkey,intvalue){Nodenodemap.get(key);// 如果节点已存在更新值并把它移到头部if(node!null){node.valuevalue;find(key);// 复用 find 方法中的移到头部逻辑return;}// 如果节点不存在创建新节点并加入nodenewNode(key,value);map.put(key,node);putFront(node);// 判断是否超容超容则淘汰最久未使用的节点即 dummy 的前驱节点if(map.size()capacity){Nodetempdummy.prev;// 环形链表的尾节点map.remove(temp.key);remove(temp);}}// 辅助方法查找节点并将其移动到链表头部表示最近使用过privateNodefind(intkey){if(!map.containsKey(key)){returnnull;}Nodetempmap.get(key);remove(temp);// 先从原位置拔出putFront(temp);// 再插入到头部returntemp;}// 辅助方法从双向链表中删除节点privatevoidremove(Nodenode){node.prev.nextnode.next;node.next.prevnode.prev;}// 辅助方法将节点插入到头部dummy 之后privatevoidputFront(Nodenode){node.prevdummy;node.nextdummy.next;node.next.prevnode;node.prev.nextnode;}}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.keyk;this.valuev;this.expireTimeexpireTime;}}privatefinalintcapacity;NodedummynewNode(0,0,0);MapInteger,NodemapnewHashMap();publicLRUCacheWithTTL(intcapacity){this.capacitycapacity;dummy.prevdummy;dummy.nextdummy;}publicintget(intkey){Nodenodemap.get(key);if(nodenull){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){longexpireTimeSystem.currentTimeMillis()ttlMillis;Nodenodemap.get(key);if(node!null){// 节点存在更新值和过期时间并移到头部node.valuevalue;node.expireTimeexpireTime;remove(node);putFront(node);return;}// 插入新节点nodenewNode(key,value,expireTime);map.put(key,node);putFront(node);// 如果超出容量执行 LRU 淘汰策略if(map.size()capacity){Nodetaildummy.prev;// 拿到最久未使用的节点map.remove(tail.key);remove(tail);}}privatevoidremove(Nodenode){node.prev.nextnode.next;node.next.prevnode.prev;}privatevoidputFront(Nodenode){node.prevdummy;node.nextdummy.next;node.next.prevnode;node.prev.nextnode;}}进阶思考还有优化的空间吗目前的 TTL 版本在超容size capacity淘汰时只是盲目淘汰了最久未使用的节点。在更完美的工程实现中遇到超容时可以先遍历一下链表尾部看看有没有已经过期的节点优先清理掉如果都没有再严格淘汰 LRU 节点。这使得内存的利用率更加极致。4. 总结标准 LRU核心是HashMap保证访问速度双向链表维持时间顺序。通过单 Dummy 环形链表可以大大简化代码。带 TTL 的 LRU核心是引入时间戳并在get操作时执行惰性删除这也是理解工业级缓存组件如 Redis 淘汰策略的敲门砖。