跳到主要內容
Jasonmel Online

資料結構

資料怎麼排，決定了哪些操作便宜

主題 · LRU 快取

LRU 快取

LRU 是 Least Recently Used（最近最少使用），滿了就淘汰最久沒用的那一筆。雜湊表負責一步找到資料，雙向串列負責記住誰最久沒用；兩個結構合起來，讀取與淘汰都只要一步。

存取
容量
雜湊表：鍵 → 節點位址
A→ #16
B→ #32
C→ #48
D→ #64
雙向串列：最近用過 → 最久沒用
  1. HEAD
  2. D#64
  3. A#16
  4. C#48
  5. B#32
  6. TAIL
存取紀錄
  1. A
  2. B
  3. C
  4. A
  5. D
命中／剛存取沒命中被淘汰

沒命中：還有空位，把 D 放到串列最前面，並記進雜湊表。

存取次數
5
命中
1
命中率
20%
亮起來的是這一步執行的程式碼
class ListNode {
  prev: ListNode | null = null;
  next: ListNode | null = null;
  constructor(public key: string, public value: number) {}
}
 
class LRUCache {
  private map = new Map<string, ListNode>();
  private head = new ListNode("", 0); // sentinel: most recent side
  private tail = new ListNode("", 0); // sentinel: least recent side
 
  constructor(private capacity: number) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  get(key: string): number | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.unlink(node);
    this.pushFront(node);
    return node.value;
  }
 
  put(key: string, value: number): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.unlink(existing);
      this.pushFront(existing);
      return;
    }
    if (this.map.size === this.capacity) {
      const oldest = this.tail.prev!;
      this.unlink(oldest);
      this.map.delete(oldest.key);
    }
    const node = new ListNode(key, value);
    this.map.set(key, node);
    this.pushFront(node);
  }
 
  private unlink(node: ListNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
 
  private pushFront(node: ListNode): void {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

  • 記憶體只放得下一部分資料，而且最近用過的東西很可能馬上又會用到。
  • 讀取和淘汰都必須是常數時間：每秒幾十萬次存取的快取，不能每次都掃一遍。

和其他主題的關係

語言內建的版本

Map<K, V>
操作寫法成本
標成最近用過：先刪掉lru.delete(key)O(1)
……再放回最後lru.set(key, value)O(1)
找最久沒用的lru.keys().next().valueO(1)
超過容量就淘汰if (lru.size > capacity)O(1)
const capacity = 2;
const lru = new Map<string, number>();
 
function get(key: string): number | undefined {
  const value = lru.get(key);
  if (value === undefined) return undefined;
  lru.delete(key);
  lru.set(key, value);
  return value;
}
 
function put(key: string, value: number): void {
  lru.delete(key);
  lru.set(key, value);
  if (lru.size > capacity) lru.delete(lru.keys().next().value!);
}
 
put("a", 1);
put("b", 2);
get("a");                    // → 1
put("c", 3);
[...lru.keys()];             // → ["a", "c"]
get("b");                    // → undefined
 
// set() on an existing key keeps its old position.
const m = new Map([["x", 1], ["y", 2]]);
m.set("x", 9);
[...m.keys()];               // → ["x", "y"]

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

  • Map 照插入順序走訪，所以「刪掉再放回去」就等於移到最後，keys().next() 拿到的就是最久沒用的。這就是一個 LRU（Least Recently Used，最近最少使用）快取，每個操作都是 O(1)。
  • 對已經存在的鍵 set 不會改變它的位置，一定要先 delete。
  • 如果值可能是 undefined，就不能靠 get 的回傳值判斷有沒有，要先用 has。

時間與空間複雜度（Big O）

操作平均最差
讀取（get）
雜湊表查找是平均 O(1)
O(1)O(1)
寫入（put），含淘汰O(1)O(1)
改用陣列依新舊排序O(n)O(n)

空間：O(n)，n 是容量；每個項目一個串列節點加一筆雜湊表記錄

Big O 實測：n 變大時步數怎麼長

數的是：每次存取平均的指標寫入或比較＋搬動（n 是容量，快取先填滿）

Big On = 100n = 1,000n = 10,000成長倍數：實測（理論）
雜湊表＋雙向串列O(1)8.08.08×1.0 (×1.0)
陣列依新舊排序O(n)1451,41813,470×93 (×100)

和其他做法比

雜湊表＋雙向串列陣列依新舊排序命中率
容量 101 次查表＋改幾個指標平均 14 次比較或搬動54%
容量 1001 次查表＋改幾個指標平均 145 次比較或搬動54%
容量 1,0001 次查表＋改幾個指標平均 1,415 次比較或搬動52%

兩種做法跑同一串存取（鍵的種類是容量的兩倍，前一半被存取的機率是後一半的兩倍），最後剩下的鍵和順序完全一樣：差別只在每次存取要做多少事。陣列的版本隨容量線性變慢，雜湊表＋串列的版本不會。

真實世界裡的它

  • Redis 的 allkeys-lru、作業系統的頁面置換、資料庫的 buffer pool（多半是省記憶體的近似版）。
  • 瀏覽器快取、CDN（Content Delivery Network，內容傳遞網路）邊緣節點、各種程式語言的 memoize 工具（例如 Python 的 functools.lru_cache）。

取捨與陷阱

  • 一次大量掃描（例如備份或報表把所有資料讀過一遍）會把熱門資料全部擠出去，所以才有 LRU-K（看倒數第 K 次存取）、2Q（Two Queues）、ARC（Adaptive Replacement Cache）等變形。
  • 每次讀取都要改串列：多執行緒時那把鎖會變成瓶頸，實務上常分片或用近似 LRU。
  • 只看「最近」不看「頻率」：只用一次的資料也會擠掉常用的資料。

LeetCode 練習