前言
最近復習作業系統，看到了lru演算法，就去網上搜索下，因此發現了GeeCache，順手寫了一遍，研究下lru演算法的實作，
正文:
lru使用map+鏈表實作，map里面存盤了key以及其對應的鏈表節點，當我們根據某個key訪問快取值的時候，可以經過map快速定位到該鏈表節點，從而獲取值
下面我們來看下它的具體實作:
首先，我們可以考慮下lru的結構：
1.map
2.鏈表
3.占用的記憶體大小
4.最大記憶體
type Cache struct {
maxBytes int64
nbytes int64
ll *list.List
cache map[string]*list.Element
}
添加key:
lru演算法的思想是經常訪問的元素移動到隊頭,不常訪問的元素移動到隊尾，從而進行淘汰隊尾元素，
當我們添加的key已經存在的時候，我們只需要更新其對應的值即可，
不存在的時候，需要插入鏈表和map
如果記憶體已經不夠，我們需要開啟淘汰演算法
func (c *Cache) Add(key string,value Value) {
if v,ok := c.cache[key]; ok{
// 移動到常用元素 --> 隊頭
c.ll.MoveToFront(v)
// 獲取舊值
kv := v.Value.(*entry)
c.nbytes += int64(value.Len()) - int64(kv.value.Len())
// 更新值
kv.value = https://www.cnblogs.com/freeyw/archive/2022/08/05/value
}else{
ele := c.ll.PushFront(&entry{key,value})
c.cache[key] = ele
c.nbytes += int64(len(key)) + int64(value.Len())
}
if c.maxBytes != 0 || c.maxBytes < c.nbytes{
// 淘汰演算法
c.RemoveOldest()
}
}
下面我們來看淘汰演算法:
在鏈表中移除隊尾的元素，洗掉map中相應的key
func (c *Cache) RemoveOldest() { ele := c.ll.Back() if ele != nil { c.ll.Remove(ele) kv := ele.Value.(*entry) delete(c.cache,kv.key) c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len()) } }
根據key獲取快取中元素就簡單了，根據map定位到鏈表元素即可:
func (c *Cache) Get(key string)(value Value,ok bool) {
if ele,ok := c.cache[key];ok {
c.ll.PushFront(ele)
kv := ele.Value.(entry)
return kv.value,true
}
return
}
lru演算法在GeeCache中的實作還是挺好理解的，記錄下~
| 不驕不躁，保持學習
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/501058.html
標籤：其他