LFU缓存机制 题目描述 LFU（Least Frequently Used）是一种缓存淘汰策略，当缓存达到容量上限时，会淘汰最不经常使用的数据项。这里的使用频率指的是数据项被访问（get）或更新（put）的次数。如果存在多个数据项具有相同的最低使用频率，则应该淘汰其中最久未被使用的数据项。请设计并实现一个满足O(1)时间复杂度进行get和put操作的LFU缓存类。 解题过程 核心思路分析 要实现O(1)的get和put，我们需要能够快速通过key找到对应的value和频率信息，因此一个 key -> (value, frequency) 的哈希表是基础。 淘汰策略涉及两个维度：频率和时间。当需要淘汰时，我们要找到频率最低的项，如果多个项频率相同，则淘汰最久未使用的（LRU规则）。 我们可以将具有相同频率的key组织成一个双向链表（类似LRU缓存中的链表），这样每个频率都对应一个链表。链表头部是最新访问的节点，尾部是最久未访问的节点。 为了快速找到最小频率对应的链表，我们需要维护一个变量 minFreq 来记录当前的最小频率。 还需要一个 frequency -> linked list 的哈希表，来通过频率快速找到对应的链表。 数据结构设计 keyToNode : 哈希表，映射key到节点（节点包含value, frequency, key）。 freqToDict : 哈希表，映射频率到一个双向链表（或OrderedDict，用于维护插入顺序）。 minFreq : 整数，记录当前最小的频率。 capacity : 整数，缓存容量。 get操作流程 如果key不存在于 keyToNode 中，返回-1。 如果key存在： a. 获取对应的节点node。 b. 从 freqToDict[node.freq] 对应的链表中移除该节点。如果移除后此链表变为空，且当前频率 node.freq 等于 minFreq ，则将 minFreq 加1。 c. 将节点的频率 node.freq 加1。 d. 将节点添加到 freqToDict[node.freq] 对应链表的头部。 e. 返回节点的value。 put操作流程 如果 capacity 为0，直接返回。 如果key已经存在： a. 更新key对应的value（过程类似get操作：先移除，频率+1，再添加到新频率链表的头部）。 如果key不存在： a. 如果缓存已满（即 len(keyToNode) == capacity ）： 找到需要淘汰的节点：在 freqToDict[minFreq] 链表的尾部（最久未使用）。 从 freqToDict[minFreq] 链表和 keyToNode 中移除该节点。 b. 创建一个新节点（key, value, frequency=1）。 c. 将新节点添加到 freqToDict[1] 链表的头部。 d. 将新节点加入 keyToNode 。 e. 将 minFreq 重置为1（因为新插入的节点频率都是1）。 关键点说明 为什么在移除节点后，如果链表为空且频率等于 minFreq ，才需要增加 minFreq ？ 因为 minFreq 表示当前存在的最小频率。如果这个频率对应的链表空了，说明缓存中已经没有频率为 minFreq 的节点了，那么最小频率自然就变成了 minFreq+1 。 为什么新插入节点后， minFreq 要设为1？ 因为新节点的频率是1，它一定是当前最小的频率。 通过以上设计，get和put操作的时间复杂度都是O(1)，因为所有操作（哈希表查找、插入、删除，链表插入、删除）都是O(1)的。