开发者日记

外观

一文搞懂 LRU：HashMap 加双向链表手写实战 ​

为什么 LRU 缓存设计是高频面试题 ​

LRU（Least Recently Used，最近最少使用）是缓存系统中最常见的淘汰策略之一。它的规则很简单：当缓存容量不足时，优先淘汰最久没有被访问的数据。

面试中，LRU 之所以高频，是因为它不是单纯考察某一个 API，而是同时考察三个能力：

  1. 是否理解缓存命中、写入、更新、淘汰的完整流程；
  2. 是否能根据时间复杂度选择合适的数据结构；
  3. 是否能正确处理双向链表节点移动、虚拟头尾节点和容量边界。

典型题目要求通常如下：

  • get(key)：如果 key 存在，返回对应 value，并将该 key 标记为最近使用；否则返回 -1；
  • put(key, value)：插入或更新数据；如果容量超限，淘汰最久未使用的 key；
  • 两个操作都必须在 O(1) 时间内完成。

这道题的关键不是“背下代码”，而是讲清楚为什么单独使用数组、单链表或 HashMap 都不够。

方案对比：为什么必须是 HashMap 加双向链表 ​

如果只使用普通链表保存访问顺序，查找 key 需要从头遍历，get 是 O(n)。如果只使用 HashMap，虽然查找是 O(1)，但无法快速知道哪个 key 最久未使用，也无法在 O(1) 时间内把某个节点移动到最近使用位置。

因此需要组合两种结构：

  • HashMap：通过 key 快速定位链表节点；
  • 双向链表：维护访问顺序，并支持节点的 O(1) 删除与插入。

常见方案对比如下：

方案查找更新访问顺序淘汰最久未使用评价
数组/列表O(n)O(n)O(n)简单但不满足要求
单链表O(n)删除需找前驱头删可行但整体慢不适合高频移动
HashMapO(1)无法维护顺序无法快速淘汰缺少顺序信息
HashMap + 双向链表O(1)O(1)O(1)标准最优实现

LRU 的核心数据结构设计 ​

约定双向链表头部表示最近使用，尾部表示最久未使用。

每次访问已存在的 key，都要把对应节点移动到头部。容量超限时，删除尾节点前面的真实节点，同时从 HashMap 中删除它的 key。

为了避免在插入和删除时反复判断空链表，可以使用两个虚拟节点：

  • head：虚拟头节点；
  • tail：虚拟尾节点。

初始化后结构为：

text
head <-> tail

插入新节点时统一放到 head 后面；淘汰节点时统一删除 tail 前面的节点。

下面这张图展示一次缓存写入、访问和淘汰时的结构变化：

put(A, 1)写入头节点后head ↔ A ↔ B ↔ C ↔ tail头部最近，尾部最久get(B)B 移动到头部容量满后 put(D)删除 tail 前节点 C，并同步删除 HashMap 中的 C

Python 手写 LRU 完整可运行代码 ​

下面代码不依赖 OrderedDict 或语言内置装饰器，而是从节点结构开始完整实现，更适合面试现场书写。

python
class Node:
    """双向链表节点，保存 key、value、前驱和后继"""

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        # 容量必须为正整数；题目通常保证合法，这里提前防御
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self.capacity = capacity
        self.cache = {}

        # 虚拟头尾节点，减少空指针判断
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 已存在：更新值并提升为最近使用
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            # 不存在：新建节点，放入 HashMap 和链表头部
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_head(node)

            # 超过容量：淘汰尾节点前的真实节点
            if len(self.cache) > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]

    def _add_to_head(self, node: Node) -> None:
        """把节点插入虚拟头节点后面"""
        node.prev = self.head
        node.next = self.head.next

        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node: Node) -> None:
        """从当前位置删除一个节点"""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_head(self, node: Node) -> None:
        """先删除，再插入头部，等价于提升访问优先级"""
        self._remove_node(node)
        self._add_to_head(node)

    def _remove_tail(self) -> Node:
        """删除并返回最久未使用节点"""
        node = self.tail.prev
        self._remove_node(node)
        return node


# 手动测试
if __name__ == "__main__":
    lru = LRUCache(2)

    lru.put(1, 10)
    lru.put(2, 20)
    print(lru.get(1))  # 10，key=1 变为最近使用

    lru.put(3, 30)     # 容量为 2，淘汰 key=2
    print(lru.get(2))  # -1
    print(lru.get(3))  # 30

