演算法面試：如何實作 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，所以每個桶必須保存最近順序，節點更新也要刷新該順序。兩者都使用頻次桶，但介面、不變條件和正確性目標不同。