在高性能服務開發中，緩存是提升訪問速度和減少后端負載的重要手段。常見的緩存淘汰策略中，**LRU（Least Recently Used，最近最少使用）**是應用最廣的一種。本篇我們用Go語言手寫一個LRU緩存機制的模擬實現。

---

一、LRU緩存機制簡介

1. 定義

LRU緩存是一種固定容量的緩存結構。當緩存已滿時，它會淘汰最近最少使用的那個數據。簡單理解：

誰最久沒被訪問，就先刪除誰。

2. 使用場景

• ? Web瀏覽器緩存
• ? 數據庫查詢結果緩存
• ? 操作系統頁面置換

---

二、設計要求

LRU緩存應支持以下操作：

1. 1.?Get(key)：如果key存在，返回對應的value，并將該key標記為最近使用；否則返回-1。
2. 2.?Put(key, value)：插入或更新key。如果容量已滿，需要刪除最近最少使用的key。

要求兩種操作都能在?O(1)?時間復雜度內完成。

---

三、核心數據結構

要實現 O(1) 操作，需要組合以下兩種結構：

1. 哈希表（map）

• ? 用于存儲?key → 節點?的映射；
• ? 可在 O(1) 時間內找到節點。

2. 雙向鏈表

• ? 用于維護數據訪問的順序；
• ? 頭部表示最近使用，尾部表示最久未使用；
• ? 插入、刪除節點都是 O(1)。

---

四、Go語言實現

1. 節點結構

type?Node?struct?{key,?value?intprev,?next?*Node
}

2. LRU緩存結構

type?LRUCache?struct?{capacity?intcache????map[int]*Nodehead?????*Nodetail?????*Node
}

• ??head?和?tail?是哨兵節點（dummy），方便操作。

---

3. 初始化

func?Constructor(capacity?int)?LRUCache?{head?:=?&Node{}tail?:=?&Node{}head.next?=?tailtail.prev?=?headreturn?LRUCache{capacity:?capacity,cache:????make(map[int]*Node),head:?????head,tail:?????tail,}
}

---

4. 輔助方法

//?moveToHead：將節點移動到頭部
func?(l?*LRUCache)?moveToHead(node?*Node)?{l.removeNode(node)l.addToHead(node)
}//?removeNode：刪除鏈表中的節點
func?(l?*LRUCache)?removeNode(node?*Node)?{prev?:=?node.prevnext?:=?node.nextprev.next?=?nextnext.prev?=?prev
}//?addToHead：在頭部插入節點
func?(l?*LRUCache)?addToHead(node?*Node)?{node.prev?=?l.headnode.next?=?l.head.nextl.head.next.prev?=?nodel.head.next?=?node
}//?removeTail：刪除尾部節點并返回它
func?(l?*LRUCache)?removeTail()?*Node?{node?:=?l.tail.prevl.removeNode(node)return?node
}

---

5. 核心操作

Get

func?(l?*LRUCache)?Get(key?int)?int?{if?node,?ok?:=?l.cache[key];?ok?{l.moveToHead(node)return?node.value}return?-1
}

Put

func?(l?*LRUCache)?Put(key?int,?value?int)?{if?node,?ok?:=?l.cache[key];?ok?{node.value?=?valuel.moveToHead(node)}?else?{newNode?:=?&Node{key:?key,?value:?value}l.cache[key]?=?newNodel.addToHead(newNode)if?len(l.cache)?>?l.capacity?{tail?:=?l.removeTail()delete(l.cache,?tail.key)}}
}

---

五、完整代碼示例

package?mainimport?"fmt"type?Node?struct?{key,?value?intprev,?next?*Node
}type?LRUCache?struct?{capacity?intcache????map[int]*Nodehead?????*Nodetail?????*Node
}func?Constructor(capacity?int)?LRUCache?{head?:=?&Node{}tail?:=?&Node{}head.next?=?tailtail.prev?=?headreturn?LRUCache{capacity:?capacity,cache:????make(map[int]*Node),head:?????head,tail:?????tail,}
}func?(l?*LRUCache)?Get(key?int)?int?{if?node,?ok?:=?l.cache[key];?ok?{l.moveToHead(node)return?node.value}return?-1
}func?(l?*LRUCache)?Put(key?int,?value?int)?{if?node,?ok?:=?l.cache[key];?ok?{node.value?=?valuel.moveToHead(node)}?else?{newNode?:=?&Node{key:?key,?value:?value}l.cache[key]?=?newNodel.addToHead(newNode)if?len(l.cache)?>?l.capacity?{tail?:=?l.removeTail()delete(l.cache,?tail.key)}}
}func?(l?*LRUCache)?moveToHead(node?*Node)?{l.removeNode(node)l.addToHead(node)
}func?(l?*LRUCache)?removeNode(node?*Node)?{prev?:=?node.prevnext?:=?node.nextprev.next?=?nextnext.prev?=?prev
}func?(l?*LRUCache)?addToHead(node?*Node)?{node.prev?=?l.headnode.next?=?l.head.nextl.head.next.prev?=?nodel.head.next?=?node
}func?(l?*LRUCache)?removeTail()?*Node?{node?:=?l.tail.prevl.removeNode(node)return?node
}func?main()?{cache?:=?Constructor(2)cache.Put(1,?1)cache.Put(2,?2)fmt.Println(cache.Get(1))?//?1cache.Put(3,?3)???????????//?淘汰?key=2fmt.Println(cache.Get(2))?//?-1cache.Put(4,?4)???????????//?淘汰?key=1fmt.Println(cache.Get(1))?//?-1fmt.Println(cache.Get(3))?//?3fmt.Println(cache.Get(4))?//?4
}

---

六、復雜度分析

• ??時間復雜度：O(1)，Get 和 Put 都只涉及哈希表查找和鏈表操作。
• ??空間復雜度：O(capacity)，存儲固定大小的map和鏈表節點。

---

七、工程實踐與優化

1. 1.?線程安全
   在多協程環境中，需使用?sync.Mutex?或?sync.RWMutex?保證安全。
2. 2.?泛型支持（Go1.18+）
   可以用泛型實現支持任意類型的key/value。
3. 3.?監控統計
   可增加命中率統計、淘汰計數。

---

八、應用場景

• ??數據庫緩存：Redis內部就支持LRU策略；
• ??瀏覽器緩存：網頁資源加載優化；
• ??API限速器：存儲用戶最近訪問記錄。

---

九、總結

• ? LRU緩存結合了?哈希表?+?雙向鏈表；
• ? 關鍵是?O(1) 時間內完成訪問和淘汰；
• ? 該思想可擴展到 LFU、ARC 等高級緩存策略。