LFU 緩存：歷史學家

演算法背後的故事：名人堂

想像一個只能容納 5 座雕像的名人堂。

• 誰能獲得一座雕像？不是那個昨天做了一件酷事的人（那是 LRU）。
• 雕像是留給那個在歷史上做酷事次數最多的人的。

如果麥可·喬丹（頻率：10,000）已經 10 年沒打球了，他依然留在名人堂裡。如果一個新秀（頻率：1）昨晚剛剛砍下 50 分，他依然進不去。

這就是 LFU (最不經常使用)。它保護「經典」。它假設如果一條數據被請求了 500 次，那它本質上就是重要的，即使過去一小時沒人問津。

為什麼需要它？

• 靜態資源： Google 的 Logo、CSS 重置文件、「首頁」圖標。這些東西被持續不斷地存取。LRU 可能會在一次「掃描」（一次性突發流量）中意外驅逐她們。LFU 保護她們。
• CDN (內容分發網絡)： 無論當前幾點鐘，始終把最受歡迎的影片緩存在邊緣節點。

演算法是如何「思考」的

在 $O(1)$ 時間內實作 LFU 出了名的難。妳需要：

1. 追蹤每個鍵的 頻率。
2. 當緩存滿時，找到 min(頻率) 對應的鍵。
3. 如果平局（多個鍵頻率都是 1），驅逐她們當中 最近最少使用 的那個。

$O(1)$ 的解法需要一個複雜的結構：雙向鏈表的哈希映射。

• Map<頻率, List<Node>>：「列表 1」裝著所有頻率為 1 的項。「列表 5」裝著所有頻率為 5 的項。
• min_freq：一個指標，永遠指向當前非空的最小頻率列表。

1. 存取 (Get)：

   • 找到節點。freq 變為 freq + 1。
   • 從 List[freq] 中移除節點。
   • 加入到 List[freq + 1] 中。
   • 如果 List[min_freq] 空了，更新 min_freq。

2. 插入 (Put)：

   • 如果是新的：加入 List[1]。min_freq 變為 1。
   • 如果滿了：去 List[min_freq]。移除那個特定列表中的 LRU 節點。

工程決策：過去的幽靈

LFU 有一個致命缺陷：緩存污染 (Memory Pollution)。

• 問題： 想像一篇關於「2020 年奧運會」的新聞。她在兩週內獲得了 100 萬次點擊。她的頻率極高。
• 後果： 三年後，沒人關心了。但因為她的頻率是 100 萬，她永遠坐在緩存裡，佔據著新內容的位置。
• 修復： 現代 LFU（如 Window-TinyLFU）使用「老化」或「衰減」機制。每隔一小時，將所有頻率除以 2。這迫使舊日的英雄最終退休。

實作參考 (Python)

這是一個使用「列表映射」策略的簡化版 $O(1)$ 實作。

import collections

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_node = {} # Map<Key, Node>
        self.freq_to_nodes = collections.defaultdict(collections.OrderedDict)

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        
        node = self.key_to_node[key]
        # 1. 晉升頻率
        val = node.value
        self._update_freq(node)
        return val

    def _update_freq(self, node):
        # 從當前頻率列表移除
        freq = node.freq
        del self.freq_to_nodes[freq][node.key]
        
        # 如果該列表空了且曾是最小頻率，讓 min_freq 遞增
        if not self.freq_to_nodes[freq] and self.min_freq == freq:
            self.min_freq += 1
        
        # 加入下一個頻率列表
        node.freq += 1
        self.freq_to_nodes[node.freq][node.key] = node

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0: return

        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.value = value
            self._update_freq(node)
            return

        if len(self.key_to_node) >= self.capacity:
            # 從 min_freq 列表中驅逐
            # popitem(last=False) 彈出第一項 (符合 FIFO/LRU 規則)
            k, v = self.freq_to_nodes[self.min_freq].popitem(last=False)
            del self.key_to_node[k]

        # 添加新節點
        new_node = Node(key, value)
        self.key_to_node[key] = new_node
        self.freq_to_nodes[1][key] = new_node
        self.min_freq = 1

小結

LFU 教會我們：忠誠很重要。透過看重長期熱度而非短期潮流，她為「經典」創造了一個穩定的環境。但她也警告我們：永遠不要讓過去拖累未來。即使是傳奇，最終也必須為新一代讓位。