golang實(shí)現(xiàn)LRU緩存淘汰算法的示例代碼
LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫，是根據(jù)數(shù)據(jù)的歷史訪問(wèn)記錄來(lái)進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高”。
雙向鏈表實(shí)現(xiàn)LRU
將Cache的所有位置都用雙鏈表連接起來(lái)，當(dāng)一個(gè)位置被訪問(wèn)(get/put)之后，通過(guò)調(diào)整鏈表的指向，將該位置調(diào)整到鏈表頭的位置，新加入的Cache直接加到鏈表頭中。
這樣，在多次操作后，最近被訪問(wèn)(get/put)的，就會(huì)被向鏈表頭方向移動(dòng)，而沒(méi)有訪問(wèn)的，向鏈表后方移動(dòng)，鏈表尾則表示最近最少使用的Cache。
當(dāng)達(dá)到緩存容量上限時(shí)，鏈表的最后位置就是最少被訪問(wèn)的Cache，我們只需要?jiǎng)h除鏈表最后的Cache便可繼續(xù)添加新的Cache。
代碼實(shí)現(xiàn)
type Node struct {
Key int
Value int
pre *Node
next *Node
}
type LRUCache struct {
limit int
HashMap map[int]*Node
head *Node
end *Node
}
func Constructor(capacity int) LRUCache{
lruCache := LRUCache{limit:capacity}
lruCache.HashMap = make(map[int]*Node, capacity)
return lruCache
}
func (l *LRUCache) Get(key int) int {
if v,ok:= l.HashMap[key];ok {
l.refreshNode(v)
return v.Value
}else {
return -1
}
}
func (l *LRUCache) Put(key int, value int) {
if v,ok := l.HashMap[key];!ok{
if len(l.HashMap) >= l.limit{
oldKey := l.removeNode(l.head)
delete(l.HashMap, oldKey)
}
node := Node{Key:key, Value:value}
l.addNode(&node)
l.HashMap[key] = &node
}else {
v.Value = value
l.refreshNode(v)
}
}
func (l *LRUCache) refreshNode(node *Node){
if node == l.end {
return
}
l.removeNode(node)
l.addNode(node)
}
func (l *LRUCache) removeNode(node *Node) int{
if node == l.end {
l.end = l.end.pre
}else if node == l.head {
l.head = l.head.next
}else {
node.pre.next = node.next
node.next.pre = node.pre
}
return node.Key
}
func (l *LRUCache) addNode(node *Node){
if l.end != nil {
l.end.next = node
node.pre = l.end
node.next = nil
}
l.end = node
if l.head == nil {
l.head = node
}
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Golang回調(diào)函數(shù)與閉包和接口函數(shù)的定義及使用介紹
這篇文章主要介紹了Golang回調(diào)函數(shù)與閉包和接口函數(shù)的定義及使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2023-05-05
在?Golang?中使用?Cobra?創(chuàng)建?CLI?應(yīng)用
這篇文章主要介紹了在?Golang?中使用?Cobra?創(chuàng)建?CLI?應(yīng)用,來(lái)看下?Cobra?的使用，這里我們使用的?go1.13.3?版本，使用?Go?Modules?來(lái)進(jìn)行包管理,需要的朋友可以參考下2022-01-01
GoFrame?gredis緩存DoVar及Conn連接對(duì)象的自動(dòng)序列化
這篇文章主要為大家介紹了GoFrame?gredis干貨DoVar?Conn連接對(duì)象自動(dòng)序列化詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
Golang利用casbin實(shí)現(xiàn)權(quán)限驗(yàn)證詳解
Casbin是一個(gè)強(qiáng)大的、高效的開(kāi)源訪問(wèn)控制框架，其權(quán)限管理機(jī)制支持多種訪問(wèn)控制模型，Casbin只負(fù)責(zé)訪問(wèn)控制。本文將利用casbin實(shí)現(xiàn)權(quán)限驗(yàn)證功能，需要的可以參考一下2023-02-02
這篇文章主要介紹了golang goroutine順序輸出方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-04-04
golang連接MongoDB數(shù)據(jù)庫(kù)及數(shù)據(jù)庫(kù)操作指南
MongoDB是Nosql中常用的一種數(shù)據(jù)庫(kù),下面這篇文章主要給大家介紹了關(guān)于golang連接MongoDB數(shù)據(jù)庫(kù)及數(shù)據(jù)庫(kù)操作的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-09-09
Channel 和 goroutine 的結(jié)合是 Go 并發(fā)編程的大殺器。而 Channel 的實(shí)際應(yīng)用也經(jīng)常讓人眼前一亮，通過(guò)與 select，cancel，timer 等結(jié)合，它能實(shí)現(xiàn)各種各樣的功能。接下來(lái)，我們就要梳理一下 channel 的應(yīng)用2022-10-10
Go語(yǔ)言LeetCode題解706設(shè)計(jì)哈希映射
這篇文章主要為大家介紹了Go語(yǔ)言LeetCode題解706設(shè)計(jì)哈希映射示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
這篇文章主要為大家介紹了GoFrame?glist的基礎(chǔ)使用和自定義遍歷示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
GoLang RabbitMQ TTL與死信隊(duì)列以及延遲隊(duì)列詳細(xì)講解
這篇文章主要介紹了GoLang RabbitMQ TTL與死信隊(duì)列以及延遲隊(duì)列，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-12-12