golang實現(xiàn)LRU緩存淘汰算法的示例代碼
更新時間：2018年12月27日 14:22:57 作者：caelansar
這篇文章主要介紹了golang實現(xiàn)LRU緩存淘汰算法的示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫，是根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。
雙向鏈表實現(xiàn)LRU
將Cache的所有位置都用雙鏈表連接起來，當(dāng)一個位置被訪問(get/put)之后，通過調(diào)整鏈表的指向，將該位置調(diào)整到鏈表頭的位置，新加入的Cache直接加到鏈表頭中。
這樣，在多次操作后，最近被訪問(get/put)的，就會被向鏈表頭方向移動，而沒有訪問的，向鏈表后方移動，鏈表尾則表示最近最少使用的Cache。
當(dāng)達(dá)到緩存容量上限時，鏈表的最后位置就是最少被訪問的Cache，我們只需要刪除鏈表最后的Cache便可繼續(xù)添加新的Cache。
代碼實現(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
}
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Go語言metrics應(yīng)用監(jiān)控指標(biāo)基本使用說明
這篇文章主要為大家介紹了Go語言metrics應(yīng)用監(jiān)控指標(biāo)的基本使用說明，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-02-02
一文理解Goland協(xié)程調(diào)度器scheduler的實現(xiàn)
本文主要介紹了Goland協(xié)程調(diào)度器scheduler的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
Go語言追求簡潔優(yōu)雅，所以，Go語言不支持傳統(tǒng)的 try…catch…finally 這種異常，因為Go語言的設(shè)計者們認(rèn)為，將異常與控制結(jié)構(gòu)混在一起會很容易使得代碼變得混亂，今天給大家介紹golang panic及處理機(jī)制，需要的朋友參考下吧2021-08-08
詳解Go語言中for循環(huán),break和continue的使用
這篇文章主要通過一些示例為大家介紹一下Go語言中for循環(huán)、break和continue的基本語法以及使用，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-06-06
這篇文章主要為大家詳細(xì)介紹了Go語言中接口應(yīng)用模式或慣例介紹的相關(guān)知識,文中的示例代碼講解詳細(xì),有需要的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-11-11
Go 語言為我們提供了豐富的并發(fā)原語，且大多數(shù)都位于 sync 包下,今天我們來探討一下該庫下的原語之一：errgroup，感興趣的小伙伴可以了解一下2023-05-05
這篇文章主要介紹了go語言ssh客戶端解決密碼過期問題,本文給大家分享了解決的方法和原理，非常不錯，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-04-04
這篇文章主要給大家介紹了關(guān)于Golang JSON進(jìn)階用法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用golang具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-09-09
這篇文章主要為大家詳細(xì)介紹了Golang實現(xiàn)斷點續(xù)傳、復(fù)制文件功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
Golang遠(yuǎn)程調(diào)用框架RPC的具體使用
Remote Procedure Call (RPC) 是一種使用TCP協(xié)議從另一個系統(tǒng)調(diào)用應(yīng)用程序功能執(zhí)行的方法。Go有原生支持RPC服務(wù)器實現(xiàn),本文通過簡單實例介紹RPC的實現(xiàn)過程2022-12-12