缓存淘汰算法 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+=
}

缓存淘汰算法 LRU