w wyl123ly 的博客
未分类 更新于 10 月 28 日

从零实现一个 LRU 缓存:链表与哈希表的配合

缓存淘汰算法里,LRU(Least Recently Used)是最常被要求手写的一个。它的难点不在思路,而在于同时满足 O(1) 的查找与 O(1) 的淘汰。单独用任何一种数据结构都做不到。

为什么需要两种结构#

如果用数组存 key,查找是 O(1) 的,但每次访问都要把元素挪到末尾,移动是 O(n)。如果用链表,移动到头部是 O(1),但查找必须遍历,也是 O(n)。

把「查找」和「顺序维护」拆给两个结构:哈希表存 key → 节点指针,链表维护冷热顺序。这就是 LRU 的全部秘密。

结构设计#

用一个带哨兵头尾的双向链表,头部是最近访问,尾部是最久未访问。哈希表的 value 直接指向链表节点,因此删除节点不需要遍历。

操作 数据结构 复杂度
查找 key dict O(1)
移到头部 双向链表 O(1)
淘汰尾部 双向链表 + dict O(1)

参考实现#

class Node:
    __slots__ = ("key", "val", "prev", "next")

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


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = Node()          # 哨兵:最近使用
        self.tail = Node()          # 哨兵:最久未用
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._unlink(node)
        self._push_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

三个容易踩的坑#

  • 删除 dict 条目时要用节点里存的 key,而不是外部传入的 key,否则淘汰逻辑会错位。
  • 哨兵节点能让边界判断消失,强烈建议加,代码可读性提升明显。
  • Python 3.7+ 的 dict 虽然有序,但那是插入顺序,不是访问顺序,不能直接当 LRU 用。

小结#

LRU 是「用空间换常数」的典型:多存一份指针,换来所有操作都是 O(1)。真正写的时候,把哨兵和摘链/头插两个基础操作封装好,主流程就只有几行。