LRU 快取與資料結構的選擇

快取放不下時，要丟掉誰

快取（cache）是把「最近可能還會用到」的資料放在比較快的地方：瀏覽器把看過的圖片存在本機、 資料庫把常讀的資料頁留在記憶體、CPU 把剛讀過的記憶體內容放在晶片上。快取比原來的地方快，但容量有限， 放滿之後要放新資料，就得先丟掉一筆。決定丟掉誰的規則叫淘汰策略（eviction policy）。

LRU（least recently used，最近最少使用）的規則是：丟掉最久沒被用過的那一筆。 背後的想法是：剛用過的資料，很可能馬上又會用到；很久沒碰的，大概暫時用不到了。

LRU 快取要支援兩個操作，而且希望都是 O(1)，因為快取就是為了快：

這一課把前面學過的兩個結構組合起來完成它，最後整理整個資料結構軌：遇到一個問題，怎麼挑資料結構。

只用一種結構都不夠

LRU 要同時做到兩件事：用 key 很快找到資料，以及很快調整與找出使用順序。

每種結構都只擅長一半。解法是兩種一起用，各管一件事：

• 雜湊表：key → 節點。負責「用 key 找到資料」，O(1)
• 雙向鏈結串列：依使用順序串起所有節點，最前面最近用過，最後面最久沒用。負責「調整順序」與「找出最久沒用的」

關鍵在雜湊表存的不是值，而是串列裡那個節點的位置（Python 是物件參考、C++ 是指標、Java 是參考）。 拿到節點之後，從串列裡拿掉、再接到最前面，只要改幾個指標，不必在串列裡找。

還有兩個細節：

1. 為什麼要雙向：從串列拿掉一個節點，要改「前一個節點的 next」。單向串列不知道前一個是誰，只能從頭找（第 06 課）；雙向串列的 node.prev 直接就是。
2. 節點裡要存 key：淘汰時拿到的是串列尾端的節點，要把它從雜湊表刪掉，得知道它的 key 是什麼。

各語言的現成做法

實際寫程式時，Python 和 Java 都有「雜湊表＋雙向串列」的現成容器，幾行就能做出 LRU。

Python：collections.OrderedDict 會記住 key 的順序。move_to_end(key) 把 key 搬到最後面， popitem(last=False) 拿掉最前面的一筆（last 預設是 True，拿最後面的）。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()          # 依使用順序排：最前面最久沒用

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)         # 用過了，搬到最後面
        return self.data[key]

    def put(self, key, val):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = val
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)  # 拿掉最前面（最久沒用）的

要快取的是「函數的回傳值」時，直接用 functools.lru_cache 裝飾器，它內部就是 LRU。

Java：LinkedHashMap 有一個建構子 LinkedHashMap(initialCapacity, loadFactor, accessOrder)，accessOrder 設成 true， 走訪順序就是「最久沒存取的在前、最近存取的在後」；再覆寫 removeEldestEntry，每次放入新資料後，它會問要不要移除最舊的一筆。

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LRUCache(int capacity) {
        super(16, 0.75f, true);            // true：依存取順序排列
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;          // 超過容量就移除最久沒用的
    }
}

使用時 cache.getOrDefault(key, -1) 取值、cache.put(key, val) 放入；get、put、getOrDefault 都算一次存取。

C++：標準函式庫沒有現成的，通常用 list（雙向鏈結串列）加 unordered_map 存「key → 串列裡的位置（迭代器）」。 list::splice 可以把一個節點搬到另一個位置，不必複製、也不會讓指向它的迭代器失效：

int capacity = 3;
list<pair<int, int>> items;                                // 最前面最近用過
unordered_map<int, list<pair<int, int>>::iterator> pos;    // key → 在 items 裡的位置

int get(int key) {
    auto it = pos.find(key);
    if (it == pos.end()) return -1;
    items.splice(items.begin(), items, it->second);        // 搬到最前面，O(1)
    return it->second->second;
}

void put(int key, int val) {
    auto it = pos.find(key);
    if (it != pos.end()) {
        it->second->second = val;
        items.splice(items.begin(), items, it->second);
        return;
    }
    if ((int)items.size() == capacity) {
        pos.erase(items.back().first);                     // 串列節點存著 key
        items.pop_back();
    }
    items.push_front({key, val});
    pos[key] = items.begin();
}

三種寫法的結構和前面自己做的完全相同：雜湊表找節點，雙向串列管順序。

依操作挑資料結構

LRU 的解法示範了選資料結構的一般步驟：

1. 列出程式要做哪些操作，以及各自多常做（LRU：用 key 查、更新順序、找最舊的）
2. 找出每個操作最適合的結構，看它的成本（查表）
3. 沒有一種結構能讓所有操作都夠快時，組合兩種，讓它們指向同一份資料
4. 最後才考慮記憶體、常數、程式好不好寫、語言有沒有內建

整個資料結構軌學過的結構，依「要做什麼」整理如下（n 是元素個數；雜湊表是平均情況）：

常見的組合還有：雜湊表＋堆積（優先佇列裡的元素要能依 key 找到並修改優先順序）、 平衡樹＋雜湊表（依 key 查的同時維持排名）。看到一個需求同時要求兩種很不一樣的操作時，先想想能不能讓兩個結構指向同一份資料。

重點整理

• 快取容量有限，放滿時依淘汰策略丟掉一筆；LRU 丟掉最久沒用的
• 只用陣列記順序：更新順序與淘汰是 O(n)；只用串列：找 key 是 O(n)；只用雜湊表記時間：找最舊的是 O(n)
• 雜湊表（key → 節點）＋雙向鏈結串列（依使用順序）：get、put、淘汰都是 O(1)。串列要雙向，拿掉節點才不必找前一個；節點要存 key，淘汰時才能刪雜湊表
• 頭尾哨兵節點讓插入與刪除不必處理空串列與頭尾的特殊情況
• Python 用 OrderedDict（move_to_end、popitem(last=False)）或 functools.lru_cache；Java 用 LinkedHashMap(容量, 0.75f, true) 加 removeEldestEntry；C++ 用 list 加 unordered_map 與 splice
• 選資料結構：先列出操作與頻率，查每種結構的成本；一種不夠就組合兩種，讓它們指向同一份資料

資料結構軌到這裡結束。十八課裡的每一種結構都是在「哪些操作要快、願意多付出多少空間」之間的一種取捨； 遇到新問題時，從要做的操作出發，你就能判斷該用哪一種，或怎麼把它們組合起來。演算法軌會繼續用這些結構解決排序、搜尋、最短路徑等問題。