LFU缓存详解（用Python从零实现最不经常使用缓存）

为什么需要LFU缓存？

在高并发系统中，某些热点数据会被频繁访问。LFU能有效保留这些热点数据，提高缓存命中率。这也是为什么缓存淘汰策略在系统设计中如此重要。

LFU缓存的挑战

看似简单的LFU其实有两大难点：

1. 高效更新频率：每次访问都要更新计数
2. 快速找到最小频率项：淘汰时要迅速定位使用最少的数据

如果用普通字典+列表实现，时间复杂度会很高。我们需要更聪明的数据结构！

Python实现LFU缓存

我们将使用以下数据结构组合：

• key_to_node：字典，存储键到节点的映射
• freq_to_list：字典，存储频率到双向链表的映射
• min_freq：记录当前最小频率，用于快速淘汰

首先定义缓存节点类：

class Node:    def __init__(self, key, val):        self.key = key        self.val = val        self.freq = 1  # 初始频率为1        self.prev = None        self.next = None  

然后实现双向链表辅助类：

class DoublyLinkedList:    def __init__(self):        self.head = Node(0, 0)  # 哨兵节点        self.tail = Node(0, 0)        self.head.next = self.tail        self.tail.prev = self.head        self.size = 0        def add_first(self, node):        node.next = self.head.next        node.prev = self.head        self.head.next.prev = node        self.head.next = node        self.size += 1        def remove(self, node):        node.prev.next = node.next        node.next.prev = node.prev        self.size -= 1        return node        def remove_last(self):        if self.size > 0:            last_node = self.tail.prev            self.remove(last_node)            return last_node        return None  

最后是LFU缓存主类：

class LFUCache:    def __init__(self, capacity: int):        self.capacity = capacity        self.key_to_node = {}          # key -> Node        self.freq_to_list = {}         # freq -> DoublyLinkedList        self.min_freq = 0              # 当前最小频率        def get(self, key: int) -> int:        if key not in self.key_to_node:            return -1                node = self.key_to_node[key]        self._update_freq(node)  # 更新频率        return node.val        def put(self, key: int, value: int) -> None:        if self.capacity == 0:            return                if key in self.key_to_node:            # 更新已有键            node = self.key_to_node[key]            node.val = value            self._update_freq(node)        else:            # 插入新键            if len(self.key_to_node) >= self.capacity:                # 缓存满，淘汰最小频率的最后一个节点                old_list = self.freq_to_list[self.min_freq]                removed_node = old_list.remove_last()                del self.key_to_node[removed_node.key]                        new_node = Node(key, value)            self.key_to_node[key] = new_node            # 新节点频率为1            if 1 not in self.freq_to_list:                self.freq_to_list[1] = DoublyLinkedList()            self.freq_to_list[1].add_first(new_node)            self.min_freq = 1  # 新插入节点频率为1，所以最小频率重置为1        def _update_freq(self, node):        # 从原频率链表中移除        old_freq = node.freq        old_list = self.freq_to_list[old_freq]        old_list.remove(node)                # 如果原频率链表为空且等于min_freq，更新min_freq        if old_list.size == 0 and old_freq == self.min_freq:            self.min_freq += 1                # 增加频率并加入新链表        node.freq += 1        new_freq = node.freq        if new_freq not in self.freq_to_list:            self.freq_to_list[new_freq] = DoublyLinkedList()        self.freq_to_list[new_freq].add_first(node)  

如何测试你的LFU缓存？

你可以这样简单测试：

# 创建容量为2的LFU缓存cache = LFUCache(2)cache.put(1, 1)cache.put(2, 2)print(cache.get(1))   # 输出: 1cache.put(3, 3)       # 淘汰key=2（因为1被访问过2次，2只被访问1次）print(cache.get(2))   # 输出: -1 (未找到)print(cache.get(3))   # 输出: 3  

总结

通过本教程，你已经掌握了LFU缓存的核心原理和Python实现方法。这种缓存淘汰策略在实际项目中非常有用，特别是在处理热点数据时。记住，理解数据结构的选择是高效实现的关键！

现在你已经可以自信地说：我懂Python缓存实现了！继续加油，成为更优秀的开发者吧！

关键词回顾：LFU缓存、Python缓存实现、缓存淘汰策略、Least Frequently Used