吸引人的标题手写实现

手写LRU缓存：3道高频面试题，打通底层逻辑 看了一堆教程还是不会写项目？别慌，这不是你的错。很多开发者卡在“懂原理”和“能落地”之间，面试时一提到 高频面试题 里的 LRU 缓存，脑子里全是概念，手却写不出代码。今天不讲虚的，直接拆解 LRU 缓存的核心考点，从算法原理到代码实现，帮你把这块硬骨头啃下来。 考点梳理：LRU 到底考什么？ 面试官问 LRU（Least Recently Used，最近最少使用），通常不是只想听你背定义。他们想确认三件事：数据结构选型能力：你知道为什么需要结合哈希表和双向链表？ 边界条件处理：容量满时怎么淘汰？键不存在时怎么处理？ 性能意识：你能不能说出时间复杂度是 O(1)，并解释为什么？很多初学者只记得“链表+哈希表”，但说不清为什么是双向链表而不是单向。这里有个关键细节：单向链表删除节点需要前驱节点，而双向链表可以直接通过节点指针访问前后节点，从而在 O(1) 时间内完成删除。这一点在面试中必须讲清楚，否则会被追问倒。 另外，NPM 官方包 lru-cache 是 JS 生态中实现 LRU 的经典库，其源码逻辑与本文讲解高度一致。研究官方实现，比看十篇博客更有效。你可以去 GitHub 上看 lru-cache 的源码，你会发现它正是用了 Map + 双向链表的变体实现。 标准答法：如何组织语言？ 面试时，建议按“总-分-总”结构回答： 第一步：给出结论 “LRU 缓存通常用哈希表 + 双向链表实现，保证 get 和 put 操作都是 O(1) 时间复杂度。” 第二步：解释设计思路哈希表：键为缓存的 key，值为链表中对应节点的指针。用于 O(1) 查找。 双向链表：维护访问顺序。头部是最近使用的，尾部是最久未使用的。 操作逻辑：get(key)：如果 key 存在，将对应节点移到头部，返回 value；否则返回 -1。 put(key, value)：如果 key 存在，更新 value 并移到头部；如果不存在，新建节点插入头部，若超过容量，删除尾部节点，并同步删除哈希表中的键。第三步：强调优势 “相比数组或普通链表，这种结构避免了 O(n) 的查找或插入开销，特别适合缓存场景。” 注意：不要只说“用哈希表和链表”，必须点明是双向链表，并说明理由。这是区分“背答案”和“真理解”的关键。 代码实现：Python 逐行讲解 下面用 Python 实现一个标准的 LRU 缓存，代码简洁，注释清晰，适合面试手写。 class Node:def __init__(self, key=0, value=0):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):self.capacity = capacityself.cache = {} # key - Node# 双向链表哨兵节点，避免边界判断self.head = Node()self.tail = Node()self.head.next = self.tailself.tail.prev = self.headdef _remove_node(self, node: Node):从链表中移除节点node.prev.next = node.nextnode.next.prev = node.prevdef _add_to_head(self, node: Node):将节点添加到头部（最近使用）node.next = self.head.nextnode.prev = self.headself.head.next.prev = nodeself.head.next = nodedef get(self, key: int) - int:if key not in self.cache:return -1node = self.cache[key]# 移动到头部，表示最近使用self._remove_node(node)self._add_to_head(node)return node.valuedef put(self, key: int, value: int) - None:if key in self.cache:# 更新值，并移动到头部node = self.cache[key]node.value = valueself._remove_node(node)self._add_to_head(node)else:# 新建节点new_node = Node(key, value)self.cache[key] = new_nodeself._add_to_head(new_node)# 超过容量，淘汰尾部节点if len(self.cache) self.capacity:lru_node = self.tail.prevself._remove_node(lru_node)del self.cache[lru_node.key]逐行解析关键点：哨兵节点（head/tail）：避免处理空链表或头尾节点的边界情况，代码更简洁。 _remove_node 和 _add_to_head：封装链表操作，逻辑清晰，便于复用。 put 中的淘汰逻辑：注意先添加新节点，再判断容量，这样保证新节点不会立即被淘汰。 哈希表同步删除：删除尾部节点时，必须同时删除哈希表中对应的键，否则会导致内存泄漏或数据不一致。这段代码在 PyPI 官方包 中虽无直接对应，但逻辑与 functools.lru_cache 装饰器底层实现思路一致。lru_cache 内部也使用了类似的双向链表结构来管理缓存条目。 追问与延伸：面试官还会问什么？ 追问1：为什么不用单向链表？ 答：单向链表删除节点需要 O(n) 时间找前驱，而双向链表可以 O(1) 删除。在缓存高频读写场景下，性能差异显著。 追问2：如果并发访问，怎么改造？ 答：可以加锁，但会降低性能。更优方案是使用线程本地缓存，或采用分段锁。在分布式场景下，可以考虑 Redis 的 LRU 策略，它基于近似算法，适合大规模数据。 追问3：LRU 和 LFU 有什么区别？ 答：LRU 淘汰最久未使用的，LFU 淘汰最少使用的。LFU 需要额外记录访问频率，实现更复杂，但适合访问模式不随时间变化的场景。 避坑提醒：手写代码时，不要漏掉哈希表的同步删除，这是最常见的 bug。 测试用例要覆盖：容量为 1、重复 put 相同 key、get 不存在的 key 等边界情况。记忆口诀：快速回忆核心逻辑 为了方便面试前快速回顾，送你一个口诀：哈希查节点，链表管顺序； Get 移头部，Put 先判断； 存在则更新，不存在则新； 超容删尾部，哈希同步删。这四句话涵盖了 LRU 缓存的所有核心操作。面试时，先背口诀，再展开细节，能极大提升表达流畅度。 总结与行动建议 LRU 缓存是 高频面试题 中的经典，但绝非难到无法攻克。关键在于理解“哈希表 + 双向链表”的设计动机，并能手写代码。建议你：亲手敲一遍上面的 Python 代码，不要只看不练。 用测试用例验证，包括边界情况。 对比 NPM/PyPI 官方包的实现，理解工程化细节。这个知识点你面试被问过吗？留言说说，你当时是怎么回答的？有没有被追问到哑口无言？