Terry Yao's Blog

algorithmsLRU Cache 最近最少使用快取
algorithms

LRU Cache 最近最少使用快取

閱讀時間約 6 分鐘

cover

LRU Cache 是面試最愛考的「設計題」，也是你每天都在受益但沒意識到的東西。

兩個結構湊出 O(1)

LRU Cache = HashMap（O(1) 查找）+ 雙向鏈表（O(1) 維護使用順序）。容量滿了淘汰最久沒用的。get 和 put 都是 O(1)。瀏覽器快取、CDN、資料庫、Redis 的記憶體淘汰策略，底層都有它。

運作方式

容量: 3
 
put(1) → [1]
put(2) → [2, 1]
put(3) → [3, 2, 1]
get(1) → [1, 3, 2]      ← 1 被用到，移到最前面
put(4) → [4, 1, 3]      ← 滿了，淘汰最久沒用的 2
get(2) → -1             ← 2 已經被淘汰了

規則只有一條：每次存取都把該元素移到最前面，淘汰從最後面開始。

為什麼是 HashMap + 雙向鏈表？

先想想不用這組合會怎樣：

  • 只用 Array？找元素 O(n)，移動元素 O(n)，全都慢
  • 只用 HashMap？沒有順序概念，不知道誰最久沒用
  • 只用鏈表？找元素 O(n)
  • HashMap + 單向鏈表？找到元素了但刪不掉——因為要知道前一個節點才能刪，得再走一遍 O(n)

HashMap + 雙向鏈表才是正解：HashMap O(1) 找到節點，雙向鏈表 O(1) 刪除它（因為有 prev 指標），再 O(1) 插到頭部。

核心操作

int get(int key) {
    if (!map.containsKey(key)) return -1;
    Node node = map.get(key);
    moveToHead(node);  // 用到了就移到最前面
    return node.value;
}
 
void put(int key, int value) {
    if (map.containsKey(key)) {
        Node node = map.get(key);
        node.value = value;
        moveToHead(node);
    } else {
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToHead(newNode);
        if (map.size() > capacity) {
            Node tail = removeTail();  // 淘汰最久沒用的
            map.remove(tail.key);
        }
    }
}

上面 get/put 呼叫的 moveToHead、addToHead、removeTail，拆開來其實只是幾行指標接線。之所以每一個都是 O(1)，關鍵就在雙向鏈表的 prev：

void addToHead(Node node) {   // 接到 dummy head 後面
    node.prev = head;
    node.next = head.next;
    head.next.prev = node;
    head.next = node;
}
 
void removeNode(Node node) {  // 前後兩鄰居直接牽手，把自己跳過
    node.prev.next = node.next;
    node.next.prev = node.prev;
}
 
void moveToHead(Node node) {  // 「用到了」= 先拔掉再插回最前面
    removeNode(node);
    addToHead(node);
}
 
Node removeTail() {           // 淘汰：拿 dummy tail 前一個開刀
    Node node = tail.prev;
    removeNode(node);
    return node;
}

removeNode 敢寫得這麼乾淨，全靠 node.prev 隨手可得——單向鏈表在這裡就得再從頭走一趟找前驅，O(1) 直接變 O(n)，整個 LRU 就垮了。

一個小技巧：用虛擬的 head 和 tail 節點，避免處理邊界條件。這樣不管鏈表是空的還是只有一個元素，removeNode 裡的 node.prev.next 都不會踩到 null，操作邏輯全部統一。

🎬 互動視覺化：鏈結串列指標操作動畫 — LRU 的靈魂就是雙向鏈表的接線，看指標怎麼在 moveToHead、removeTail 時重連，比讀 code 更快抓到手感。

LRU vs LFU

LRULFU
全名Least Recently UsedLeast Frequently Used
淘汰依據最久沒用使用次數最少
偏好最近用過的最常用的

LFU 的問題：某個元素早期被大量存取但後來不再使用，它的高頻率讓它霸占快取很久。LRU 比較「健忘」，但這種健忘反而在大部分場景更實用。

Redis 的預設淘汰策略也是 LRU 的近似版（allkeys-lru）。

Java 的偷吃步

LinkedHashMap<Integer, Integer> cache =
    new LinkedHashMap<>(capacity, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > capacity;
        }
    };

LinkedHashMap 的第三個參數設成 true 就是 access-order 模式——存取過的元素自動移到最後面。配合 removeEldestEntry 就是完整的 LRU。面試時先手寫，然後補充「Java 其實有 built-in」，加分。

LRU Cache 的人生哲學：不管你過去多重要，只要你最近不活躍，就會被淘汰。聽起來殘酷，但你的瀏覽器每天都在這麼做。

接下來往哪走

關係圖譜

反向連結