Go語言中LRU緩存機制的實現(xiàn)
更新時間：2025年08月14日 10:53:00 作者：程序員愛釣魚
本文詳解如何用Go語言實現(xiàn)LRU緩存,通過哈希表+雙向鏈表組合確保Get和Put操作均為O(1),具有一定的參考價值,感興趣的可以了解一下
在高性能服務開發(fā)中，緩存是提升訪問速度和減少后端負載的重要手段。常見的緩存淘汰策略中，**LRU（Least Recently Used，最近最少使用）**是應用最廣的一種。本篇我們用Go語言手寫一個LRU緩存機制的模擬實現(xiàn)。
一、LRU緩存機制簡介
1. 定義
LRU緩存是一種固定容量的緩存結構。當緩存已滿時，它會淘汰最近最少使用的那個數(shù)據(jù)。簡單理解：
誰最久沒被訪問，就先刪除誰。
2. 使用場景
- Web瀏覽器緩存
- 數(shù)據(jù)庫查詢結果緩存
- 操作系統(tǒng)頁面置換
二、設計要求
LRU緩存應支持以下操作：
Get(key)：如果key存在，返回對應的value，并將該key標記為最近使用；否則返回-1。Put(key, value)：插入或更新key。如果容量已滿，需要刪除最近最少使用的key。
要求兩種操作都能在 O(1) 時間復雜度內(nèi)完成。
三、核心數(shù)據(jù)結構
要實現(xiàn) O(1) 操作，需要組合以下兩種結構：
1. 哈希表（map）
- 用于存儲
key → 節(jié)點的映射； - 可在 O(1) 時間內(nèi)找到節(jié)點。
2. 雙向鏈表
- 用于維護數(shù)據(jù)訪問的順序；
- 頭部表示最近使用，尾部表示最久未使用；
- 插入、刪除節(jié)點都是 O(1)。
四、Go語言實現(xiàn)
1. 節(jié)點結構
type Node struct {
key, value int
prev, next *Node
}
2. LRU緩存結構
type LRUCache struct {
capacity int
cache map[int]*Node
head *Node
tail *Node
}
head和tail是哨兵節(jié)點（dummy），方便操作。
3. 初始化
func Constructor(capacity int) LRUCache {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make(map[int]*Node),
head: head,
tail: tail,
}
}
4. 輔助方法
// moveToHead：將節(jié)點移動到頭部
func (l *LRUCache) moveToHead(node *Node) {
l.removeNode(node)
l.addToHead(node)
}
// removeNode：刪除鏈表中的節(jié)點
func (l *LRUCache) removeNode(node *Node) {
prev := node.prev
next := node.next
prev.next = next
next.prev = prev
}
// addToHead：在頭部插入節(jié)點
func (l *LRUCache) addToHead(node *Node) {
node.prev = l.head
node.next = l.head.next
l.head.next.prev = node
l.head.next = node
}
// removeTail：刪除尾部節(jié)點并返回它
func (l *LRUCache) removeTail() *Node {
node := l.tail.prev
l.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 = value
l.moveToHead(node)
} else {
newNode := &Node{key: key, value: value}
l.cache[key] = newNode
l.addToHead(newNode)
if len(l.cache) > l.capacity {
tail := l.removeTail()
delete(l.cache, tail.key)
}
}
}
五、完整代碼示例
package main
import "fmt"
type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
capacity int
cache map[int]*Node
head *Node
tail *Node
}
func Constructor(capacity int) LRUCache {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return 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 = value
l.moveToHead(node)
} else {
newNode := &Node{key: key, value: value}
l.cache[key] = newNode
l.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.prev
next := node.next
prev.next = next
next.prev = prev
}
func (l *LRUCache) addToHead(node *Node) {
node.prev = l.head
node.next = l.head.next
l.head.next.prev = node
l.head.next = node
}
func (l *LRUCache) removeTail() *Node {
node := l.tail.prev
l.removeNode(node)
return node
}
func main() {
cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)
fmt.Println(cache.Get(1)) // 1
cache.Put(3, 3) // 淘汰 key=2
fmt.Println(cache.Get(2)) // -1
cache.Put(4, 4) // 淘汰 key=1
fmt.Println(cache.Get(1)) // -1
fmt.Println(cache.Get(3)) // 3
fmt.Println(cache.Get(4)) // 4
}
六、復雜度分析
- 時間復雜度：O(1)，Get 和 Put 都只涉及哈希表查找和鏈表操作。
- 空間復雜度：O(capacity)，存儲固定大小的map和鏈表節(jié)點。
七、工程實踐與優(yōu)化
- 1. 線程安全
在多協(xié)程環(huán)境中，需使用sync.Mutex或sync.RWMutex保證安全。 - 2. 泛型支持（Go1.18+）
可以用泛型實現(xiàn)支持任意類型的key/value。 - 3. 監(jiān)控統(tǒng)計
可增加命中率統(tǒng)計、淘汰計數(shù)。
八、應用場景
- 數(shù)據(jù)庫緩存：Redis內(nèi)部就支持LRU策略；
- 瀏覽器緩存：網(wǎng)頁資源加載優(yōu)化；
- API限速器：存儲用戶最近訪問記錄。
九、總結
- LRU緩存結合了 哈希表 + 雙向鏈表；
- 關鍵是 O(1) 時間內(nèi)完成訪問和淘汰；
- 該思想可擴展到 LFU、ARC 等高級緩存策略。
到此這篇關于Go語言中LRU緩存機制的實現(xiàn)的文章就介紹到這了,更多相關Go語言 LRU緩存內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
詳解golang執(zhí)行Linux shell命令完整場景下的使用方法
本文主要介紹了golang執(zhí)行Linux shell命令完整場景下的使用方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-06-06
這篇文章主要為大家詳細介紹了Go語言中的監(jiān)視器模式與配置熱更新的相關知識,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-03-03
這篇文章主要為大家詳細介紹了Go語言并發(fā)中Sync包的6個關鍵概念，文中的示例代碼講解詳細，對我們深入學習Go語言有一定的幫助，需要的可以參考一下2023-05-05
這篇文章主要為大家詳細介紹了Go語言中數(shù)組一些細節(jié)的相關資料，文中的示例代碼講解詳細，對我們學習Go語言有一定的幫助，需要的可以了解一下2022-11-11
這篇文章主要為大家介紹了多階段構建優(yōu)化Go?程序Docker鏡像，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
mac下golang安裝了windows編譯環(huán)境后編譯變慢
這篇文章主要介紹了mac下golang安裝了windows編譯環(huán)境后編譯變慢的處理方法，非常的簡單，有相同問題的小伙伴可以參考下。2015-04-04
隨著科技的進步，人人都想要快速的應用，這就需要優(yōu)化您的應用程序性能。本文為大家整理了一些Golang應用程序性能優(yōu)化的技巧，希望對大家有所幫助2023-04-04
這篇文章主要介紹了grpool?goroutine池協(xié)程管理，goroutine協(xié)程非常輕量級，這也是為什么go支持高并發(fā)，但是goroutine頻繁創(chuàng)建銷毀對GC的壓力比較大，文章圍繞主題展開詳細的內(nèi)容介紹，需要的小伙伴可以參考一下2022-06-06
這篇文章主要介紹了golang等待觸發(fā)事件的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
Go語言中的結構體切片是一種結合了結構體和切片特點的數(shù)據(jù)結構,用于存儲和操作多個結構體實例,具有一定的參考價值,感興趣的可以了解一下2024-11-11