开发者日记

外观

一文搞懂 LFU：双哈希加频次链表实战 ​

为什么热点缓存需要 LFU ​

缓存的核心矛盾很简单：容量有限，而访问数据无限。当缓存满时，系统必须选择一个键淘汰。LRU 会淘汰最近最久未使用的数据，适合“最近访问代表未来价值”的场景；但如果一次性扫描大量冷数据，LRU 很容易把真正长期被访问的热点数据挤掉。

LFU（Least Frequently Used，最不经常使用）依据访问频次做决策，优先淘汰访问次数最少的数据。它更适合热点分布稳定、重复访问明显的业务，例如商品详情、配置项、用户画像中的高频字段。

本文实现一个支持两个操作的 LFU 缓存：

  • get(key)：存在则返回值，并将该键访问频次加一；否则返回 -1。
  • put(key, value)：插入或更新；容量满时淘汰当前最小频次中的一个键。

两个操作都要求平均时间复杂度为 O(1)。

方案对比：单堆、双哈希与频次链表 ​

最直观的方法是使用最小堆，堆顶保存“频次最小、时间最早”的节点。但每次访问都要修改频次并重新调整堆，时间复杂度通常是 O(log n)，而且堆中旧节点的延迟删除也容易引入边界问题。

更经典的 O(1) 方案使用三类结构：

  1. key_map：键到节点的哈希表，用于快速定位节点。
  2. freq_map：频次到双向链表的哈希表，同一频次的节点放在一条链表中。
  3. min_freq：记录当前最小频次，淘汰时直接访问该频次链表。

节点在链表中的顺序也有价值：新加入或刚提升到某频次的节点放到头部，尾部就是该频次下最早进入的节点。当多个键频次相同时，可以稳定淘汰最久没有发生频次变化的键。

key_mapkey → 节点频次 1 链表频次 2 链表频次 k 链表min_freq 指针

节点与双向链表设计 ​

双向链表节点需要保存四类信息：键、值、频次，以及前后指针。键不能省略，因为淘汰链表节点后，还要通过节点中的键反向删除 key_map 中的记录。

python
class Node:
    def __init__(self, key=0, value=0, freq=1):
        self.key = key
        self.value = value
        self.freq = freq
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        # 使用虚拟头尾节点，减少空链表边界判断
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_front(self, node):
        # 新节点放头部，表示同频次下最新发生变化
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        # O(1) 摘除已知节点
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        self.size -= 1

    def pop_back(self):
        # 尾部节点是当前频次下最早进入的节点
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node

为什么同频次还要维护顺序？因为 LFU 只规定淘汰频次最低者，并没有规定频次相同怎么办。把同频次节点按变化时间排列，可以在平局时采用近似 LRU 的策略，降低突发访问对旧热点的影响。

手写 LFU 缓存完整代码 ​

下面代码可直接运行，并附带简单测试。核心在于 _increase_freq：节点每次被访问或更新后，都要从旧频次链表摘除，再加入新频次链表头部。

