大家好！众所周知，作为一名合格的程序猿，不断地学习和交流是提升的关键。今天，一夕和大家一起来了解下LRU缓存淘汰。

先介绍下LRUcache。大家都知道，缓存在任何稍具规模的项目里，都有着举足轻重的地位，而对于性能要求高的系统，缓存都是使用内存的，大小受限。那么当缓存空间被用满时，哪些数据应该被清理出去？这就需要缓存淘汰策略来决定。常见的策略有三种：FIFO（First In，First Out）、LFU（Least Frequently Used）、LRU（Least Recently Used）。今天我们先来了解LRU策略（淘汰最近最少使用的数据）。

首先，既然是实现一个cache功能，那么我们先来定义一个cache接口，以及LRU的结构体

而要想实现一个功能，首先我们就要想到用什么数据结构来实现，这里一夕首先就想到的是双链表。用双链表来实现的话，如果某条数据被访问了，则把该条数据移动到链表首部，队尾是最少使用的元素，内存超出限制时，淘汰队尾元素即可。（双链表移动任意记录到队首时间复杂度O(1)，队首添加记录也是O(1)，删除记录也是O(1)）。

下面，show code

 package cache

import (
"container/list"
"sync"
)

type Cache interface {
Set(key string, value interface{})
Get(key string) interface{}
Del(key string)

// 缓存删除策略
DelPolicy()
}

type LRUCache struct {
sync.RWMutex
dll *list.List //doubleLinkedList 双链表
cache map[string]*list.Element //采用双链表储存数据，这里value存为双链表对应节点的指针
maxSize int  //cache缓存最大容量 字节
usedSize int //已用容量
}

func (c *LRUCache)Set(key string,value interface{})  {
c.Lock()
defer c.Unlock() //并发
if elm,ok := c.cache[key];ok {
c.dll.MoveToFront(elm) //将该value移到头部
elm.Value = value  //更新
//todo 更新cache内存占用
}else{
p := c.dll.PushFront(value) //存入双链表 并返回对应指针
c.cache[key] = p
//todo 更新cache内存占用
}

for c.usedSize > c.maxSize { //执行LRU策略
c.DelPolicy()
}
}

func (c *LRUCache)Get(key string) interface{} {
c.RLock()
defer c.RUnlock()
if elm,ok := c.cache[key];ok {
c.dll.MoveToFront(elm)
return elm.Value
}
return nil
}

func (c *LRUCache)Del(key string)  {
c.Lock()
defer c.Unlock()
if elm,ok := c.cache[key];ok {
c.dll.Remove(elm)
//todo 更新占用内存
delete(c.cache,key)
}
}

func (c *LRUCache)DelPolicy()  {
c.Lock()
defer c.Unlock()
var key string //获取被淘汰链表数据对应的key
for k,v :=range c.cache {
if v==c.dll.Back() {
key = k
break
}
}
// （ps: 这里可以优化，cache map里面存的value可以用一个结构体包含对应的key和value，这样可以不用遍历cache就获取key了）
c.dll.Remove(c.dll.Back())
//todo 更新占用内存
delete(c.cache,key)
}

func NewLRUCache(size int) Cache {
return &LRUCache{
dll: list.New(),
cache: make(map[string]*list.Element),
maxSize:size,
}
}

  

如此，大致功能就完成了。

各位条友们，欢迎大家前来交流，一起进步。