LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫(xiě)，是根據(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í)有所幫助，也希望大家多多支持腳本之家。
標(biāo)簽：東營(yíng) 吐魯番 貴州 保定 德宏 許昌 曲靖 常州
巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《golang實(shí)現(xiàn)LRU緩存淘汰算法的示例代碼》，本文關(guān)鍵詞 golang,實(shí)現(xiàn),LRU,緩存,淘汰,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。