操作流程拆解：get 和 put 到底做了什么 ​

get 查询流程 ​

  1. 在 HashMap 中判断 key 是否存在；
  2. 不存在直接返回 -1；
  3. 存在则取出节点；
  4. 将节点从原位置删除；
  5. 重新插入链表头部；
  6. 返回节点中的 value。

注意，HashMap 中保存的是节点引用，而不是只保存 value。这样在移动节点时，不需要再通过链表查找节点。

put 写入流程 ​

  • key 已存在：更新 value，并移动到头部；
  • key 不存在：创建新节点，同时写入 HashMap 和链表头部；
  • 如果节点数量超过容量：删除尾部真实节点，并根据该节点保存的 key 删除 HashMap 记录。

节点中必须保存 key。淘汰尾节点时，需要通过 removed.key 找到 HashMap 中对应项。如果节点只保存 value，链表虽然能删掉节点，但 HashMap 中会残留脏数据。

复杂度分析 ​

  • get(key)：平均时间复杂度 O(1)，HashMap 查找为 O(1)，双向链表删除和插入为 O(1)；
  • put(key, value)：平均时间复杂度 O(1)，包括插入、更新、移动和淘汰；
  • 空间复杂度：O(capacity)，HashMap 和双向链表最多保存容量范围内的数据。

这里的 HashMap 操作按平均复杂度分析。极端哈希冲突下可能退化，但工程语言中的哈希表通常有扩容和冲突处理机制，面试中回答平均 O(1) 即可。

面试满分答法：不要只说使用哈希表和链表 ​

建议按下面四层回答：

  1. 先讲需求：查询和写入都要 O(1)，并且访问过的元素要变成最近使用；
  2. 再讲选型：HashMap 负责快速定位，双向链表负责维护顺序；
  3. 讲清细节：头部最近、尾部最久，使用虚拟头尾节点简化边界；
  4. 补充边界：更新已有 key、插入新 key、容量超限淘汰、HashMap 与链表一致性。

如果面试官继续追问，可以补充：

  • 为什么不用单链表？因为删除已知节点时还需要找前驱；
  • 为什么节点里存 key？因为淘汰尾节点时要反删 HashMap；
  • 是否需要线程安全？基础题不需要，若在多线程环境中需要加锁或使用并发缓存结构；
  • Python 是否有内置工具？有 collections.OrderedDict 和 functools.lru_cache，但面试重点仍是手写原理。

避坑总结：这 3 类错误最容易丢分 ​

1. 只更新链表，忘记更新 HashMap ​

错误现象：执行淘汰后，链表中节点已经删除，但 cache 中仍然保留旧 key，导致容量统计错误或查询到无效数据。

修正方法：删除尾节点后，必须执行：

python
removed = self._remove_tail()
del self.cache[removed.key]

链表和 HashMap 是同一批数据的两种索引，任何增删都要保持一致。

2. 更新已有 key 时只改 value，没有移动到头部 ​

错误现象：调用 get 或 put 更新某个 key 后，它仍然停留在原位置，最终被错误淘汰。

修正方法：只要发生访问或更新，就应该调用 _move_to_head(node)。LRU 的“recently used”不只针对新插入，也针对查询和修改。

3. 插入节点时指针修改顺序错误 ​

错误现象：先执行 self.head.next = node，导致原来的第二个节点丢失，后续节点无法访问。

修正方法：先让新节点连接旧节点，再修改外部指针：

python
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node

可以记为“先接后断，先新后旧”。在双向链表操作中，不要提前覆盖仍然需要使用的指针。

4. 淘汰时删除虚拟尾节点 ​

错误现象：容量满后直接删除 tail，导致链表结构被破坏，后续操作出现空指针或循环异常。

修正方法：真正要淘汰的是 self.tail.prev，也就是虚拟尾节点前面的最后一个真实节点。虚拟节点只作为边界哨兵，不保存业务数据。

结语 ​

LRU 的本质是用 HashMap 解决“快速找到谁”，用双向链表解决“快速调整顺序”。掌握节点结构、头尾约定、四个基础指针操作和容量淘汰流程后，这道题就不再是模板记忆题，而是一道可以清晰推导的数据结构设计题。面试时只要把一致性、复杂度和边界条件讲完整，就能显著提升回答的完整度。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。

本文来自开发者日记（devdiary.cn）· 记录开发者实战笔记与免费在线工具箱

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。