LRU 緩存：實用主義者

演算法背後的故事：桌上的一摞紙

想像妳的桌子亂糟糟的，上面只有一摞文件。

• 當妳閱讀一份文件時，妳把她抽出來，放在這摞紙的最頂端。
• 當妳收到一份新文件時，妳也把她放在最頂端。
• 當這摞紙太高，搖搖欲墜時，妳從最底端抽出一張紙，扔進垃圾桶。

這就是 LRU (最近最少使用)。底部的紙是妳最長時間沒有碰過的。邏輯告訴我們，如果妳已經好幾天沒看她了，那妳接下來的 5 分鐘裡大概率也不需要她。

LRU 是幾乎所有緩存系統（從 CPU 緩存到 Redis）的預設策略，因為她完美契合了人類的行為模式：我們傾向於在一段時間內專注於幾件事。

為什麼需要它？

• 瀏覽器： 當妳點擊「後退」按鈕時，瀏覽器能瞬間顯示頁面，因為該頁面就在 LRU 緩存中。
• 作業系統： 哪些記憶體頁面應該保留在 RAM 中？當然是用戶正在點擊的那些。
• 簡單性： 她易於理解，且對 90% 的工作負載都出奇地有效。

演算法是如何「思考」的

這個演算法需要快速 ($O(1)$) 做兩件事：

1. 找到 一個鍵 (Map)。
2. 移動 那個鍵到「頂端」 (List)。

這需要一種混合結構：哈希表 + 雙向鏈表。

1. 存取 (Get)：

   • 在 Map 中查找節點。
   • 將節點從鏈表當前位置斷開。
   • 將其掛載到 頭部 (最近使用)。
   • 返回值。

2. 插入 (Put)：

   • 如果鍵存在：更新值，移動到頭部。
   • 如果鍵是新的：創建節點，添加到頭部，存入 Map。
   • 驅逐 (Eviction)： 如果緩存滿了，看向 尾部 (最近最少使用)。從鏈表和 Map 中移除她。

工程決策：重活累活

雖然 LRU 很棒，但她並不完美。

• 掃描問題 (Scan Problem)： 如果一個用戶一次性請求了 100 萬個數據（比如「全表掃描」），她們會沖刷掉妳整個有價值的緩存，把那些高頻使用的熱點數據全部替換成這種「只用一次」的數據。
• 並發： 為了把項目移到「頭部」，妳需要鎖定鏈表。在多執行緒系統中，這種「鎖競爭」會拖慢一切。

實作參考 (Python)

Python 的 collections.OrderedDict 讓這件事變得微不足道，但讓我們構建內部邏輯，以窺探機器的靈魂。

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {} # Map: key -> Node
        # 啞元頭尾節點，避免複雜的邊界檢查
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # 1. 從當前位置移除
            self._remove(node)
            # 2. 移到頭部 (最近使用)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        
        node = Node(key, value)
        self._add_to_head(node)
        self.cache[key] = node

        if len(self.cache) > self.capacity:
            # 驅逐 LRU (尾部之前的那個節點)
            lru_node = self.tail.prev
            self._remove(lru_node)
            del self.cache[lru_node.key]

# 使用範例
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1)) # 返回 1, 將 1 移至頭部. 緩存: [1, 2]
lru.put(3, 3)     # 驅逐 2 (LRU). 緩存: [3, 1]
print(lru.get(2)) # 返回 -1 (未找到)

小結

LRU 教會我們：時間是最好的過濾器。透過假設過去能預測未來，我們可以做出在大多數情況下都正確的簡單決策。她提醒我們，在一個快節奏的世界裡，「妳最近為我做了什麼？」並不是一種侮辱——而是一種優化。