---
title: 深入剖析 LeetCode 第 146 题「LRU 缓存」：基于哈希表与双向链表实现 O(1) 时间复杂度的 Python 解决方案及原理详解
created: 2026-03-10
updated: 2026-03-10
type: summary
tags: ["algorithm", "cache", "notes", "python", "telegram"]
external: http://go/ui/posts/2141/
status: inbox
---

好的，我们来看 LeetCode 第 146 题「LRU 缓存」。我会用最通俗的方式解释，并给出 Python 代码。

## 问题是什么？

我们需要设计一个「最近最少使用」（LRU）缓存。它就像一个能存放一定数量东西的盒子（容量 capacity）。你可以做两件事：
- `get(key)`：从盒子里拿出某个东西，如果存在就返回它的值，否则返回 -1。
- `put(key, value)`：往盒子里放东西。如果这个 key 已经存在，就更新它的值；如果 key 不存在，就放入新的 key-value 对。但盒子容量有限，如果放新东西时盒子已经满了，就要把**最久没用过**的东西扔掉，腾出空间。

关键要求：`get` 和 `put` 操作的时间复杂度必须是 **O(1)**，也就是非常快，不管盒子多大，操作时间几乎不变。

## 怎么设计？

要实现 O(1) 的查找，我们需要一个**哈希表**（字典），这样能立刻根据 key 找到对应的东西。

但是，我们还需要知道每个东西的「使用时间」顺序，以便在容量满时找出最久没用的那个。如果我们用一个数组或链表来记录顺序，那么更新顺序（比如某个 key 被使用了，要把它移到「最近使用」的位置）可能很慢。

因此，我们需要一个既能快速查找，又能快速调整顺序的数据结构。经典做法是：**哈希表 + 双向链表**。

- **双向链表**：链表中的每个节点代表一个缓存项（key-value 对）。链表按使用时间排序：**最近使用的在头部，最久未使用的在尾部**。
- **哈希表**：key 映射到链表中的对应节点。这样我们就能 O(1) 找到节点。

### 为什么用双向链表？
- 因为我们要频繁地把一个节点移到头部，或者删除尾部节点。双向链表可以让我们 O(1) 地修改前后节点的指针，而不需要遍历整个链表。
- 单向链表做不到 O(1) 删除中间节点，因为需要知道前一个节点。

## 操作详解

### 初始化
- 设定容量 capacity。
- 创建一个空的哈希表 `cache`。
- 创建双向链表，为了方便，我们通常添加虚拟的 head 和 tail 节点，这样就不用处理边界情况。

### get(key)
1. 如果 key 在哈希表中：
   - 找到对应的节点。
   - 把这个节点从当前位置**移除**，然后**插入到链表头部**（表示刚刚使用过）。
   - 返回节点的值。
2. 如果 key 不在，返回 -1。

### put(key, value)
1. 如果 key 已经在缓存中：
   - 找到节点，更新它的值。
   - 把这个节点移到链表头部（表示刚刚使用过）。
2. 如果 key 不在缓存中：
   - 创建一个新节点，存入 key 和 value。
   - 把这个节点插入到链表头部。
   - 在哈希表中添加 key -> 节点的映射。
   - 检查当前缓存大小是否超过容量：
     - 如果超过，需要删除链表尾部的节点（最久未使用），同时从哈希表中删除对应的 key。

## 代码实现（Python）

```python
class DLinkedNode:
    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):
        self.capacity = capacity
        self.cache = {}  # 哈希表：key -> node
        # 初始化双向链表，带虚拟头尾节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0  # 当前链表节点数量

    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:
            # 创建新节点
            new_node = DLinkedNode(key, value)
            self.cache[key] = new_node
            # 插入到头部
            self._add_to_head(new_node)
            self.size += 1
            # 如果超出容量，删除尾部节点
            if self.size > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]
                self.size -= 1

    # 辅助函数：将节点移到头部
    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)

    # 辅助函数：删除一个节点（已知节点）
    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    # 辅助函数：将节点添加到头部
    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    # 辅助函数：删除尾部节点（并返回该节点）
    def _remove_tail(self):
        node = self.tail.prev
        self._remove_node(node)
        return node
```

## 关键点解释

- **为什么用虚拟头尾节点？**  
  这样在插入和删除时，不需要判断 `head` 或 `tail` 是否为空，代码更简洁。

- **`_move_to_head` 为什么要先删再加？**  
  因为要改变节点的位置，所以先把它从链表中摘下来，再插入到头部。这两个操作都是 O(1)。

- **怎么保证 O(1)？**  
  所有操作都只涉及哈希表查找和链表指针修改，不涉及遍历。

这样我们就实现了一个高效的 LRU 缓存。希望这个解释对你有帮助！如果有不懂的地方，欢迎继续问。
