Algorithm

LRU 缓存

LRU 缓存在满时淘汰最久未使用的条目，用哈希表加双向链表让 get 和 put 都达到 O(1)。

LRU（Least Recently Used，最近最少使用）缓存是一种容量固定的缓存，满了以后优先淘汰最长时间没有被使用的条目。它依赖时间局部性，即最近用过的数据很可能很快再次被用到；与 FIFO 不同，每次读取都会刷新条目的位置。标准实现把按键查找节点的哈希表和按使用顺序排列的双向链表结合起来，使 get 和 put 的平均时间都是 O(1)。

LRU 以原样或近似的形式出现在系统的几乎每一层：CPU 缓存、操作系统页缓存、数据库缓冲池、Redis 的内存淘汰策略、CDN 和浏览器缓存。标准库里也有现成的实现，例如 Python 的 functools.lru_cache 和 OrderedDict，Java 的 LinkedHashMap。由于它在一个设计中同时用到哈希表和链表，也是编程面试中的经典题目。

建议先弄清 FIFO、LRU、LFU、TTL 等淘汰策略的区别以及命中率的概念，再手动跟踪一段简短的请求序列。接着用字典和带哨兵节点的双向链表亲自实现，并与 OrderedDict、LinkedHashMap 等库版本对比。最后通过练习处理线程安全、缓存失效以及与过期时间结合等实际问题。

特点

哈希表加双向链表

哈希表按键直接找到节点，链表以 O(1) 摘下节点并重新插入到头部，从而维持顺序。

O(1) 操作

get 和 put 只修改固定数量的指针，平均为常数时间；空间与容量成正比。

实用变体

实际系统常用 CLOCK、伪 LRU、采样 LRU、2Q 或 W-TinyLFU 来降低开销或抵御大规模扫描。

适用场景

函数结果记忆化
Redis 等内存数据库的内存淘汰
操作系统页缓存和数据库缓冲池
CDN 和浏览器的 HTTP 缓存

参考实现

dict 把键映射到节点，哨兵 head 与 tail 之间的双向链表保存使用顺序。get 把节点移到最前面；put 在缓存已满时淘汰 tail 前面的节点。运行 python lru_cache.py 会淘汰 "b"，输出 None 1 3。

lru_cache.py

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 = {}                           # key -> Node
        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, default=None):
        node = self.map.get(key)
        if node is None:
            return default
        self._unlink(node)                      # touch: move to the front
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if self.capacity <= 0:
            return
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) >= self.capacity:      # evict the least recently used
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)


cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")                                  # "a" is now the most recent
cache.put("c", 3)                               # full: evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c"))  # None 1 3

分步指南

共六章，带你从安装一步步了解 LRU 缓存的核心概念。

官方文档与参考资料

讨论

发起讨论

在这里提问、分享经验，交流关于 LRU 缓存的看法。

还没有讨论。来发起第一个吧。