哈希算法题目：LFU 缓存

题目描述
设计并实现最不经常使用（LFU）缓存机制。实现 LFUCache 类：

• LFUCache(int capacity)：用数据结构的容量 capacity 初始化对象
• int get(int key)：如果键 key 存在于缓存中，则获取键的值，否则返回 -1
• void put(int key, int value)：如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键

解题过程

步骤1：理解LFU的淘汰规则
LFU缓存的核心淘汰策略是：当缓存容量满时，移除访问频率最小的键。如果有多个键的频率相同（平局情况），则移除这些键中最久未被访问的那个。

步骤2：数据结构设计分析
需要同时维护三种信息：

1. 键值对存储（快速通过key获取value）
2. 每个key的访问频率计数（记录每个key被访问的次数）
3. 相同频率key的访问时序（解决平局情况）

步骤3：核心数据结构选择
使用三个哈希表：

• keyToVal：存储key-value映射
• keyToFreq：存储key-frequency映射
• freqToKeys：存储frequency到key集合的映射，且每个频率对应的key集合要维护访问时序（使用LinkedHashSet）

步骤4：详细数据结构设计

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity  # 容量限制
        self.minFreq = 0     # 当前最小频率
        self.keyToVal = {}   # key到value的映射
        self.keyToFreq = {}  # key到频率的映射
        self.freqToKeys = defaultdict(LinkedHashSet)  # 频率到key集合的映射

步骤5：LinkedHashSet的实现
LinkedHashSet需要同时具备哈希表的快速查找和链表的时序特性：

class LinkedHashSet:
    def __init__(self):
        self.keys = []        # 维护插入顺序
        self.keySet = set()   # 快速判断是否存在
    
    def add(self, key):
        if key not in self.keySet:
            self.keys.append(key)
            self.keySet.add(key)
    
    def remove(self, key):
        if key in self.keySet:
            self.keys.remove(key)
            self.keySet.remove(key)
    
    def pop_first(self):
        if not self.keys:
            return None
        key = self.keys.pop(0)
        self.keySet.remove(key)
        return key

步骤6：get操作实现逻辑

1. 如果key不存在，返回-1
2. 如果key存在：
   • 增加该key的频率计数
   • 将该key从原频率集合移到新频率集合
   • 更新minFreq（如果原频率是最小频率且该频率集合变空）
   • 返回对应的value

步骤7：put操作实现逻辑

1. 如果key已存在：更新value，并执行get操作更新频率
2. 如果key不存在：
   • 如果容量已满，需要淘汰：
     • 从minFreq对应的集合中移除最久未使用的key
     • 清理相关数据结构
   • 插入新key：
     • 频率初始化为1
     • minFreq重置为1
     • 更新所有相关映射

步骤8：频率更新辅助函数

def increaseFreq(self, key):
    freq = self.keyToFreq[key]
    # 更新频率计数
    self.keyToFreq[key] = freq + 1
    # 从原频率集合移除
    self.freqToKeys[freq].remove(key)
    # 添加到新频率集合
    self.freqToKeys[freq + 1].add(key)
    
    # 如果原频率是最小频率且该集合变空
    if freq == self.minFreq and not self.freqToKeys[freq].keys:
        self.minFreq += 1

步骤9：淘汰最小频率键函数

def removeMinFreqKey(self):
    # 获取最小频率对应的key集合
    keyList = self.freqToKeys[self.minFreq]
    # 移除最久未使用的key（集合中的第一个）
    deletedKey = keyList.pop_first()
    
    # 清理相关数据
    if not keyList.keys:
        del self.freqToKeys[self.minFreq]
    
    del self.keyToVal[deletedKey]
    del self.keyToFreq[deletedKey]

步骤10：完整算法整合
将以上各个部分组合起来，注意边界条件处理（容量为0的情况），确保所有操作的时间复杂度为O(1)。