手写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]

逐行解析关键点：