LeetCode 题目 ：460.LFU 缓存的实现[https://leetcode-cn.com/problems/lfu-cache/]
要求：设计实现一个 LFU（最不经常使用）的缓存淘汰机制。时间复杂度控制在 O(1)
最不经常使用这个要求包含两个要素：时间和次数，使用次数最少的元素优先淘汰，当使用次数最少的元素是多个时（比如使用次数都是 1），则最久未用到的淘汰（此时问题变为了 LRU，可以参看前文[https://xie.infoq.cn/article/6b446f0b9d21f0af4fa562f58]）。
分析后可知在使用次数最少的元素中，其实使用的是 LRU(最近最少使用)算法。所以此类处理要使用到双向链表。最近使用的放头部，尾部自然就成了最久未使用的元素，并且新增和删除操作复杂度为 O(1) 。
其次 O(1) 的查询复杂度需要依赖哈希表。并且存在两种查询：
(1) 通过 key 查询[发生在 Cache 的日常查找上];
(2) 通过使用次数查询 [相同使用次数的查找]；
算法涉及的操作有哪些：
(1) 元素查询；[GET]
(2) 添加元素；[PUT]
(3) 增加使用次数，其中牵涉移动元素到其他链表；[GET 和 PUT 都会触发该操作]
相同使用次数的双向链表的操作：
(1) 移动到头部第一个元素；[每次 GET 和 PUT 都会有这个操作]
(2) 移除一个元素；[GET、PUT 时由于新增使用次数触发]
(3) 移除最后一个元素；[LFU 淘汰时为腾出新空间触发]
(3) 构造一个空链表 head --> tail
因此决定：2 个 HashMap+N 个双向链表，第一个 HashMap 用于 KV 搜索，第二个 HashMap 用于 Freq【元素使用次数】搜索，其中 Freq--HashMap 的每一个 Value 都是一个双向链表
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 使用数加操作，该操作戏份很重，说一下细节：
minFreq 的作用：记录当前有元素的链表中，使用次数最少的那个次数。或者说是淘汰区的标记。
对于它有两个操作需要注意：
(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的valuefunc 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}
复制代码
评论