既然上一篇写了LRU，那这一篇我们就来搞一下LFU吧。

LFU，Least Frequently Used，最近最少使用，其核心思想是，“如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小”。本文基于 LeetCode 460. LFU 缓存 进行，解法不是最优，但是实现了Get和Put操作的时间复杂度均为O(1)。

这里我们使用一个HashMap实现Get操作的O(1)复杂度，同时使用另一个HashMap，其Key为频次，Value为该频次下缓存节点的双向链表，用于保存该频次的缓存节点，用于维护最小频次。具体算法详解可以看LeetCode官解的方法二（双哈希表），这里不多赘述。

直接上代码：

package lfu

type LFUCache struct {
    cache   map[int]*LFUCacheNode
    freqMap map[int]*LFUCacheList
    minFreq int // 最小频次
    cap     int
}

// 双向链表
type LFUCacheList struct {
    head   *LFUCacheNode     // 虚拟头节点
    end    *LFUCacheNode    // 虚拟尾节点
    length int                 // 链表长度
}

func newLFUCacheList() *LFUCacheList {
    list := &LFUCacheList{
        head: newLFUCacheNode(0, 0),
        end:  newLFUCacheNode(0, 0),
    }
    list.head.next = list.end
    list.end.pre = list.head
    list.length = 2
    return list
}

func (l *LFUCacheList) removeNode(node *LFUCacheNode) bool {
    node.removeNode()
    l.length--
    // 查询长度，若小于等于2，即该链表没有元素，通知删除该链表
    if l.length <= 2 {
        return true
    }
    return false
}

// 将节点添加到双向链表前面
func (l *LFUCacheList) addToHead(node *LFUCacheNode) {
    node.moveToHead(l.head)
    l.length++
}

// 获取链表的最后一个节点
func (l *LFUCacheList) getLast() *LFUCacheNode {
    return l.end.pre
}

// 链表节点
type LFUCacheNode struct {
    key   int                // Key
    value int                // Value
    pre   *LFUCacheNode        // 前驱结点
    next  *LFUCacheNode        // 后驱节点
    freq  int                // 频次
}

func newLFUCacheNode(key int, value int) *LFUCacheNode {
    return &LFUCacheNode{
        key:   key,
        value: value,
        freq:  0,
    }
}

// 移除节点
func (n *LFUCacheNode) removeNode() {
    n.pre.next = n.next
    n.next.pre = n.pre
    n.pre = nil
    n.next = nil
}

// 插入最前面
func (n *LFUCacheNode) moveToHead(head *LFUCacheNode) {
    head.next.pre = n
    n.next = head.next
    n.pre = head
    head.next = n
}

func Constructor(capacity int) LFUCache {
    return LFUCache{
        cache:   make(map[int]*LFUCacheNode, capacity),
        freqMap: make(map[int]*LFUCacheList),
        cap:     capacity,
        minFreq: 0,
    }
}

func (c *LFUCache) Get(key int) int {
    // bad case
    if c.cap < 1 {
        return -1
    }
    // 查询节点
    node, ok := c.cache[key]
    // 不存在直接返回-1
    if !ok {
        return -1
    }
    // 更新频次链表
    c.refreshNode(node)
    return node.value
}

func (c *LFUCache) Put(key int, value int) {
    // bad case
    if c.cap < 1 {
        return
    }
    // 查询节点
    node, ok := c.cache[key]
    // 节点存在，更新节点
    if ok {
        node.value = value
        c.refreshNode(node)
        return
    }
    // 创建节点
    node = newLFUCacheNode(key, value)
    // 当长度小于容量时，直接插入，并更新节点
    if len(c.cache) < c.cap {
        c.cache[key] = node
        c.refreshNode(node)
        return
    }
    // 长度大于等于容量，需要删除最不常使用的节点
    list := c.freqMap[c.minFreq]
    lastNode := list.getLast()
    isDelete := list.removeNode(lastNode)
    if isDelete {
        delete(c.freqMap, c.minFreq)
    }
    delete(c.cache, lastNode.key)
    // 插入节点
    c.cache[key] = node
    c.refreshNode(node)
    return
}

// 更新节点
func (c *LFUCache) refreshNode(node *LFUCacheNode) {
    // 获取原频次链表
    list, ok := c.freqMap[node.freq]
    // 原频次存在，说明是旧节点，需要删除，不存在则为新节点
    if ok {
        // 删除节点
        isDeleteList := list.removeNode(node)
        if isDeleteList {
            delete(c.freqMap, node.freq)
            // 当需要删除时，说明该频次已无节点，如果最小频次为该节点，则需更新最小频次
            if c.minFreq >= node.freq {
                c.minFreq = node.freq + 1
            }
        }
    } else {
        // 原频次不存在，说明是新节点，频次必定为最小，更新频次
        c.minFreq = node.freq + 1
    }
    // 更新频次
    node.freq += 1
    // 查询新频次链表
    newList, ok := c.freqMap[node.freq]
    // 若存在，直接插入
    if ok {
        newList.addToHead(node)
        return
    }
    // 若不存在，创建链表并插入
    newList = newLFUCacheList()
    c.freqMap[node.freq] = newList
    newList.addToHead(node)
    return
}

测试代码：

package lfu

import (
    "fmt"
    "testing"
)

func TestLC460(t *testing.T) {
    lfu := Constructor(2)
    lfu.Put(1, 1)
    lfu.Put(2, 2)
    fmt.Println(lfu.Get(1))
    lfu.Put(3, 3)
    fmt.Println(lfu.Get(2))
    fmt.Println(lfu.Get(3))
    lfu.Put(4, 4)
    fmt.Println(lfu.Get(1))
    fmt.Println(lfu.Get(3))
    fmt.Println(lfu.Get(3))
}

执行结果：

（End）

最后修改：2022 年 11 月 12 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