python
from collections import defaultdict


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_map = {}
        self.freq_map = defaultdict(DoublyLinkedList)
        self.min_freq = 0

    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        node = self.key_map[key]
        self._increase_freq(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        # 容量为 0 时，任何写入都无法保留
        if self.capacity <= 0:
            return

        if key in self.key_map:
            node = self.key_map[key]
            node.value = value
            self._increase_freq(node)
            return

        # 新键插入前先处理淘汰
        if len(self.key_map) >= self.capacity:
            removed = self.freq_map[self.min_freq].pop_back()
            # 被淘汰节点一定能在 key_map 中找到
            del self.key_map[removed.key]

        new_node = Node(key, value, freq=1)
        self.key_map[key] = new_node
        self.freq_map[1].add_front(new_node)
        # 插入新键后，全局最小频次必然回到 1
        self.min_freq = 1

    def _increase_freq(self, node: Node) -> None:
        old_freq = node.freq
        old_list = self.freq_map[old_freq]
        old_list.remove(node)

        # 如果旧链表为空，且旧频次正是最小频次，则最小频次加一
        if old_list.size == 0 and old_freq == self.min_freq:
            self.min_freq += 1

        node.freq += 1
        self.freq_map[node.freq].add_front(node)


# 测试用例
cache = LFUCache(2)
cache.put(1, 10)
cache.put(2, 20)
print(cache.get(1))   # 10，此时 key 1 频次为 2，key 2 频次为 1
cache.put(3, 30)      # 淘汰频次最小的 key 2
print(cache.get(2))   # -1
print(cache.get(3))   # 30

频次提升与淘汰流程 ​

一次 get 命中看似只是把计数加一，但底层要保证三个状态同时一致：节点频次、频次链表、最小频次。顺序不能颠倒。

命中 key_map取得节点移出旧频次链表判断是否为空必要时更新min_freq加入新频次链表节点频次加一

需要特别注意：只有当旧频次链表变空，并且它恰好等于 min_freq 时，才能将最小频次加一。如果变空的是更高频次链表，不应该影响最小频次；如果旧最小频次链表中还有其他节点，也不能递增。

复杂度分析 ​

  • get：通过 key_map 找节点是 O(1)；从双向链表摘除已知节点是 O(1)；插入新频次链表也是 O(1)。
  • put：命中更新与 get 相同；未命中时通过 min_freq 直接找到目标链表，淘汰尾节点为 O(1)。
  • 空间复杂度：每个键只保存一个节点，并出现在一个频次链表中，因此为 O(capacity)。

相比堆方案，双哈希加频次链表把“查找最小频次”从动态排序问题变成了维护一个整数指针，这正是该设计能够达到均摊 O(1) 的关键。

避坑总结：这些边界最容易写错 ​

1. 更新已有键时忘记增加频次 ​

常见错误现象是：put 已存在的键只修改 value，没有调用频次提升逻辑。结果某个键被反复写入却始终保持低频，最终可能被错误淘汰。修正方式是把“命中”统一视为一次访问：更新值后必须执行 _increase_freq。

2. 先修改节点频次，再去旧链表删除 ​

有实现先写 node.freq += 1，再通过 freq_map[node.freq] 找旧链表，实际上找到的是新频次链表，导致链表指针错乱，甚至出现节点泄漏。正确顺序是先保存 old_freq，从旧链表摘除，再更新频次并加入新链表。

3. 删除空链表后盲目维护 min_freq ​

典型错误是只要某个频次链表为空，就删除该键或把 min_freq 加一。这会误判更高频次链表，或者在最小频次仍有其他节点时错误推进。必须同时满足两个条件：旧链表大小为零，且 old_freq == self.min_freq。

4. 节点中不保存 key ​

淘汰时只能从链表尾部拿到节点。如果节点结构只有 value 没有 key，就无法反向删除 key_map，长期运行后哈希表会保留无效键，造成容量统计错误。因此节点必须携带原始键。

5. 忽略容量为 0 的边界 ​

当 capacity = 0 时，插入新键后立刻淘汰会触发空链表弹出尾节点，返回 None，再访问 removed.key 就会抛出异常。构造函数或 put 入口应直接处理零容量与负容量。

6. 认为 LFU 一定优于 LRU ​

LFU 能提升稳定热点命中率，但它对历史频次有路径依赖。一个曾经高频、现在不再访问的键可能长期占据缓存；新的潜在热点也可能因为初始频次低而被频繁淘汰。工程上可以加入时间衰减、窗口计数，或在同频次内使用 LRU 顺序。本文把新提升节点放在链表头部，就是最简单的平局优化。

双哈希加频次链表的本质，是用空间和指针换时间：哈希负责定位，链表负责同频次序，min_freq 负责直达淘汰目标。掌握这三个角色的职责边界，LFU 的代码就不再是靠背模板，而是可以根据业务特征稳定推演出来。

免责声明

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

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

免责声明

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