缓存淘汰算法 LRU
LRU
LRU(Least Recently Used:最近最少使用)算法在缓存写满时,会根据所有数据的访问记录,淘汰掉本来访问几率最低的数据,也就是说该算法认为,最近被访问过的数据,在将来访问的几率更大。
假设我们有这么一块内存,一共有26个数据储存快。
- 当我们连续插入A、B、C...Z的时候,此时内存已经满了
- 那么当我们在插入一个6时,那么此时会将内存存放时间最久的数据A淘汰掉
- 当我们从外部读取数据C时,此时C就会提到头部,这时候C就是最晚淘汰的了。
其实流程来说很简单,我们拆分一下的话,不难发现这就是在维护一个双向链表。
代码实现
定义一个存放数据块的结构
type item struct{
key string
value any
//the frequency of key
freq int
}
定义一个LRU算法结构
type LRU struct{
dl *list.List //维护的双端队列
size int //当天容量
max int //限制的容量
storage map[string]*list.Element //储存的key
}
获取某个key的value函数,如果存在这个key,那么我们就把这个值移动到最前面MoveToFront
,否则返回一个nil.
func(c *LRU)Get(key string)any{
v,ok:=c.storage[key]
if ok{
c.dl.MoveToFrnt(v)
return v.Value.(item).value
}
return nil
}
当我们需要put进去一些东西是,会分一下几个步骤
- 是否存在,如果存在则,直接返回,并且将key移动到最前面
- 如果不存在,但是已经到了极限容量了,就把最后一个Last(),淘汰掉,然后在塞入。
塞入的话,是塞入到最前面
func(c *LRU) Put(key string,value any){ e,ok := c.storage[key] if ok { n:=e.value.(item) n.value = value e.Value = n d.dl.MoveToFront(e) return } if c.size >= c.max{ e = c.dl.Last() dk:=e.Value.(item).key c.dl.Remove(e) delete(c.storage,dk) c.size-- } n:=item{key:key,value:value} c.dl.PushFront(n) ne:=c.dl.front() c.storage[key]=ne c.size+= }