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