LRU 缓存详解：原理、代码与时间复杂度

LRU 缓存解决什么问题

缓存保存慢操作的结果，例如数据库查询、网络请求或昂贵的计算，这样重复的请求就能很快得到响应。内存是有限的，所以缓存满了之后必须决定丢弃什么。LRU 押注于：最近用过的数据很快还会被用到，而很久没碰过的数据大概率不会再被用到。这个押注在许多真实负载中表现良好，所以 LRU 及其近似算法出现在 CPU 缓存、操作系统页缓存、数据库、Web 服务器和 CDN 中。

思路：两种结构协同工作

我们需要两件事都很快：找到一个键，以及知道哪个键是最近最少使用的。单独的哈希表没有顺序，单独的列表查找很慢。两者结合就能兼顾：

执行 get(key) 时，在映射中查找节点，把它移到最前面，并返回它的值。执行 put(key, value) 时，更新或创建最前面的节点；如果缓存此时超出容量，就移除最后面的节点，并从映射中删除它的键。

容量为 2 的示例演练

从零开始的 Python 实现

哨兵头节点和尾节点消除了空链表的特殊情况：每个真实节点前后始终都有节点。

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

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()   # sentinels
        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.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = self.map[key] = Node(key, value)
        self._push_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache.get(1))   # a
cache.put(3, "c")     # evicts key 2
print(cache.get(2))   # None
cache.put(1, "A")
cache.put(4, "d")     # evicts key 3
print(cache.get(3), cache.get(1), cache.get(4))  # None A d

用 OrderedDict 的简短版本

collections.OrderedDict 本身就是哈希表加双向链表的组合，move_to_end 和 popitem(last=False) 都是 O(1)。当你需要一个 LRU 缓存对象时，它是 Python 中惯用的选择。

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop least recent

c = LRU(2)
c.put("x", 1)
c.put("y", 2)
c.get("x")
c.put("z", 3)
print(list(c.data))  # ['x', 'z']

用 functools.lru_cache 缓存函数结果

要缓存函数的返回值，请使用 functools.lru_cache 装饰器。参数必须是可哈希的，因为它们会成为字典的键。cache_info() 会显示命中数、未命中数和当前大小。

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80))           # 23416728348467685
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=128, currsize=81)

maxsize=None 得到一个无上限的缓存，functools.cache（Python 3.9 及以上）正是这样做的。调用 fib.cache_clear() 可以清空它。

时间与空间复杂度

变体、常见错误与何时使用 LRU

• LFU（最不经常使用）淘汰访问次数最少的元素；它能让热门元素免受一次性扫描的冲击，但实现更复杂。
• 近似 LRU：Redis 等系统会抽样几个键，淘汰其中最旧的，而不是维护精确的列表，从而节省内存。
• TTL 缓存会让条目在固定时间后过期，通常与大小限制结合使用。
• 忘记在 get 时，或在对已有键执行 put 时把条目移到最前面，会让 LRU 退化成 FIFO。
• 忘记从哈希表中删除被淘汰的键，会留下悬空条目并造成内存泄漏。
• 在线程之间共享 LRU 缓存时，每个操作都需要加锁；functools.lru_cache 可以安全地被多个线程调用。

当最近的使用能预测未来的使用时，LRU 是个不错的默认选择。当一次大规模的一次性扫描把常用数据挤出去时，它的表现就很差；这类负载更适合 LFU 或抗扫描的策略。设计一个所有操作都是 O(1) 的 LRU 缓存，也是最常见的编程面试题之一，因为它同时考察哈希表和链表。