算法面试：如何实现 O(1) 的 LFU 缓存？

题干与适用场景

实现一个固定容量的 LFUCache。get(key) 在键存在时返回值并把该键的访问频次加一，缺失时返回 -1。put(key, value) 插入新键，或更新已有键的值；更新已有键也算一次访问。新键的初始频次是 1。容量满时插入新键，先淘汰访问频次最低的键；若多个键频次相同，淘汰其中最久未使用的键。

要求 get 和 put 都达到基于哈希表平均性能的期望 O(1)。容量可以为 0，此时 put 没有效果。题目限定为单线程、内存内数据结构，不包含 TTL、按字节计费、持久化或分布式一致性。

2025 年 12 月的中文公开面试记录明确列出 LFU 缓存，2026 年的公开题目页也保留了同一问题。LeetCode 460 给出了稳定契约，O(1) LFU 论文则给出双层链式结构的理论依据。这些证据足以说明题目在当前面试环境仍有代表性；公开信息无法独立核验唯一的公司归属，因此元数据中的 companyName 保持为空。

面试官考察点

第一项是能否从两个淘汰维度推导结构。按键查找需要哈希表；按频次找受害者需要频次索引；同一频次内还要维护最近使用顺序。单个堆可以找最小频次，但每次命中都要更新堆，复杂度通常为 O(log capacity)。

第二项是状态不变量。强回答会说明每个键只对应一个节点，每个节点只属于一个与自身频次一致的桶；桶内从新到旧排列；minFrequency 始终指向现存最小频次。只背“两个 Map 加双向链表”无法解释空桶删除、更新已有键或容量为 1 时的行为。

第三项是同频规则。节点从频次 f 升到 f + 1 时，应放到新桶的最近端，因为这次访问刚发生。淘汰则从最小频次桶的最旧端取节点。若桶只使用无序集合，LFU 的第一层规则成立，同频 LRU 规则会丢失。

最后看复杂度证明和测试。每次操作只能做常数次哈希访问、桶定位和链表摘插。测试还要覆盖频次并列、旧最小桶变空、更新已有键提升频次、容量 0，以及长随机序列下与慢速参考实现的差分结果。

回答前需要澄清的问题

• 更新已有键会增加频次吗？ 本题会。put 修改已有值后执行与成功 get 相同的提升逻辑。
• 同频如何破除并列？ 使用该频次内的 LRU：最久没有被成功 get 或更新 put 的键先淘汰。
• 新键从频次 0 还是 1 开始？ 插入本身代表一次使用，因此从 1 开始。
• 容量 0 是否合法？ 合法；所有 put 都直接返回，get 始终 miss。
• 复杂度是严格最坏 O(1) 吗？ 链表修改是最坏常数次；普通 Map 提供常见的平均或期望常数时间，因此整体表述为期望 O(1)。
• 频次会不会无限增长？ 面试实现通常使用安全范围内的整数。长期运行的生产实现需要处理计数溢出、老化或频次重标定，这会改变契约。
• 需要线程安全吗？ 本题不需要。get 会改频次和顺序，并发版本必须把跨多个结构的变更放在同一临界区。

30 秒回答框架

“我会用一个 Map 把键定位到节点，再用另一个 Map 把频次定位到双向链表。每条链表只保存同频节点，头侧最新、尾侧最旧；minFrequency 直接指出淘汰桶。成功 get 或更新 put 会把节点从频次 f 的链表摘下，必要时删除空桶，然后把频次加一并插到新桶头部。插入新键时，若已满就从 minFrequency 桶尾删除一个节点，再把新节点放进频次 1 桶并把最小频次设为 1。每一步只有常数次 Map 和指针操作，所以 get、put 期望 O(1)，空间 O(capacity)。”

分步骤深入解答

第一步：先排除不满足复杂度的直观方案

哈希表保存 key -> {value, frequency, lastUsed} 后，每次淘汰扫描全部键，成本是 O(capacity)。最小堆能把淘汰降到 O(log capacity)，但成功访问会修改频次和最近时间，仍需位置索引与堆调整。按 (frequency, time) 排序的平衡树同样是 O(log capacity)。

期望 O(1) 需要把排序拆开。频次之间通过 Map 直接定位；每个频次内部只维护最近性，用双向链表完成已知节点的摘除、头插和尾删。当前最小频次再由一个整数直接保存。

第二步：定义四条不变量

1. nodes 中每个键恰好指向一个真实节点，所有真实节点也恰好出现在 nodes 中。
2. 频次为 f 的节点只出现在 frequencyLists.get(f) 中；Map 中不保留空链表。
3. 每个频次链表从头到尾按最近使用到最久未使用排列。
4. 缓存非空时，minFrequency 等于所有节点频次的最小值；缓存为空时为 0。

一次提升只从 f 移到 f + 1。若原桶恰好是最小桶且移动后变空，新的最小值必然是 f + 1：低于 f 的桶原本就不存在，而刚移动的节点保证 f + 1 桶存在。插入新键后频次 1 一定是最小值，因此直接把 minFrequency 设为 1。

