前言 最近複習操作系統，看到了lru演算法，就去網上搜索下，因此發現了GeeCache，順手寫了一遍。研究下lru演算法的實現。 正文: lru使用map+鏈表實現。map裡面存儲了key以及其對應的鏈表節點。當我們根據某個key訪問緩存值的時候，可以經過map快速定位到該鏈表節點。從而獲取值 下麵我們 ...
前言
最近複習操作系統，看到了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 = 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中的實現還是挺好理解的。記錄下~
| 不驕不躁，保持學習
