LRU LFU算法及实现

LRU实现

LRU即最近最少使用，每次插入数据如果到达上限就删除最久的数据

```go
//缓存里的数据结构，k-v键值对
type entry struct{
    key,value int
}

//LRUCache结构，容量
//list.List是go包提供的双向链表，有PushFront、PushBack、MoveToFront、Remove、Front、Back等功能
//建立一个key-节点等哈希表
type LRUCache struct {
    capacity int
    list *list.List
    keyToNode map[int]*list.Element
}

//初始化构造LRUCache
func Constructor(capacity int) LRUCache {
    return LRUCache{capacity,list.New(),map[int]*list.Element{}}
}

//取出，就用哈希表来查看，并且因为这算一个操作
//把这个节点放到最前面
//因为list本身每个Element都是interface{}，所以需要.(entry)类型断言
func (this *LRUCache) Get(key int) int {
    node:=this.keyToNode[key]
    if node==nil{
        return -1
    }
    this.list.MoveToFront(node)
    return node.Value.(entry).value
}

func (this *LRUCache) Put(key int, value int)  {
    //如果关键字存在，就变更value
    if node:=this.keyToNode[key];node!=nil{
        node.Value=entry{key,value}
        this.list.MoveToFront(node)
        return
    }
    //如果不存在，就在最前面插入k-v
    this.keyToNode[key]=this.list.PushFront(entry{key,value})
    //如果长度超出容量，就删掉结尾的k-v
    if len(this.keyToNode)>this.capacity{
        delete(this.keyToNode,this.list.Remove(this.list.Back()).(entry).key)
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

LFU实现

LFU即最不经常使用，如果满了就清理掉使用频率最少的那个

```go
//key-value结构，包含了频率
type entry struct{
    key,value,freq int
}

//对象包含
//容量
//最少频率
//key到node转换的哈希表
//频率到链表转换到哈希表
type LFUCache struct {
    capacity int
    minFreq int
    keyToNode map[int]*list.Element
    freqToList map[int]*list.List
}

//初始化构造
func Constructor(capacity int) LFUCache {
    return LFUCache{
        capacity:capacity,
        keyToNode: map[int]*list.Element{},
        freqToList:map[int]*list.List{},
    }
}

//在内部实现pushFront方法
//如果没有这个节点频率对应的链表，那么就创建一个新的
//把这个key对应node放到最前方
func (c *LFUCache)pushFront(e *entry){
    if _,ok:=c.freqToList[e.freq];!ok{
        c.freqToList[e.freq]=list.New()
    }
    c.keyToNode[e.key]=c.freqToList[e.freq].PushFront(e)
}

//内部实现getEntry方法
//因为get也是操作一次，就在原频率链表上删除，本身频率++并且放到最上方
//如果这个频率链表因此为空，就直接删掉，同时最小频率++
func (c *LFUCache)getEntry(key int)*entry{
    node:=c.keyToNode[key]
    if node==nil{
        return nil
    }
    e:=node.Value.(*entry)
    lst:=c.freqToList[e.freq]
    //频率+1了，所以原链表里删掉
    lst.Remove(node)
    if lst.Len()==0{
        delete(c.freqToList,e.freq)
        if c.minFreq==e.freq{
            c.minFreq++
        }
    }
    //自身频率+1，新链表里放到顶
    e.freq++
    c.pushFront(e)
    return e
}

//实际的Get操作，通过getEntry获取
func (c *LFUCache) Get(key int) int {
    if e:=c.getEntry(key);e!=nil{
        return e.value
    }
    return -1
}

//实际的Put操作
func (c *LFUCache) Put(key int, value int)  {
    //如果键已存在，更新值
    if e:=c.getEntry(key);e!=nil{
        e.value=value
        return
    }
    //如果到容量了
    if len(c.keyToNode)==c.capacity{
        //找到最小频率的链表
        lst:=c.freqToList[c.minFreq]
        //删掉最下方最少使用的那个
        delete(c.keyToNode,lst.Remove(lst.Back()).(*entry).key)
        if lst.Len()==0{
            delete(c.freqToList,c.minFreq)
        }
    }
    //把新的值放到最上方
    c.pushFront(&entry{key,value,1})
    //更新最小频率重新为1
    c.minFreq=1
}

区别

特性	LRU	LFU
淘汰规则	最近最少用的	使用次数最少的
应用场景	偏重于「时间相关性」的缓存	偏重于「使用频率相关性」的缓存
实现复杂度	相对简单（O(1)）	稍复杂（接近 O(1)）
典型应用	操作系统页缓存、浏览器缓存	数据库缓存、分布式缓存

使用

在redis里内存淘汰策略有LRU和LFU两种情况

Redis 里用 LRU	Redis 里用 LFU
allkeys-lru/volatile-lru策略	allkeys-lfu/volatile-lfu策略
基于访问时间戳，近似 LRU 抽样算法	基于 8 位概率性计数器 + 衰减

策略名	描述
noeviction	不淘汰，内存满了就返回错误（默认）
allkeys-lru	所有 key 中，优先淘汰最近最少用的（LRU）
volatile-lru	只对设置了expire的 key，淘汰最近最少用的
allkeys-lfu	所有 key 中，优先淘汰访问频率最低的（LFU）
volatile-lfu	只对设置了expire的 key，淘汰访问频率最低的
allkeys-random	所有 key 中，随机淘汰
volatile-random	只对设置了expire的 key，随机淘汰
volatile-ttl	只对设置了expire的 key，淘汰剩余时间最短的