[algorithms] LRU Cache 最近最少使用快取

視覺化概覽

graph LR
    subgraph HashMap
        K1["key:1"] -.-> N1
        K2["key:2"] -.-> N2
        K3["key:3"] -.-> N3
    end

    subgraph 雙向鏈表["雙向鏈表（使用順序）"]
        H["Head"] <--> N3["Node 3\n(最近)"]
        N3 <--> N1["Node 1"]
        N1 <--> N2["Node 2\n(最久)"]
        N2 <--> T["Tail"]
    end

    GET["get(2)"] --> |"1.HashMap O(1) 查找"| K2
    K2 --> |"2.移到 Head 端"| H

    style H fill:#e0e0e0,stroke:#757575
    style T fill:#e0e0e0,stroke:#757575
    style N2 fill:#ffcdd2,stroke:#f44336
    style N3 fill:#c8e6c9,stroke:#4caf50

什麼是 LRU Cache？

容量有限的快取，滿了就淘汰最久沒用的。

容量: 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 + 雙向鏈表 = O(1) 操作

HashMap: key → Node（O(1) 查找）

雙向鏈表：維護使用順序
head ↔ [最近] ↔ [次近] ↔ ... ↔ [最久] ↔ tail

為什麼需要雙向鏈表？

• 單向鏈表：刪除節點需要 O(n) 找前驅
• 雙向鏈表：直接通過 prev 指針刪除，O(1)

核心操作

1. Get - O(1)

int get(int key) {
    if (!map.containsKey(key)) return -1;
    Node node = map.get(key);
    moveToHead(node);  // 移到最前面
    return node.value;
}

2. Put - O(1)

void put(int key, int value) {
    if (map.containsKey(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);
        }
    }
}

3. 鏈表操作

void addToHead(Node node) {
    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() {
    Node node = tail.prev;
    removeNode(node);
    return node;
}

虛擬頭尾節點

避免邊界判斷，簡化程式碼：

初始化:
head ↔ tail

添加節點 A:
head ↔ A ↔ tail

添加節點 B:
head ↔ B ↔ A ↔ tail

LRU vs LFU

策略	全名	淘汰依據
LRU	Least Recently Used	最久未使用
LFU	Least Frequently Used	使用頻率最低

LFU 範例

put(1), put(2), get(1), put(3)

key=1: 頻率 2（get 過一次）
key=2: 頻率 1
key=3: 頻率 1

淘汰 key=2（頻率最低，且比 key=3 更早）

實際應用

1. 作業系統頁面置換
2. 資料庫快取
3. CDN 快取
4. 瀏覽器快取
5. Redis 記憶體淘汰

Java 內建實現

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

時間複雜度

操作	時間複雜度
get	O(1)
put	O(1)
淘汰	O(1)

空間複雜度

O(capacity)

經典題目

1. LRU 快取 - LeetCode 146
2. LFU 快取 - LeetCode 460

相關檔案

• Java 實作：LRUCache.java