golang玩转LRUcache

大家好！众所周知，作为一名合格的程序猿，不断地学习和交流是提升的关键。今天，一夕和大家一起来了解下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,
	}
}

  

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

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