前言
最近复习操作系统，看到了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中的实现还是挺好理解的。记录下~
| 不骄不躁，保持学习
文章评论