LFU缓存算法（Least Frequently Used）

题目描述
LFU（最近最少使用）是一种缓存淘汰策略，当缓存达到容量上限时，会淘汰使用频率最低的数据。如果有多个数据的使用频率相同，则淘汰其中最久未使用的数据。相比LRU只关注访问时间，LFU增加了访问频率的维度，能更好地反映数据的长期访问模式。

核心概念解析

1. 缓存项需要存储键(key)、值(value)、使用频率(freq)和最近使用时间(timestamp)
2. 需要快速根据键找到缓存项（哈希表）
3. 需要快速找到最小频率的项（频率索引）
4. 同频率项需要按时间排序（LRU顺序）

数据结构设计
我们使用三个核心数据结构：

# 缓存项节点
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1  # 初始频率为1
        self.prev = None
        self.next = None

# 双向链表（用于维护同频率项的LRU顺序）
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_to_head(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_node(self, node):
        """从链表中移除指定节点"""
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
    
    def remove_tail(self):
        """移除链表尾部节点（最久未使用）"""
        if self.size == 0:
            return None
        tail_node = self.tail.prev
        self.remove_node(tail_node)
        return tail_node

LFU缓存实现步骤

步骤1：初始化数据结构

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0  # 当前最小频率
        self.key_map = {}  # key -> Node 的映射
        self.freq_map = {}  # freq -> DoublyLinkedList 的映射

步骤2：获取操作 get(key)

def get(self, key: int) -> int:
    if key not in self.key_map:
        return -1
    
    # 获取节点并更新频率
    node = self.key_map[key]
    self._update_freq(node)
    return node.value

步骤3：插入操作 put(key, value)

def put(self, key: int, value: int) -> None:
    if self.capacity == 0:
        return
    
    if key in self.key_map:
        # 键已存在，更新值并增加频率
        node = self.key_map[key]
        node.value = value
        self._update_freq(node)
    else:
        # 新键插入
        if len(self.key_map) >= self.capacity:
            self._evict()  # 淘汰最少使用的项
        
        new_node = Node(key, value)
        self.key_map[key] = new_node
        self._add_to_freq_list(new_node, 1)  # 初始频率为1
        self.min_freq = 1  # 新节点频率最低为1

步骤4：关键辅助方法实现

def _update_freq(self, node):
    """更新节点频率"""
    old_freq = node.freq
    new_freq = old_freq + 1
    
    # 从原频率链表中移除
    old_list = self.freq_map[old_freq]
    old_list.remove_node(node)
    
    # 如果原链表为空且是最小频率，更新min_freq
    if old_list.size == 0 and old_freq == self.min_freq:
        self.min_freq = new_freq
    
    # 添加到新频率链表
    node.freq = new_freq
    self._add_to_freq_list(node, new_freq)

def _add_to_freq_list(self, node, freq):
    """将节点添加到对应频率的链表中"""
    if freq not in self.freq_map:
        self.freq_map[freq] = DoublyLinkedList()
    freq_list = self.freq_map[freq]
    freq_list.add_to_head(node)  # 新访问的放到头部

def _evict(self):
    """淘汰使用频率最低且最久未使用的节点"""
    min_freq_list = self.freq_map[self.min_freq]
    removed_node = min_freq_list.remove_tail()  # 移除尾部（最久未用）
    del self.key_map[removed_node.key]
    
    # 如果最小频率链表为空，不需要立即更新min_freq
    # 在下次访问时会自动更新

完整算法流程示例

假设容量为2，操作序列：put(1,1), put(2,2), get(1), put(3,3)

1. put(1,1): 频率1链表：[1]
2. put(2,2): 频率1链表：[2→1]（2最新）
3. get(1):
   • 1从频率1链表移除
   • 1加入频率2链表：[1]
   • 最小频率变为1（因为频率1链表还有节点2）
4. put(3,3):
   • 缓存已满，淘汰频率1链表尾部节点2
   • 插入3到频率1链表：[3]

时间复杂度分析

• get操作：O(1) - 哈希表查找+链表操作
• put操作：O(1) - 哈希表操作+常数次链表操作
• 空间复杂度：O(capacity) - 存储所有缓存项

实际应用场景

1. 数据库查询缓存
2. 网页缓存系统
3. 操作系统页面置换
4. CDN内容分发网络

LFU算法通过结合访问频率和时间两个维度，在需要长期热点数据识别的场景中比LRU有更好的表现。