LRU Cache (Least Recently Used)#

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

核心思想#

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

為什麼 LRU 是個好策略？（快取背後的直覺）#

LRU 看起來只是一條淘汰規則，但它之所以管用，背後牽動的是整個計算的基本架構與一條優雅的理論。

記憶體階層：大而慢 + 小而快#

世上沒有一種儲存能同時又大又快——大容量的便宜但慢，快的又貴又小。於是電腦不靠單一儲存，而是把它們疊成一座階層：

層級速度容量
暫存器最快最小
快取快小
記憶體中中
磁碟慢大

每往下一層，更大但更慢。系統的任務，就是把最可能馬上用到的資料，留在最快的那一層。從這個角度看，快取不是某個系統的優化細節，而是計算本身的基本架構——只要存在「大而慢」與「小而快」的落差，就需要一套策略決定誰留在快的那層。

理論最佳 vs LRU#

那「誰該留下」的最佳答案是什麼？理論上可以證明，最完美的淘汰策略是：踢掉未來最久才會再被用到的那一個（Belady 最優策略）。

問題是，它需要預知未來——你得先知道每個資料下次什麼時候被存取。現實中沒有這種水晶球，所以這個最優解只能當作衡量基準，無法真正實作。

LRU 正是對它的最佳近似：既然看不到未來，就回頭看過去。LRU 的核心假設是「歷史會反向重演」——剛被用過的東西，短期內最可能再被用到。這條規律有個名字，叫時間局部性（temporal locality）。

LRU 不是工程師隨手挑的啟發法，而是「在無法預知未來時，最合理的猜測」。它用「最近用過」去逼近那個不可知的「未來會用到」，把一個需要先知的問題，換成一個只需回顧歷史的問題。

LRU 有理論保證#

更難得的是，這個近似不是憑感覺好用而已，它有硬性的數學保證：可以證明，採用 LRU 的總存取成本，不會超過「預知未來的最優策略」的兩倍。

換句話說，即使對手能預知未來，LRU 也最多只差它一倍。這就是 LRU 「簡單、便宜，卻可靠」的底氣——你付出極小的代價（一個雙向鏈結串列加 Hash Map），就換到一個與理論最優只差常數倍的保證。

延伸：距離就是快取#

把同一條局部性原理從晶片尺度放大到網路尺度，就是 CDN（內容傳遞網路）：把資料的副本，預先放到離使用者最近的節點上。

「離得近 = 快」，和「最近用過 = 留在快取」其實是同一件事的不同尺度——前者是空間上的就近、後者是時間上的就近。快取的思想一旦看懂，你會發現它無所不在：從 CPU 的 L1 快取，到瀏覽器，到全球的 CDN 節點，都是同一條直覺在不同尺度上的展開。

運作原理#

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

  • 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，依序操作：

  1. 插入 A, B, C, D, E ➡️ [E, D, C, B, A]
  2. 插入 F（容量滿）➡️ 淘汰 A ➡️ [F, E, D, C, B]
  3. 訪問 C ➡️ C 移到 Head ➡️ [C, F, E, D, B]

資料結構#

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

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

程式碼實作（LRU Cache ↗）#

Kotlin 標準庫的 LinkedHashMap 內建 access-order 模式，設 accessOrder = true 後，只要覆寫 removeEldestEntry 就能得到一個現成的 LRU：

LinkedHashMap 實作
class LRUCache(private val capacity: Int) {
    // accessOrder = true：被存取過的項目會移到尾端，最舊的留在頭端
    private val cache = object : LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
        override fun removeEldestEntry(eldest: Map.Entry<Int, Int>): Boolean =
            size > capacity   // 超出容量時，自動淘汰最久未使用者
    }

    fun get(key: Int): Int = cache.getOrDefault(key, -1)

    fun put(key: Int, value: Int) {
        cache[key] = value
    }
}
手寫實作：雙向鏈結串列 + HashMap
class LRUCache(private val capacity: Int) {
    private class Node(val key: Int = 0, var value: Int = 0) {
        var prev: Node? = null
        var next: Node? = null
    }

    private val map = HashMap<Int, Node>()
    // 虛擬頭尾節點，簡化邊界處理
    private val head = Node()
    private val tail = Node()

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: Int): Int {
        val node = map[key] ?: return -1
        moveToHead(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        val existing = map[key]
        if (existing != null) {
            existing.value = value
            moveToHead(existing)
        } else {
            val node = Node(key, value)
            map[key] = node
            addToHead(node)
            if (map.size > capacity) {
                val removed = removeTail()
                map.remove(removed.key)
            }
        }
    }

    private fun moveToHead(node: Node) {
        removeNode(node)
        addToHead(node)
    }

    private fun addToHead(node: Node) {
        node.next = head.next
        node.prev = head
        head.next!!.prev = node
        head.next = node
    }

    private fun removeNode(node: Node) {
        node.prev!!.next = node.next
        node.next!!.prev = node.prev
    }

    private fun removeTail(): Node {
        val node = tail.prev!!
        removeNode(node)
        return node
    }
}

LRU vs LFU#

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

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

應用場景#

  • CPU 多級快取 (L1/L2/L3)
  • 資料庫查詢快取
  • 作業系統頁面置換
  • CDN 內容快取
Backward 布隆過濾器 位圖 Forward