第三步：实现节点与频次链表

双向链表使用头尾哨兵，减少空链表、单节点和端点删除的条件分支。节点保存键，淘汰时才能同步删除 nodes 中的映射。

class Entry {
  frequency = 1
  prev: Entry | null = null
  next: Entry | null = null

  constructor(
    readonly key: number,
    public value: number,
  ) {}
}

class FrequencyList {
  private readonly head = new Entry(0, 0)
  private readonly tail = new Entry(0, 0)
  size = 0

  constructor() {
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  addFirst(node: Entry): void {
    node.prev = this.head
    node.next = this.head.next
    this.head.next!.prev = node
    this.head.next = node
    this.size += 1
  }

  remove(node: Entry): void {
    node.prev!.next = node.next
    node.next!.prev = node.prev
    node.prev = null
    node.next = null
    this.size -= 1
  }

  removeLast(): Entry {
    const node = this.tail.prev
    if (!node || node === this.head) {
      throw new Error("cannot remove from an empty frequency list")
    }
    this.remove(node)
    return node
  }
}

两个哨兵不属于缓存，不进入 nodes，也不计入容量。remove 只接收已经位于当前链表中的真实节点；这个前置条件由 LFUCache 的不变量保证。

第四步：实现提升、读取和写入

class LFUCache {
  private readonly nodes = new Map<number, Entry>()
  private readonly frequencyLists = new Map<number, FrequencyList>()
  private minFrequency = 0

  constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity < 0) {
      throw new RangeError("capacity must be a non-negative integer")
    }
  }

  get(key: number): number {
    const node = this.nodes.get(key)
    if (!node) return -1

    this.promote(node)
    return node.value
  }

  put(key: number, value: number): void {
    if (this.capacity === 0) return

    const existing = this.nodes.get(key)
    if (existing) {
      existing.value = value
      this.promote(existing)
      return
    }

    if (this.nodes.size === this.capacity) {
      const victimList = this.frequencyLists.get(this.minFrequency)
      if (!victimList) throw new Error("missing minimum-frequency list")

      const victim = victimList.removeLast()
      this.nodes.delete(victim.key)
      if (victimList.size === 0) {
        this.frequencyLists.delete(this.minFrequency)
      }
    }

    const node = new Entry(key, value)
    this.getOrCreateList(1).addFirst(node)
    this.nodes.set(key, node)
    this.minFrequency = 1
  }

  private promote(node: Entry): void {
    const oldFrequency = node.frequency
    const oldList = this.frequencyLists.get(oldFrequency)
    if (!oldList) throw new Error("missing source frequency list")

    oldList.remove(node)
    if (oldList.size === 0) {
      this.frequencyLists.delete(oldFrequency)
      if (this.minFrequency === oldFrequency) {
        this.minFrequency = oldFrequency + 1
      }
    }

    node.frequency = oldFrequency + 1
    this.getOrCreateList(node.frequency).addFirst(node)
  }

  private getOrCreateList(frequency: number): FrequencyList {
    let list = this.frequencyLists.get(frequency)
    if (!list) {
      list = new FrequencyList()
      this.frequencyLists.set(frequency, list)
    }
    return list
  }
}

更新已有键必须先于容量判断。它没有增加条目数，不应淘汰任何键；但它会提升频次并刷新桶内最近性。插入新键时，淘汰发生在插入之前，此时 minFrequency 仍准确指向受害者所在桶。

第五步：证明正确性与复杂度

初始化时四条不变量成立。miss 不改变状态。成功访问从正确的旧桶删除一个节点，再把同一节点以新频次放到新桶最近端；成员集合不变，桶归属和最近顺序更新，空最小桶的处理保持最小频次正确。

更新已有键只额外修改值，随后走同一提升流程。插入新键前若已满，从最小频次桶尾部选出的节点同时满足最低频次和该频次内最旧两个条件；从链表与 nodes 删除后，成员集合仍一致。新节点进入频次 1 的最近端，minFrequency = 1 恢复全部不变量。

每个方法只有固定次数的 Map 查找、插入或删除，以及固定次数的链表指针修改，所以在 Map 平均性能假设下，get 与 put 都是期望 O(1)。每个真实节点只存在于一个 Map 和一条链表，频次桶数量不超过节点数量，空间为 O(capacity)。

第六步：用轨迹与差分测试验证

容量为 2 时执行以下序列：

put(1, 10)  -> 1 的频次为 1
put(2, 20)  -> 1、2 同频，2 更新
get(1)      -> 返回 10；1 的频次升为 2
put(3, 30)  -> 淘汰频次为 1 的 2
get(3)      -> 返回 30；3 的频次升为 2，且比 1 更新
put(4, 40)  -> 1、3 同频，淘汰更旧的 1

