)
如果要评选“面试手写题之王”LRU缓存一定进前三。字节、阿里、腾讯高频到几乎每轮都问。它考的不是冷门技巧而是两个基础数据结构的缝合能力哈希表给你O(1)的查找双向链表给你O(1)的插入/删除 维护访问时序今天你就学一件事怎么把这两个结构缝成一个整体让get和put都是严格O(1)。以及面试最常被追问的那句“为什么必须是双向链表单链表不行吗” 题目速览 LeetCode 14630秒读懂设计一个LRU最近最少使用缓存支持get(key)命中返回value否则-1并把它标记为“最近使用”put(key, value)写入若超容逐出最久未使用的key要求get和put都是O(1)平均时间复杂度。示例LRUCache(2) put(1,1) → [(1,1)] put(2,2) → [(2,2),(1,1)] get(1) → 1变成 [(1,1),(2,2)] put(3,3) → 逐出2[(3,3),(1,1)] get(2) → -1约束capacity ≤ 3000调用次数 ≤ 2e5。 核心思路哈希表负责“找得到”双向链表负责“排得开”暴力为什么不行用数组get线性扫描O(n)put时“搬到头部”还要移动大量元素。2e5次调用 × 3000容量扫描直接超时。瓶颈有两处① 查找慢② 移动慢。对症下药两个结构各治一个瓶颈查找慢 → 哈希表用HashMapkey, 节点引用一次定位O(1)。⚠️关键细节哈希表存的不是key→value而是key→链表节点引用——只有拿到节点引用才能操作它在链表里的位置。移动慢 → 双向链表所有节点串成一条双向链表约定靠近头部 最近使用靠近尾部 最久未使用命中时从哈希表拿到节点引用移到链表头部纯指针操作O(1)。超容时直接删掉尾部节点。⚠️ 第一号追问为什么必须是双向链表get/put命中后要把任意一个中间节点从链表里摘掉。摘掉任意节点需要node.prev.nextnode.next单链表没有 prev拿不到前驱只能从头遍历O(n)——O(1)立刻退化成O(n)。双向链表不是为了炫技是为了让“删除任意节点”本身是O(1)。⚠️ 第二号追问哨兵节点Sentinel的价值没有哨兵时addToHead、removeTail都要判断链表是不是空的是不是只有一个节点要删的是不是头节点边界一多白板上必错。虚拟head和虚拟tail两个哑节点永远存在、彼此相连业务节点始终插在它们中间任何节点的prev和next永不为null彻底消灭空指针分支头插永远是dummyHead.next尾删永远是dummyTail.prev核心流程四句话动作操作命中哈希表拿到节点 → 移到链表头部新增建节点 → 塞哈希表 → 头插超容摘掉dummyTail.prev→同步从哈希表删掉它的key逐出唯一要点两个结构必须同步删否则留野引用 → 内存泄漏️ 图解算法手把手走一遍骨架结构完整示例capacity 2步骤操作命中?链表状态头 → 尾输出1LRUCache(2)—[]null2put(1,1)新增[1:1]null3put(2,2)新增[2:2, 1:1]null4get(1)✅[1:1, 2:2]15put(3,3)超限[3:3, 1:1]逐出尾部2null6get(2)❌[3:3, 1:1]-17put(4,4)超限[4:4, 3:3]逐出尾部1null8get(1)❌[4:4, 3:3]-19get(3)✅[3:3, 4:4]310get(4)✅[4:4, 3:3]4第5步是淘汰的教科书演示新节点头插 → 超容 → 取dummyTail.prev→ 先断链表、再从哈希表删除key。两步必须成对出现漏掉删哈希表这一步节点会在哈希表里“复活”。 代码实现Python JavaPython版哈希表 手写双向链表classDLinkedNode:__slots__(key,value,prev,next)def__init__(self,key0,value0):self.keykey self.valuevalue self.prevNoneself.nextNoneclassLRUCache:def__init__(self,capacity:int):self.capacitycapacity self.cache{}# key - 节点引用不是valueself.headDLinkedNode()# 虚拟头哨兵self.tailDLinkedNode()# 虚拟尾哨兵self.head.nextself.tail self.tail.prevself.head# --- 三个原子操作 ---def_remove(self,node):摘掉任意节点O(1)因为node.prev直接可拿node.prev.nextnode.nextnode.next.prevnode.prevdef_add_to_head(self,node):头插 标记为最近使用node.prevself.head node.nextself.head.nextself.head.next.prevnode self.head.nextnodedef_move_to_head(self,node):self._remove(node)# 先摘再插顺序不能反self._add_to_head(node)def_pop_tail(self):nodeself.tail.prev# 最久未使用的那个self._remove(node)returnnodedefget(self,key:int)-int:nodeself.cache.get(key)ifnodeisNone:return-1self._move_to_head(node)# 命中即最近使用returnnode.valuedefput(self,key:int,value:int)-None:nodeself.cache.get(key)ifnodeisNone:freshDLinkedNode(key,value)self.cache[key]fresh self._add_to_head(fresh)iflen(self.cache)self.capacity:deadself._pop_tail()delself.cache[dead.key]# 链表与哈希表必须同步删else:node.valuevalue self._move_to_head(node)Java版importjava.util.HashMap;importjava.util.Map;classLRUCache{staticclassNode{intkey,value;Nodeprev,next;Node(intkey,intvalue){this.keykey;this.valuevalue;}}privatefinalintcapacity;privatefinalMapInteger,NodecachenewHashMap();privatefinalNodedummyHeadnewNode(0,0);privatefinalNodedummyTailnewNode(0,0);publicLRUCache(intcapacity){this.capacitycapacity;dummyHead.nextdummyTail;dummyTail.prevdummyHead;}privatevoidremove(Nodenode){node.prev.nextnode.next;node.next.prevnode.prev;}privatevoidaddToHead(Nodenode){node.prevdummyHead;node.nextdummyHead.next;dummyHead.next.prevnode;dummyHead.nextnode;}privatevoidmoveToHead(Nodenode){remove(node);addToHead(node);}privateNoderemoveTail(){NodenodedummyTail.prev;remove(node);returnnode;}publicintget(intkey){Nodenodecache.get(key);if(nodenull)return-1;moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){Nodenodecache.get(key);if(nodenull){NodefreshnewNode(key,value);cache.put(key,fresh);addToHead(fresh);if(cache.size()capacity){NodedeadremoveTail();cache.remove(dead.key);// 别漏这一步}}else{node.valuevalue;moveToHead(node);}}}⚠️防坑提醒必看哈希表存的必须是节点引用而不是value否则拿不到链表位置。_move_to_head是“先remove再addToHead”别试图省步数直接改两根指针容易漏掉一侧的反向指针。淘汰时链表断链 哈希表删 key 必须成对。Python版给节点加了__slots__省内存也更接近 Java 的字段语义。⏱️ 复杂度分析面试必问时间三个原子操作全是常数次指针赋值get 一次哈希查找 一次移动 O(1)put 一次哈希查找 一次移动或新增 可能的淘汰 O(1)。空间哈希表 链表总共存capacity个键值对 O(capacity)。为什么叫“平均”O(1)HashMap 的哈希冲突理论上可能退化Java8之后链表转红黑树保底O(logn)题目才说“平均O(1)”。 举一反三4 道高频变体题题目变化点思路要点LC.460 LFU 缓存按“使用频次”淘汰同频再比时间双哈希表key→节点频次→该频次下的双向链表维护minFreqLC.432 全O(1)数据结构支持inc/dec/getMaxKey/getMinKey双向链表 计数桶本质同LFU的“桶链表”结构设计LFU / LRU-K / FIFO缓存淘汰策略换一套骨架不动只换“谁该被淘汰”的判定逻辑LC.588 设计内存文件系统目录树 文件操作哈希表 树结构组合 面试追问模拟提前准备惊艳全场Q1为什么必须用双向链表单链表不行吗摘除任意节点需要node.prev.next node.next。单链表没有prev只能从头遍历找前驱O(1)立刻退化成O(n)。除非你能保证只删表头那就退化成FIFO 了不是LRU。这是本题唯一的硬性理由。Q2哨兵节点到底省了什么省掉三类分支链表为空、只有一个元素、要删的是首/尾节点。有了dummyHead/dummyTail业务节点的prev/next永远非nullremove和addToHead可以写成无分支的4行。白板题少一个分支就少一个bug。Q3如果让你改成LFU怎么改淘汰标准从“最久未使用”变成“使用次数最少”。做法节点增加freq字段哈希表①仍是key→节点哈希表②变成freq→双向链表同频次内部仍按时间排序再维护minFreq。每次get把节点从freq桶移到freq1桶淘汰时从minFreq桶的尾部取节点。两个哈希表 N条链表操作依然全O(1)。Q4线程安全怎么保证工程版要加锁或用分段锁。Java里最简单两种给整个类加synchronized简单但串行或用ConcurrentHashMapReadWriteLock。Caffeine/Guava Cache内部用的是更精细的分段 环形缓冲区 读写锁组合。 实战小技巧刷题党必备口诀哈希找节点链表排时序命中移头部超容删尾巴哨兵灭边界删表要同步。模板LRU HashMap 双向链表 虚拟哨兵 moveToHead/popTail。防坑先remove再addToHead淘汰时同步删哈希表。 实际应用场景不止是刷题MySQL/PostgreSQL Buffer Pool页的LRU淘汰改进版防全表扫描污染Redisallkeys-lru采样近似LRU代价低操作系统页面置换LRU是经典策略浏览器前进后退历史记录管理多级缓存本地层Caffeine、Memcached 今日思考题如果一个节点被get了100次但都是很久以前的事而另一个节点刚刚被get了1次LRU会淘汰谁提示LRU只看“最近一次使用时间”不看频率——这个“不合理”正是LFU存在的理由。
高频必考！LRU缓存：哈希表 + 双向链表缝在一起，get/put都是O(1)
如果要评选“面试手写题之王”LRU缓存一定进前三。字节、阿里、腾讯高频到几乎每轮都问。它考的不是冷门技巧而是两个基础数据结构的缝合能力哈希表给你O(1)的查找双向链表给你O(1)的插入/删除 维护访问时序今天你就学一件事怎么把这两个结构缝成一个整体让get和put都是严格O(1)。以及面试最常被追问的那句“为什么必须是双向链表单链表不行吗” 题目速览 LeetCode 14630秒读懂设计一个LRU最近最少使用缓存支持get(key)命中返回value否则-1并把它标记为“最近使用”put(key, value)写入若超容逐出最久未使用的key要求get和put都是O(1)平均时间复杂度。示例LRUCache(2) put(1,1) → [(1,1)] put(2,2) → [(2,2),(1,1)] get(1) → 1变成 [(1,1),(2,2)] put(3,3) → 逐出2[(3,3),(1,1)] get(2) → -1约束capacity ≤ 3000调用次数 ≤ 2e5。 核心思路哈希表负责“找得到”双向链表负责“排得开”暴力为什么不行用数组get线性扫描O(n)put时“搬到头部”还要移动大量元素。2e5次调用 × 3000容量扫描直接超时。瓶颈有两处① 查找慢② 移动慢。对症下药两个结构各治一个瓶颈查找慢 → 哈希表用HashMapkey, 节点引用一次定位O(1)。⚠️关键细节哈希表存的不是key→value而是key→链表节点引用——只有拿到节点引用才能操作它在链表里的位置。移动慢 → 双向链表所有节点串成一条双向链表约定靠近头部 最近使用靠近尾部 最久未使用命中时从哈希表拿到节点引用移到链表头部纯指针操作O(1)。超容时直接删掉尾部节点。⚠️ 第一号追问为什么必须是双向链表get/put命中后要把任意一个中间节点从链表里摘掉。摘掉任意节点需要node.prev.nextnode.next单链表没有 prev拿不到前驱只能从头遍历O(n)——O(1)立刻退化成O(n)。双向链表不是为了炫技是为了让“删除任意节点”本身是O(1)。⚠️ 第二号追问哨兵节点Sentinel的价值没有哨兵时addToHead、removeTail都要判断链表是不是空的是不是只有一个节点要删的是不是头节点边界一多白板上必错。虚拟head和虚拟tail两个哑节点永远存在、彼此相连业务节点始终插在它们中间任何节点的prev和next永不为null彻底消灭空指针分支头插永远是dummyHead.next尾删永远是dummyTail.prev核心流程四句话动作操作命中哈希表拿到节点 → 移到链表头部新增建节点 → 塞哈希表 → 头插超容摘掉dummyTail.prev→同步从哈希表删掉它的key逐出唯一要点两个结构必须同步删否则留野引用 → 内存泄漏️ 图解算法手把手走一遍骨架结构完整示例capacity 2步骤操作命中?链表状态头 → 尾输出1LRUCache(2)—[]null2put(1,1)新增[1:1]null3put(2,2)新增[2:2, 1:1]null4get(1)✅[1:1, 2:2]15put(3,3)超限[3:3, 1:1]逐出尾部2null6get(2)❌[3:3, 1:1]-17put(4,4)超限[4:4, 3:3]逐出尾部1null8get(1)❌[4:4, 3:3]-19get(3)✅[3:3, 4:4]310get(4)✅[4:4, 3:3]4第5步是淘汰的教科书演示新节点头插 → 超容 → 取dummyTail.prev→ 先断链表、再从哈希表删除key。两步必须成对出现漏掉删哈希表这一步节点会在哈希表里“复活”。 代码实现Python JavaPython版哈希表 手写双向链表classDLinkedNode:__slots__(key,value,prev,next)def__init__(self,key0,value0):self.keykey self.valuevalue self.prevNoneself.nextNoneclassLRUCache:def__init__(self,capacity:int):self.capacitycapacity self.cache{}# key - 节点引用不是valueself.headDLinkedNode()# 虚拟头哨兵self.tailDLinkedNode()# 虚拟尾哨兵self.head.nextself.tail self.tail.prevself.head# --- 三个原子操作 ---def_remove(self,node):摘掉任意节点O(1)因为node.prev直接可拿node.prev.nextnode.nextnode.next.prevnode.prevdef_add_to_head(self,node):头插 标记为最近使用node.prevself.head node.nextself.head.nextself.head.next.prevnode self.head.nextnodedef_move_to_head(self,node):self._remove(node)# 先摘再插顺序不能反self._add_to_head(node)def_pop_tail(self):nodeself.tail.prev# 最久未使用的那个self._remove(node)returnnodedefget(self,key:int)-int:nodeself.cache.get(key)ifnodeisNone:return-1self._move_to_head(node)# 命中即最近使用returnnode.valuedefput(self,key:int,value:int)-None:nodeself.cache.get(key)ifnodeisNone:freshDLinkedNode(key,value)self.cache[key]fresh self._add_to_head(fresh)iflen(self.cache)self.capacity:deadself._pop_tail()delself.cache[dead.key]# 链表与哈希表必须同步删else:node.valuevalue self._move_to_head(node)Java版importjava.util.HashMap;importjava.util.Map;classLRUCache{staticclassNode{intkey,value;Nodeprev,next;Node(intkey,intvalue){this.keykey;this.valuevalue;}}privatefinalintcapacity;privatefinalMapInteger,NodecachenewHashMap();privatefinalNodedummyHeadnewNode(0,0);privatefinalNodedummyTailnewNode(0,0);publicLRUCache(intcapacity){this.capacitycapacity;dummyHead.nextdummyTail;dummyTail.prevdummyHead;}privatevoidremove(Nodenode){node.prev.nextnode.next;node.next.prevnode.prev;}privatevoidaddToHead(Nodenode){node.prevdummyHead;node.nextdummyHead.next;dummyHead.next.prevnode;dummyHead.nextnode;}privatevoidmoveToHead(Nodenode){remove(node);addToHead(node);}privateNoderemoveTail(){NodenodedummyTail.prev;remove(node);returnnode;}publicintget(intkey){Nodenodecache.get(key);if(nodenull)return-1;moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){Nodenodecache.get(key);if(nodenull){NodefreshnewNode(key,value);cache.put(key,fresh);addToHead(fresh);if(cache.size()capacity){NodedeadremoveTail();cache.remove(dead.key);// 别漏这一步}}else{node.valuevalue;moveToHead(node);}}}⚠️防坑提醒必看哈希表存的必须是节点引用而不是value否则拿不到链表位置。_move_to_head是“先remove再addToHead”别试图省步数直接改两根指针容易漏掉一侧的反向指针。淘汰时链表断链 哈希表删 key 必须成对。Python版给节点加了__slots__省内存也更接近 Java 的字段语义。⏱️ 复杂度分析面试必问时间三个原子操作全是常数次指针赋值get 一次哈希查找 一次移动 O(1)put 一次哈希查找 一次移动或新增 可能的淘汰 O(1)。空间哈希表 链表总共存capacity个键值对 O(capacity)。为什么叫“平均”O(1)HashMap 的哈希冲突理论上可能退化Java8之后链表转红黑树保底O(logn)题目才说“平均O(1)”。 举一反三4 道高频变体题题目变化点思路要点LC.460 LFU 缓存按“使用频次”淘汰同频再比时间双哈希表key→节点频次→该频次下的双向链表维护minFreqLC.432 全O(1)数据结构支持inc/dec/getMaxKey/getMinKey双向链表 计数桶本质同LFU的“桶链表”结构设计LFU / LRU-K / FIFO缓存淘汰策略换一套骨架不动只换“谁该被淘汰”的判定逻辑LC.588 设计内存文件系统目录树 文件操作哈希表 树结构组合 面试追问模拟提前准备惊艳全场Q1为什么必须用双向链表单链表不行吗摘除任意节点需要node.prev.next node.next。单链表没有prev只能从头遍历找前驱O(1)立刻退化成O(n)。除非你能保证只删表头那就退化成FIFO 了不是LRU。这是本题唯一的硬性理由。Q2哨兵节点到底省了什么省掉三类分支链表为空、只有一个元素、要删的是首/尾节点。有了dummyHead/dummyTail业务节点的prev/next永远非nullremove和addToHead可以写成无分支的4行。白板题少一个分支就少一个bug。Q3如果让你改成LFU怎么改淘汰标准从“最久未使用”变成“使用次数最少”。做法节点增加freq字段哈希表①仍是key→节点哈希表②变成freq→双向链表同频次内部仍按时间排序再维护minFreq。每次get把节点从freq桶移到freq1桶淘汰时从minFreq桶的尾部取节点。两个哈希表 N条链表操作依然全O(1)。Q4线程安全怎么保证工程版要加锁或用分段锁。Java里最简单两种给整个类加synchronized简单但串行或用ConcurrentHashMapReadWriteLock。Caffeine/Guava Cache内部用的是更精细的分段 环形缓冲区 读写锁组合。 实战小技巧刷题党必备口诀哈希找节点链表排时序命中移头部超容删尾巴哨兵灭边界删表要同步。模板LRU HashMap 双向链表 虚拟哨兵 moveToHead/popTail。防坑先remove再addToHead淘汰时同步删哈希表。 实际应用场景不止是刷题MySQL/PostgreSQL Buffer Pool页的LRU淘汰改进版防全表扫描污染Redisallkeys-lru采样近似LRU代价低操作系统页面置换LRU是经典策略浏览器前进后退历史记录管理多级缓存本地层Caffeine、Memcached 今日思考题如果一个节点被get了100次但都是很久以前的事而另一个节点刚刚被get了1次LRU会淘汰谁提示LRU只看“最近一次使用时间”不看频率——这个“不合理”正是LFU存在的理由。
