LRU Cache (Least Recently Used)#

LRU 是一種快取淘汰策略：當快取滿時，優先淘汰「最久沒有被使用」的資料。

核心思想#

剛用過的，大概率馬上還會用；很久沒用的，大概率不需要了。

運作原理#

使用雙向鏈結串列維護使用順序：

Head：最近剛使用
Tail：最久未使用

操作流程#

flowchart TD
    subgraph GET["Get 操作"]
        G1{Key 存在?} -->|否| G2[返回 -1]
        G1 -->|是| G3[移動到 Head]
        G3 --> G4[返回 Value]
    end

    subgraph PUT["Put 操作"]
        P1{Key 已存在?} -->|是| P2[更新 Value<br/>移動到 Head]
        P1 -->|否| P3{容量已滿?}
        P3 -->|否| P4[插入 Head]
        P3 -->|是| P5[淘汰 Tail]
        P5 --> P4
    end

    style G3 fill:#e8f5e9
    style G4 fill:#e8f5e9
    style P4 fill:#e3f2fd
    style P5 fill:#ffebee

操作	行為
Get	取出資料，並移動到 Head
Put (未滿)	插入 Head
Put (已滿)	淘汰 Tail，新資料插入 Head

運作範例

假設容量為 5，依序操作：

插入 A, B, C, D, E → [E, D, C, B, A]
插入 F（容量滿）→ 淘汰 A → [F, E, D, C, B]
訪問 C → C 移到 Head → [C, F, E, D, B]

資料結構#

實作 O(1) 的 Get/Put 需要：

Hash Map：O(1) 查找 key 對應的節點
雙向鏈結串列：O(1) 插入、刪除、移動節點

程式碼實作#

Python 實作 (使用 OrderedDict)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 移動到末尾（最近使用）
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 移除最舊的元素（第一個）
            self.cache.popitem(last=False)

Java 手寫實作

class LRUCache {
    class Node {
        int key, value;
        Node prev, next;
    }

    private Map<Integer, Node> map = new HashMap<>();
    private Node head, tail;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node node = new Node();
            node.key = key;
            node.value = value;
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node removed = removeTail();
                map.remove(removed.key);
            }
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
}

LRU vs LFU#

特性	LRU	LFU
全稱	Least Recently Used	Least Frequently Used
依據	時間（最近使用）	頻率（使用次數）
適用	時間局部性強	長期熱度穩定
實作	相對簡單	需維護頻率計數

LRU 可能因一次性批量掃描導致熱點資料被誤淘汰。若存取模式具有長期頻率穩定性，LFU 更適合。

應用場景#

CPU 多級快取 (L1/L2/L3)
資料庫查詢快取
作業系統頁面置換
CDN 內容快取