Go语言实现LFU缓存淘汰机制（深入浅出讲解LFU缓存算法与数据结构）

LFU 的关键挑战

实现一个高效的 LFU 缓存并不简单，主要难点在于：

• 如何快速找到频率最低的键？
• 如何在 O(1) 时间内更新某个键的访问频率？
• 如何处理多个键具有相同频率的情况？

Go语言实现 LFU 缓存

我们将使用以下数据结构组合来实现 O(1) 时间复杂度的 LFU 缓存：

• map[int]*Node：存储 key 到节点的映射
• map[int]*List：存储频率到双向链表的映射
• 双向链表（自定义）：每个频率对应一个链表，链表中的节点按插入顺序排列

1. 定义节点和链表

type Node struct {    key, val, freq int    prev, next     *Node}type List struct {    head, tail *Node    size       int}func newList() *List {    head := &Node{}    tail := &Node{}    head.next = tail    tail.prev = head    return &List{head: head, tail: tail}}func (l *List) pushFront(node *Node) {    node.next = l.head.next    node.prev = l.head    l.head.next.prev = node    l.head.next = node    l.size++}func (l *List) remove(node *Node) {    node.prev.next = node.next    node.next.prev = node.prev    l.size--}func (l *List) popBack() *Node {    if l.size == 0 {        return nil    }    last := l.tail.prev    l.remove(last)    return last}

2. 实现 LFU 缓存结构

type LFUCache struct {    capacity   int    minFreq    int    keyMap     map[int]*Node    freqMap    map[int]*List}func Constructor(capacity int) LFUCache {    return LFUCache{        capacity: capacity,        minFreq:  0,        keyMap:   make(map[int]*Node),        freqMap:  make(map[int]*List),    }}

3. Get 操作

func (lfu *LFUCache) Get(key int) int {    if lfu.capacity == 0 {        return -1    }    node, exists := lfu.keyMap[key]    if !exists {        return -1    }    lfu.updateFreq(node)    return node.val}func (lfu *LFUCache) updateFreq(node *Node) {    // 从旧频率链表中移除    oldList := lfu.freqMap[node.freq]    oldList.remove(node)    if oldList.size == 0 && lfu.minFreq == node.freq {        lfu.minFreq++    }    // 增加频率并加入新链表    node.freq++    newList, exists := lfu.freqMap[node.freq]    if !exists {        newList = newList()        lfu.freqMap[node.freq] = newList    }    newList.pushFront(node)}

4. Put 操作

func (lfu *LFUCache) Put(key int, value int) {    if lfu.capacity == 0 {        return    }    if node, exists := lfu.keyMap[key]; exists {        node.val = value        lfu.updateFreq(node)        return    }    // 缓存已满，需要淘汰    if len(lfu.keyMap) >= lfu.capacity {        listToEvict := lfu.freqMap[lfu.minFreq]        evictedNode := listToEvict.popBack()        delete(lfu.keyMap, evictedNode.key)    }    // 添加新节点    newNode := &Node{key: key, val: value, freq: 1}    lfu.keyMap[key] = newNode    if _, exists := lfu.freqMap[1]; !exists {        lfu.freqMap[1] = newList()    }    lfu.freqMap[1].pushFront(newNode)    lfu.minFreq = 1}

使用示例

func main() {    cache := Constructor(2)    cache.Put(1, 1)    cache.Put(2, 2)    fmt.Println(cache.Get(1)) // 输出: 1    cache.Put(3, 3)           // 淘汰 key=2（频率最低）    fmt.Println(cache.Get(2)) // 输出: -1    fmt.Println(cache.Get(3)) // 输出: 3}

总结

通过本文，我们深入理解了 LFU 缓存淘汰算法的原理，并使用 Go语言实现了高效的 O(1) 时间复杂度版本。这种实现方式巧妙地结合了哈希表和双向链表，是学习 数据结构 和 缓存算法 的绝佳案例。

掌握 LFU 不仅能帮助你在面试中脱颖而出，还能在实际项目中优化系统性能。希望这篇教程对你有所帮助！

关键词：Go语言, LFU缓存淘汰, 数据结构, 缓存算法