毕竟上一篇文章的项目都用到了, 不妨来讲一下
最近最不常用(LFU, Least Frequently Used)算法
以次数作为参考,如果次数相同,则淘汰最早的数据
因为规则多了,LFU会比LRU复杂,而且有多种方法实现,我们只看常用的:
- 双哈希表(+N个双向链表), 一个HashMap实现Get操作的O(1)复杂度，同时使用另一个HashMap，其Key为频次，Value为该频次下缓存节点的双向链表，用于保存该频次的缓存节点，用于维护最小频次
第一个哈希表是key-value的哈希表(以下简称kv哈希表)
key就是输入的key，而它的value不是一个简单的value，而是一个节点对象Node
节点对象Node包含了key，value，以及频率，这个Node也会出现在第二个哈希表的value中。
至于为什么Node中又重复包含了key，因为某些情况下我们不是通过k-v哈希表拿到Node的，而是通过其他方式获得了Node，之后需要用Node中的key去k-v哈希表中做一些操作，所以Node中包含了一些冗余信息
第二张哈希表，频率哈希表
key是频率，也就是元素被访问的频率(被访问了1次，被访问了两次等等)，它的value是一个双向链表
刚才说的Node对象和这里的Node是一个东西,它其实是双向链表中的一个节点。
第一张图中我们介绍了Node中包含了一个冗余的key，其实它还包含了一个冗余的频率值，因为某些情况下，我们需要通过Node中的频率值，去频率哈希表中做查找，所以也需要一个冗余的频率值。
两张表结合起来:
k-v哈希表中key1指向一个Node，这个Node的频率为1，位于频率哈希表中key=1下面的双链表中(处于第一个节点)
获取数据
具体逻辑大致是这样：
- 如果key不存在则返回-1/nil/false,根据API而定
- 如果key存在，则返回对应的value，同时:
- 假设该key对应的Node的频率为i,将该Node的访问频率+1,并将Node从访问频率为i的链表中移出，放到频率为i+1的链表中(如果这个频率的链表不存在,就需要先创建)
- 如果移出之后,频率i的链表为空，则从频率哈希表中移除这个链表
添加/更新数据
- 如果key已经存在，修改对应的value，并将访问频率+1
- 将元素从访问频率
i的链表中移除，放到频率i+1的链表中 - 如果频率
i的链表为空，则从频率哈希表中移除这个链表
- 将元素从访问频率
- 如果key不存在
- 缓存超过最大容量，则先删除访问频率最低的元素(如果对应链表为空也要删)，再插入新元素
- 新元素的访问频率为1，如果频率哈希表中不存在对应的链表需要创建
- 缓存没有超过最大容量，则插入新元素
- 新元素的访问频率为1，如果频率哈希表中不存在对应的链表需要创建
- 缓存超过最大容量，则先删除访问频率最低的元素(如果对应链表为空也要删)，再插入新元素
我们在代码实现中还需要维护一个minFreq的变量，用来记录LFU缓存中频率最小的元素，在缓存满的时候，可以快速定位到最小频繁的链表，以达到 O(1) 时间复杂度删除一个元素。 维护minFreq的具体做法是:
- 更新/查找的时候，将Node频率+1之后,如果
minFreq对应的链表不在频率哈希表中了，说明那条链表已经没有元素,被删除了.那么minFreq需要+1，否则minFreq不变。 - 插入的时候，因为新元素的频率都是1，所以只需要将minFreq改为1即可。
看下缓存超过最大容量时是怎么处理的:
综上所述,LFU的代码如下:
// OnEvicted 当key-value被淘汰时 执行的处理函数 cachestrategy包里的
type OnEvicted func(key string, value Lengthable)
// Node 定义双向链表节点所存储的对象
// 其实key和freq可以不用存储在Node中，但是为了一些情况下查找方便，就存了
type Node struct {
key string
value Value
freq int
}
// Cache 是LFU算法实现的缓存
type Cache struct {
maxByte int64 // Cache 最大容量(Byte)
currByte int64 // Cache 当前容量(Byte)
kvMap map[string]*list.Element // key对应的双向链表节点
freqMap map[int]*list.List // 频率对应的双向链表,链头表示最近使用
minFreq int // 最小频率
callback cachestrategy.OnEvicted // 淘汰回调(可选)
}
// New 创建指定最大容量的LFU缓存
// 当maxBytes为0时，代表cache无内存限制，无限存放
func New(maxBytes int64, callback cachestrategy.OnEvicted) *Cache {
return &Cache{
maxByte: maxBytes,
kvMap: make(map[string]*list.Element),
freqMap: make(map[int]*list.List),
callback: callback,
}
}
// Len 返回当前缓存元素个数
func (c *Cache) Len() int64 {
return int64(len(c.kvMap))
}
// Get 从缓存获取对应key的value。
// ok 指明查询结果 false代表查无此key
func (c *Cache) Get(key string) (value Value, ok bool) {
if elem, ok := c.kvMap[key]; ok {
c.updateFreq(elem)
node := elem.Value.(*Node)
return node.value, true
}
return
}
// Add 向缓存添加/更新一枚key-value
func (c *Cache) Add(key string, value Value) {
kvSize := int64(len(key)) + int64(value.Len())
// cache 容量检查
for c.maxByte != 0 && c.currByte+kvSize > c.maxByte {
c.Evict()
}
if elem, ok := c.kvMap[key]; ok {
node := elem.Value.(*Node)
c.currByte += int64(value.Len()) - int64(node.value.Len())
node.value = value
c.updateFreq(elem)
} else {
// 新增缓存key值
node := &Node{key: key, value: value, freq: 1}
// 如果freq为1的链表不存在，创建该链表
if _, ok := c.freqMap[1]; !ok {
c.freqMap[1] = list.New()
}
elem := c.freqMap[1].PushFront(node)
c.kvMap[key] = elem
// 更新minFreq
c.minFreq = 1
// 更新写入字节
c.currByte += kvSize
}
}
// Evict 淘汰一枚最低频率的缓存,如果次数相同,则淘汰最早的数据
func (c *Cache) Evict() {
// 获取最低频率的链表
lowFreqList := c.freqMap[c.minFreq]
// 获取最低频率链表的最后一个节点
node := lowFreqList.Back().Value.(*Node)
// 删除最低频率链表的最后一个节点
lowFreqList.Remove(lowFreqList.Back())
// 删除kvMap中对应的key
delete(c.kvMap, node.key)
// 更新写入字节
c.currByte -= int64(len(node.key)) + int64(node.value.Len())
// 如果最低频率链表为空，删除该链表
if lowFreqList.Len() == 0 {
delete(c.freqMap, c.minFreq)
}
// 执行淘汰回调
if c.callback != nil {
c.callback(node.key, node.value)
}
}
func (c *Cache) updateFreq(elem *list.Element) {
node := elem.Value.(*Node)
// 将节点从原来的freq对应的链表中删除
c.freqMap[node.freq].Remove(elem)
// 更新节点的freq
node.freq++
// 如果新的freq对应的链表不存在，创建该链表
if _, ok := c.freqMap[node.freq]; !ok {
c.freqMap[node.freq] = list.New()
}
// 将节点插入到新的freq对应的链表中
c.freqMap[node.freq].PushFront(elem)
// 如果原来的freq对应的链表为空，删除该链表
if c.freqMap[node.freq].Len() == 0 {
delete(c.freqMap, node.freq)
}
// 更新minFreq
if c.minFreq == node.freq-1 {
c.minFreq++
}
}