146.LRU缓存 详细技术解析（O(1)复杂度实现）

146.LRU缓存 详细技术解析O(1)复杂度实现 面试高频题 | 手把手教你实现LRU缓存 | 满足O(1)平均时间复杂度 | 含完整代码逐行解析示例验证避坑指南新手也能看懂一、题目核心解析读懂LRU约束二、核心思路为什么需要“哈希表双向链表”三、完整代码实现严格遵循题目指定格式四、代码逐行详解新手必看拆解每一步逻辑五、示例验证完全匹配题目案例六、复杂度分析为什么能达到O(1)七、常见避坑指南面试易错点八、进阶优化与拓展面试加分项九、总结核心要点提炼一、题目核心解析读懂LRU约束LRULeast Recently Used最近最少使用缓存的核心逻辑当缓存容量已满时逐出“最久未使用”的元素同时保证get和put操作的平均时间复杂度为O(1)。题目要求实现LRUCache类包含3个核心方法__init__(self, capacity: int)以正整数capacity初始化缓存设定缓存的最大容量get(self, key: int) - int查询key对应的value存在则返回value不存在返回-1注意查询操作会将该key标记为“最近使用”put(self, key: int, value: int) - None若key已存在更新其对应的value并标记为“最近使用”若key不存在插入新的key-value对若插入后容量超出capacity逐出“最久未使用”的key-value对。核心难点如何在O(1)时间内完成“查询key”“标记最近使用”“逐出最久未使用”三个操作这是本题的关键也是面试考察的重点。示例补充说明题目中的输入输出对应逻辑本质是模拟LRU的核心流程——每次get/put操作都会改变元素的“使用优先级”容量满时淘汰最久未被使用的元素。二、核心思路为什么需要“哈希表双向链表”要实现O(1)时间复杂度单一数据结构无法满足所有需求需结合两种数据结构的优势互补短板2.1 两种数据结构的作用哈希表dict作用快速查询key对应的节点时间复杂度O(1)存储key为缓存的关键字value为双向链表中的节点包含key和value短板无法记录元素的“使用顺序”无法快速找到“最久未使用”的元素。双向链表作用记录元素的使用顺序快速调整元素优先级、删除节点时间复杂度O(1)规则最近使用的元素放在链表头部最久未使用的元素放在链表尾部优势双向链表可通过前驱/后继指针快速将节点移到头部、删除尾部节点无需遍历短板无法快速查询某个key对应的节点时间复杂度O(n)。2.2 核心配合逻辑查询get通过哈希表快速找到key对应的链表节点返回value同时将该节点移到链表头部标记为最近使用插入/更新putkey已存在通过哈希表找到节点更新value将节点移到链表头部key不存在创建新节点插入到链表头部同时存入哈希表若容量超出删除链表尾部节点最久未使用并从哈希表中删除对应key。补充为了简化链表操作避免处理头节点/尾节点为空的边界问题我们会使用虚拟头节点和虚拟尾节点无需额外判断边界提升代码简洁度和稳定性。三、完整代码实现严格遵循题目指定格式以下代码完全遵循题目要求的类和方法格式可直接复制提交LeetCode一次性AC且满足O(1)平均时间复杂度classLRUCache:def__init__(self,capacity:int):# 定义双向链表节点类内部类classListNode:def__init__(self,key0,value0):self.keykey self.valuevalue self.prevNone# 前驱指针self.nextNone# 后继指针# 初始化缓存容量self.capacitycapacity# 初始化哈希表用于快速映射key和链表节点self.cachedict()# 初始化虚拟头节点和虚拟尾节点简化边界处理self.headListNode()self.tailListNode()# 连接虚拟头和虚拟尾形成空链表self.head.nextself.tail self.tail.prevself.head# 关键修正将内部类ListNode赋值给实例属性供其他方法调用self.ListNodeListNodedefget(self,key:int)-int:# 1. 判断key是否在缓存中ifkeynotinself.cache:return-1# 2. 找到对应的链表节点nodeself.cache[key]# 3. 将该节点移到链表头部标记为最近使用self._move_to_head(node)# 4. 返回节点的值returnnode.valuedefput(self,key:int,value:int)-None:# 1. 判断key是否已存在ifkeyinself.cache:# 1.1 存在更新节点值并移到头部nodeself.cache[key]node.valuevalue self._move_to_head(node)return# 2. 不存在创建新节点此时self.ListNode已定义可正常调用new_nodeself.ListNode(key,value)# 2.1 将新节点存入哈希表self.cache[key]new_node# 2.2 将新节点插入到链表头部self._add_to_head(new_node)# 3. 判断缓存是否超出容量iflen(self.cache)self.capacity:# 3.1 移除链表尾部节点最久未使用removed_nodeself._remove_tail()# 3.2 从哈希表中删除对应keydelself.cache[removed_node.key]# 辅助方法将节点添加到链表头部私有方法外部不调用def_add_to_head(self,node):# 1. 先处理node的前驱和后继node.prevself.head node.nextself.head.next# 2. 再处理头节点的后继节点和头节点本身self.head.next.prevnode self.head.nextnode# 辅助方法将节点从当前位置移除私有方法外部不调用def_remove_node(self,node):# 让节点的前驱和后继直接连接跳过当前节点node.prev.nextnode.nextnode.next.prevnode.prev# 辅助方法将节点移到链表头部先移除再添加到头部def_move_to_head(self,node):self._remove_node(node)self._add_to_head(node)# 辅助方法移除链表尾部节点最久未使用并返回该节点def_remove_tail(self):# 找到真正的尾节点虚拟尾节点的前驱tail_nodeself.tail.prev# 移除该节点self._remove_node(tail_node)# 返回该节点用于后续从哈希表中删除returntail_node# Your LRUCache object will be instantiated and called as such:# obj LRUCache(capacity)# param_1 obj.get(key)# obj.put(key,value)说明代码中使用了内部类ListNode定义双向链表节点所有辅助方法_add_to_head、_remove_node等均为私有方法仅在类内部调用符合代码规范严格遵循题目指定的类和方法格式可直接提交使用。关键修正在__init__中添加self.ListNode ListNode解决“AttributeError: ‘LRUCache’ object has no attribute ‘ListNode’”报错——内部类仅在__init__内部可见需赋值给实例属性才能被put方法调用。四、代码逐行详解新手必看拆解每一步逻辑重点拆解核心方法和辅助方法搞懂每一行代码的作用避免死记硬背面试时能灵活应对。4.1 初始化方法init核心铺垫def__init__(self,capacity:int):# 定义双向链表节点类内部类classListNode:def__init__(self,key0,value0):self.keykey# 存储key用于删除哈希表时快速定位self.valuevalue# 存储缓存值self.prevNone# 前驱指针指向前一个节点self.nextNone# 后继指针指向后一个节点# 初始化缓存容量self.capacitycapacity# 初始化哈希表key: 缓存关键字value: 对应的链表节点self.cachedict()# 虚拟头节点和虚拟尾节点无实际意义简化边界处理self.headListNode()self.tailListNode()# 连接虚拟头和虚拟尾形成空的双向链表self.head.nextself.tail self.tail.prevself.head# 关键修正将内部类ListNode赋值给实例属性供put等方法调用# 报错原因内部类仅在__init__内部可见不赋值给实例属性其他方法无法调用self.ListNodeListNode关键细节节点类ListNode必须存储key因为删除链表尾部节点后需要通过节点的key从哈希表中删除对应的条目否则哈希表会残留无效key虚拟头/尾节点避免处理“头节点为空”“尾节点为空”的边界情况比如第一次插入节点、删除最后一个节点让后续操作更简洁。4.2 辅助方法核心工具简化主逻辑4个辅助方法是实现O(1)复杂度的关键单独拆解理解其作用4.2.1 _add_to_head(node)将节点添加到链表头部def_add_to_head(self,node):# 1. 先设置node的前驱和后继前驱是虚拟头后继是虚拟头的下一个节点node.prevself.head node.nextself.head.next# 2. 再修改虚拟头下一个节点的前驱以及虚拟头的后继self.head.next.prevnode self.head.nextnode逻辑头部插入是“最近使用”的标记新插入、查询后的节点都会通过这个方法移到头部确保头部始终是最近使用的元素。4.2.2 _remove_node(node)将节点从当前位置移除def_remove_node(self,node):# 让当前节点的前驱直接指向当前节点的后继node.prev.nextnode.next# 让当前节点的后继直接指向当前节点的前驱node.next.prevnode.prev逻辑双向链表的优势在此体现——无需遍历通过前驱和后继指针直接跳过当前节点实现O(1)时间删除。4.2.3 _move_to_head(node)将节点移到链表头部def_move_to_head(self,node):self._remove_node(node)# 先从当前位置移除self._add_to_head(node)# 再添加到头部逻辑查询get、更新put已存在key操作后需要将节点标记为“最近使用”本质就是“先删后加”移到头部。4.2.4 _remove_tail()移除链表尾部节点最久未使用def_remove_tail(self):# 真正的尾节点是虚拟尾节点的前驱虚拟尾节点无实际意义tail_nodeself.tail.prev self._remove_node(tail_node)# 移除该节点returntail_node# 返回节点用于删除哈希表中的key逻辑缓存容量满时需要删除最久未使用的元素而双向链表的尾部虚拟尾的前驱就是最久未使用的节点删除后返回该节点方便后续从哈希表中删除对应key。4.3 get方法查询操作defget(self,key:int)-int:# 1. 若key不在缓存中直接返回-1ifkeynotinself.cache:return-1# 2. 从哈希表中找到对应的节点nodeself.cache[key]# 3. 将节点移到头部标记为最近使用self._move_to_head(node)# 4. 返回节点的值returnnode.value流程总结查询→判断存在性→移到头部→返回值全程O(1)时间哈希表查询O(1)移动节点O(1)。4.4 put方法插入/更新操作defput(self,key:int,value:int)-None:# 1. 若key已存在更新值移到头部ifkeyinself.cache:nodeself.cache[key]node.valuevalue# 更新值self._move_to_head(node)# 标记为最近使用return# 2. 若key不存在创建新节点# 修正说明self.ListNode已在__init__中赋值可正常创建新节点解决AttributeErrornew_nodeself.ListNode(key,value)self.cache[key]new_node# 存入哈希表self._add_to_head(new_node)# 插入头部# 3. 若超出容量删除尾部节点删除哈希表对应keyiflen(self.cache)self.capacity:removed_nodeself._remove_tail()# 移除最久未使用节点delself.cache[removed_node.key]# 从哈希表中删除流程总结判断存在性→更新/创建节点→插入头部→判断容量→淘汰尾部节点全程O(1)时间所有操作均为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]]代码执行流程对应输出LRUCache(2)初始化容量为2的缓存链表head ↔ tail哈希表空 → 输出nullput(1, 1)key1不存在创建节点插入头部哈希表{1: 节点1} → 输出null链表head ↔ 节点1 ↔ tailput(2, 2)key2不存在创建节点插入头部哈希表{1:节点1, 2:节点2} → 输出null链表head ↔ 节点2 ↔ 节点1 ↔ tailget(1)key1存在将节点1移到头部返回1 → 输出1链表head ↔ 节点1 ↔ 节点2 ↔ tailput(3, 3)key3不存在创建节点插入头部哈希表长度32删除尾部节点2哈希表{1:节点1, 3:节点3} → 输出null链表head ↔ 节点3 ↔ 节点1 ↔ tailget(2)key2不在哈希表中返回-1 → 输出-1put(4, 4)key4不存在创建节点插入头部哈希表长度32删除尾部节点1哈希表{3:节点3, 4:节点4} → 输出null链表head ↔ 节点4 ↔ 节点3 ↔ tailget(1)key1不在哈希表中返回-1 → 输出-1get(3)key3存在将节点3移到头部返回3 → 输出3get(4)key4存在将节点4移到头部返回4 → 输出4最终输出[null, null, null, 1, null, -1, null, -1, 3, 4]与题目示例完全一致 ✅。六、复杂度分析为什么能达到O(1)核心要求get和put操作的平均时间复杂度为O(1)我们的实现完全满足具体分析如下操作涉及的操作时间复杂度说明get(key)哈希表查询、节点移到头部移除添加O(1)哈希表查询O(1)双向链表移除/添加节点O(1)put(key, value)哈希表查询/插入/删除、节点添加/移除/移动O(1)所有操作均为O(1)无遍历操作空间复杂度O(capacity)哈希表和双向链表的存储容量均不超过缓存容量capacity符合题目要求。七、常见避坑指南面试易错点坑1节点类忘记存储key导致删除尾部节点后无法同步删除哈希表错误原因删除链表尾部节点后需要通过节点的key删除哈希表中的对应条目若节点不存储key无法定位正确做法ListNode类必须包含key属性与哈希表的key对应。坑2未使用虚拟头/尾节点边界处理出错错误原因没有虚拟节点插入第一个节点、删除最后一个节点时需要额外判断head/tail是否为空容易遗漏边界正确做法固定使用虚拟头和虚拟尾节点统一所有节点的操作逻辑无需额外判断。坑3移动节点时只修改了节点的指针未修改相邻节点的指针错误原因比如_move_to_head方法只删除节点未重新连接相邻节点导致链表断裂正确做法严格按照“先处理节点的前驱后继再处理相邻节点”的顺序确保链表连接正常。坑4put操作中key已存在时忘记更新value错误原因只将节点移到头部未更新节点的value导致后续get操作返回旧值正确做法key存在时先更新node.value再移动节点。坑5哈希表和链表不同步导致内存泄漏错误原因删除链表尾部节点后未从哈希表中删除对应key导致哈希表残留无效key占用内存正确做法删除链表节点后必须同步删除哈希表中的对应key。八、进阶优化与拓展面试加分项在基础实现的基础上可进行以下优化提升代码的鲁棒性和拓展性面试时可主动提及优化1使用collections.OrderedDict简化实现Python的collections.OrderedDict有序字典本身就支持“插入顺序”且提供了move_to_end移到末尾、popitem删除头部/尾部方法可简化代码但本质还是哈希表双向链表面试时建议先讲基础实现再补充这个优化优化2处理key的边界值根据题目提示key的范围是0~10000可在get/put方法中添加key的合法性校验提升代码鲁棒性拓展LRU缓存的应用场景面试时可能会被追问LRU的实际应用可举例浏览器缓存、Redis的缓存淘汰策略Redis支持LRU作为淘汰策略之一、操作系统的内存页面置换算法等。补充OrderedDict实现简化版仅作拓展基础实现仍是面试重点fromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.capacitycapacity self.cacheOrderedDict()defget(self,key:int)-int:ifkeynotinself.cache:return-1# 移到末尾OrderedDict默认末尾是最近使用self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)-None:ifkeyinself.cache:self.cache[key]value self.cache.move_to_end(key)returnself.cache[key]valueiflen(self.cache)self.capacity:# 删除头部最久未使用self.cache.popitem(lastFalse)九、总结核心要点提炼146.LRU缓存的核心是“O(1)时间复杂度实现查询、插入、淘汰”面试重点掌握以下3点数据结构选型哈希表双向链表互补短板实现O(1)操作核心逻辑最近使用的元素放链表头部最久未使用的放尾部get/put操作后更新元素优先级容量满时淘汰尾部元素避坑重点节点存储key、使用虚拟头/尾节点、哈希表与链表同步、边界处理。本题是面试高频题考察的核心是“数据结构的灵活运用”掌握基础实现后能轻松应对变体题目如LRU的拓展、其他缓存淘汰策略对比。建议手动敲写代码理解每一步指针操作避免死记硬背。