测试集还应覆盖容量 0、容量 1、miss 不改状态、更新已有键、连续提升导致最小桶消失，以及相同频次的多次顺序变化。更强的验证方式是写一个 O(capacity) 扫描受害者的参考实现，用确定性随机操作流逐步比较每次 get 的返回值和最终可见键值。这样能发现只在长序列后暴露的 minFrequency 漂移和链表断链。

高质量示范回答

“我先确认规则：新键频次为 1，成功 get 和更新已有键的 put 都增加频次；同频时按最近使用顺序淘汰；容量 0 合法。目标是基于 Map 平均性能的期望 O(1)。

我会维护 key -> node、frequency -> doubly linked list 和 minFrequency。节点保存键、值、频次和链表指针。同一频次链表的头侧最新、尾侧最旧。命中时把节点从 f 桶摘下，旧桶为空就删除；若它还是最小桶，最小频次升到 f+1。然后把节点放进 f+1 桶头部。

插入时，已有键只改值并提升，不做淘汰。新键且缓存已满时，从最小频次桶尾删除节点，并同步删键索引；随后把新节点插入频次 1 桶并把最小频次重置为 1。核心不变量是键与节点一一对应、节点只在正确频次桶、桶内保持最近顺序、最小频次准确。每步只有常数次哈希和指针操作，空间与容量线性。

我会用容量 2 的并列淘汰轨迹、容量 0 和 1、更新已有键、最小桶变空做单测，再用慢速扫描实现跑随机差分测试。生产扩展还要单独定义频次老化、溢出、并发和 TTL，不能把这些要求塞进当前复杂度结论。”

常见错误

• 只维护 key -> frequency → 淘汰时仍要扫描所有键 → 用最小频次指针直接定位桶。
• 频次桶使用无序集合 → 无法确定同频最旧键 → 每个桶维护一条双向 LRU 链表。
• 提升后把节点放到桶尾 → 刚访问的键反而被视为最旧 → 把提升节点插到最近端。
• 旧桶为空时仍保留 → minFrequency 可能指向没有受害者的桶 → 立即删除空桶，并在必要时推进最小频次。
• 更新已有键前先做容量淘汰 → 条目数没有增长却误删其他键 → 先识别已有键，改值并提升后返回。
• 淘汰只删链表节点 → 键 Map 留下幽灵节点 → 两个结构同步删除同一键。
• 新键插入后不重置最小频次 → 下一次淘汰可能跳过频次 1 → 每次新插入都设为 1。
• 把堆方案写成 O(1) → 命中后的频次更新需要堆调整 → 承认 O(log capacity)，或改用频次桶。
• 声称严格 O(1) → 普通 Map 的复杂度依赖平均哈希性能 → 表述为期望 O(1)。
• 只跑官方示例 → 很难覆盖空桶与并列顺序漂移 → 加入不变量检查和随机差分测试。

追问及应对

追问一：为什么 minFrequency 在最小桶清空时只加一？

节点一次只从 f 升到 f + 1。如果 f 是当前最小值且旧桶清空，所有其他节点的频次原本都至少为 f + 1，刚提升的节点又保证 f + 1 桶存在。因此新最小值恰好是 f + 1，不需要向上扫描。淘汰后若缓存马上插入新键，最终仍会重置为 1。

追问二：怎样支持 TTL？

TTL 引入按过期时间淘汰的第二套顺序。命中时先检查过期，容量淘汰前也可能需要清理过期项。最小堆可按过期时间组织，但更新和删除通常变为 O(log n)；时间轮能降低成本，却引入精度与更多状态。必须先定义“过期优先还是 LFU 优先”，再重新给出复杂度。

追问三：频次长期增长会怎样？

计数可能溢出，历史热点也可能长期占据缓存。可按周期衰减频次、在全局最小值增长到阈值时重标定，或使用带时间衰减的近似策略。任何全量重标定都会产生阶段性 O(n) 工作；若要求稳定延迟，需要增量迁移或摊销方案，并清楚说明它与本题精确累计频次的契约差异。

追问四：怎样改成线程安全？

最简单的正确方案是一把互斥锁包住完整 get 和 put，因为成功 get 会同时修改节点频次、两个桶和最小频次。分片能降低竞争，但每个分片会独立淘汰，结果不再等同于一个精确全局 LFU。细粒度锁还要固定键索引、旧桶、新桶的加锁顺序，并防止淘汰与提升交错。

追问五：LFU 一定比 LRU 更好吗？

选择取决于访问分布。LFU 能保留反复访问的长期热点，但对历史热点适应较慢；LRU 对工作集切换更敏感，实现也更小。生产缓存常使用频次老化、准入策略或近似算法来平衡两者。面试实现的价值在于精确验证复合淘汰规则，不代表所有生产负载都应采用纯 LFU。

追问六：为什么动态 Top-K 的频次桶不能直接复用？

动态 Top-K 只需要按频次枚举结果，同频顺序通常可以任意。本题还要在容量满时精确淘汰，并要求同频 LRU，所以每个桶必须保存最近顺序，节点更新也要刷新该顺序。两者都使用频次桶，但接口、不变量和正确性目标不同。