什麼是LRU，如何用JavaScript實現LRU緩存機制
- 842字
- 4分鐘
- 2024-08-08
簡介
LRU 是 Least Recently Used 的縮寫，是一種緩存淘汰策略。當緩存達到其存儲上限時，LRU 會移除最久未使用的條目。該策略基於這樣一個假設：最近使用的數據很可能在將來還會被使用，而最久未使用的數據很可能不會再被使用。
LRU緩存的JavaScript實現
在 JavaScript 中實現一個 LRU 緩存，可以使用 Map 結合 雙向鏈表 來實現。Map 保證了元素的插入順序，雙向鏈表有助於高效地將最近使用的元素移到表頭和刪除最久未使用的元素。
代碼實現
以下是一個簡單的 LRU 緩存實現：
1// 定義雙向鏈表節點類2class Node {3 constructor(key, value) {4 this.key = key;5 this.value = value;6 this.prev = null;7 this.next = null;8 }9}10
11// 定義LRU緩存類12class LRUCache {13 constructor(capacity) {14 this.capacity = capacity; // 緩存容量15 this.map = new Map(); // 存儲緩存數據16 this.head = new Node(null, null); // 虛擬頭節點17 this.tail = new Node(null, null); // 虛擬尾節點18 this.head.next = this.tail;19 this.tail.prev = this.head;20 }21
22 // 獲取緩存值23 get(key) {24 if (!this.map.has(key)) {25 return -1; // 如果緩存中沒有該鍵，返回-126 }27
28 const node = this.map.get(key);29 this._remove(node); // 從雙向鏈表中移除節點30 this._add(node); // 將節點添加到鏈表尾部（表示最近使用）31
32 return node.value;33 }34
35 // 添加或更新緩存值36 put(key, value) {37 if (this.map.has(key)) {38 this._remove(this.map.get(key)); // 如果緩存中已存在該鍵，先刪除舊節點39 }40
41 const newNode = new Node(key, value);42 this._add(newNode); // 將新節點添加到鏈表尾部43 this.map.set(key, newNode);44
45 if (this.map.size > this.capacity) {46 const lruNode = this.head.next; // 獲取最久未使用的節點47 this._remove(lruNode); // 從鏈表中移除最久未使用的節點48 this.map.delete(lruNode.key); // 從緩存中刪除最久未使用的鍵49 }50 }51
52 // 從雙向鏈表中移除節點53 _remove(node) {54 node.prev.next = node.next;55 node.next.prev = node.prev;56 }57
58 // 將節點添加到雙向鏈表尾部59 _add(node) {60 node.prev = this.tail.prev;61 node.next = this.tail;62 this.tail.prev.next = node;63 this.tail.prev = node;64 }65}示例使用
1const lru = new LRUCache(2);2
3lru.put(1, 1);4lru.put(2, 2);5console.log(lru.get(1)); // 輸出 16lru.put(3, 3); // 淘汰鍵 27console.log(lru.get(2)); // 輸出 -1 (未找到)8lru.put(4, 4); // 淘汰鍵 19console.log(lru.get(1)); // 輸出 -1 (未找到)10console.log(lru.get(3)); // 輸出 311console.log(lru.get(4)); // 輸出 4代碼解釋
- Node 類：用於雙向鏈表節點，包含
key和value以及prev和next指針。 - LRUCache 類：管理緩存的主要類，初始化時設置容量
capacity並創建一個Map和兩個哨兵節點head和tail。 - get 方法：從緩存中獲取值，如果存在則將節點移動到尾部（表示最近使用）。
- put 方法：將新值插入緩存，若緩存已存在該鍵值對，則先刪除舊節點。插入新節點後，檢查是否超過容量，若超過則移除最前面的節點（表示最久未使用）。
- _remove 方法：從雙向鏈表中刪除節點。
- _add 方法：將節點添加到雙向鏈表尾部。
這個實現確保了 get 和 put 操作都能在常數時間複雜度 ( O(1) ) 內完成。
總結
通過以上代碼和詳細註釋，我們了解了如何使用 JavaScript 實現一個簡單的 LRU 緩存。LRU 緩存是一種常用的緩存淘汰策略，廣泛應用於各種緩存系統中。希望這篇文章能幫助你更好地理解 LRU 緩存的實現原理和應用。
