乙己说：LFU实现思路整理
要求：设计实现一个LFU（最不经常使用）的缓存淘汰机制。时间复杂度控制在O(1)
最不经常使用这个要求包含两个要素：
(1) 通过key查询[发生在Cache的日常查找上];
(2) 通过使用次数查询 [相同使用次数的查找]；
(1) 元素查询；[GET]
(2) 添加元素；[PUT]
(3) 增加使用次数，其中牵涉移动元素到其他链表；[GET和PUT都会触发该操作]
(1) 移动到头部第一个元素；[每次GET和PUT都会有这个操作]
(2) 移除一个元素；[GET、PUT时由于新增使用次数触发]
(3) 移除最后一个元素；[LFU淘汰时为腾出新空间触发]
(3) 构造一个空链表 head --> tail
因此决定：
Get：查找依赖HashMap，移动依赖链表指针。
if HashMap查询是否存在{
// 存在
(1)使用次数+1
(2)返回value
}
返回-1 // 没查到Put：
if HashMap查询是否存在{
// 存在
(1) 更新节点值；
(2) 更新使用次数+1；
} else{
// 不存在
(1) if 当前缓存空间是否够用 {
// 不够用 则需要LFU淘汰
(1) 删除链表尾部节点
(2) 删除HashMap中尾部节点Key
}
// 正常加入即可
if 当前Freq-双向链表是否存下 {
// 不存在则新建一个空链表 head-->tail
}
(1) 链表添加新节点
(2) Freq--HashMap增加新KV
}incrFreq 使用数加操作，该操作戏份很重，说一下细节：
对于它有两个操作需要注意：
(1) 在使用次数加1的操作中，如果这个节点的使用次数刚好等于minFreq，则为了保证淘汰区总是有元素可淘汰的，需要跟随这个元素minFreq+1；
(2) 每当有新元素（第一次加入到Cache）时，都需要重置minFreq为1；（因为1是可以达到的最小使用次数）
(1) 取出当前节点所在Freq--List（双向链表）
(2) 从当前Freq--List链表中删除当前节点
if 当前使用次数==minFreq && 当前链表是空的{
// 为了保证淘汰区随时都是有元素的，则要跟随这个元素一起加1
minFreq+1
链表为空，因此需要清理freqMap[当前使用次数]
}
当前节点使用次数+1
if 当前使用次数对应的双向链表是否存在{
// 不存在
新建双向链表
}
将当前节点加入到，双向链表头部第一个元素Go实现：
package main
import "fmt"
func main() {
cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)
fmt.Println(cache.Get(1))
cache.Put(3, 3)
fmt.Println(cache.Get(2))
fmt.Println(cache.Get(3))
cache.Put(4, 4)
fmt.Println(cache.Get(1))
fmt.Println(cache.Get(3))
fmt.Println(cache.Get(4))
}
/*
1. 使用2个散列表，第一个散列表用于KV搜索，第二个散列表用于freq[元素使用次数]搜索
2. 每个freq散列表元素[value]是一个双链表
3. 双向链表内维护规则：(1) 新加入节点在前面; (2) LFU淘汰时，删除链表末尾元素;
*/
type Node struct {
key, val int
freq int // 节点使用次数，第一次加入时为1，命中一次+1
prev, next *Node // 构造双向链表
}
// 相同freq的节点，放置在同一个列表里
type NodeList struct {
head, tail *Node
}
type LFUCache struct {
searchMap map[int]*Node
freqMap map[int]*NodeList
maxCap int // 总空间
usedCap int // 当前已用空间
minFreq int // 记录当前元素最小使用次数[说明该使用次数下链表是有元素的]
}
func Constructor(capacity int) LFUCache {
return LFUCache{
searchMap: make(map[int]*Node),
freqMap: make(map[int]*NodeList),
maxCap: capacity,
}
}
func (this *LFUCache) Get(key int) int {
if node, exist := this.searchMap[key]; exist {
// freq加一
this.incrFreq(node)
return node.val
}
return -1
}
func (this *LFUCache) Put(key int, value int) {
if this.maxCap == 0 {
return
}
if node, exist := this.searchMap[key]; exist {
// 元素命中 更新值
node.val = value
this.incrFreq(node)
} else {
// 未命中 保存
// 保存前 判断是否还有空间存储，空间不足则需要执行LFU淘汰
if this.usedCap >= this.maxCap {
delNode := this.freqMap[this.minFreq].removeLastNode() // 删除最小使用次数链表的末尾元素，腾出空间
delete(this.searchMap, delNode.key)
this.usedCap-- // 使用过空间减一
}
// 保存
if this.freqMap[1] == nil {
this.freqMap[1] = createNodeList()
}
newNode := &Node{key: key, val: value, freq: 1}
// 一下两步需要并发锁
this.searchMap[key] = newNode
this.freqMap[1].addNodeForHead(newNode)
this.minFreq = 1 // 此时最小使用次数1下的链表已经有了元素，因此要恢复minFreq
this.usedCap++
}
}
// 新建一个双向链表 用于freqMap的value
func createNodeList() *NodeList {
head, tail := &Node{}, &Node{}
head.next = tail
tail.prev = head
return &NodeList{
head: head,
tail: tail,
}
}
// 为节点使用次数加1，并移动到正确位置
func (this *LFUCache) incrFreq(node *Node) {
_freq := node.freq
this.freqMap[_freq].removeNode(node) // 从原先freq链表中删除
// 在移走一个节点后，由于该节点的freq要加1了
// 如果当前链表为空了，那么minFreq要跟随这个节点一起加1
// 直到有新节点加入时，minFreq重新回到1
if this.minFreq == _freq && this.freqMap[_freq].isEmpty() {
this.minFreq++
delete(this.freqMap, _freq) // 删除freqMap
}
node.freq++ // 该节点使用次数加1
// 将节点加入新链表【头部】
// 当前freq还为空，则需要先构建出双链表
if this.freqMap[node.freq] == nil {
this.freqMap[node.freq] = createNodeList()
}
// 加入链表，并且放在头部第一个元素
this.freqMap[node.freq].addNodeForHead(node)
}
// 维护对象：相同freq[使用次数]的双向链表
func (list *NodeList) removeNode(node *Node) {
node.next.prev = node.prev
node.prev.next = node.next
node.next = nil
node.prev = nil
}
// 维护对象：相同freq[使用次数]的双向链表 逻辑：head == tail 就说明是空的
func (list *NodeList) isEmpty() bool {
return list.head.next == list.tail
}
// 维护对象：相同freq[使用次数]的双向链表
func (list *NodeList) removeLastNode() *Node {
if list.isEmpty() {
return nil
}
lastNode := list.tail.prev
list.removeNode(lastNode)
return lastNode
}
// 维护对象：相同freq[使用次数]的双向链表
func (list *NodeList) addNodeForHead(node *Node) {
node.next = list.head.next
node.prev = list.head
list.head.next.prev = node
list.head.next = node
}