前言
在设计和优化数据结构时，缓存策略是提升系统性能的关键一环。今天，让我们一起来深入探讨一种非常经典的缓存淘汰算法——LFU (Least Frequently Used，最不经常使用) 缓存。
LFU 缓存的核心思想是：当缓存容量已满，需要腾出空间给新数据时，我们应该淘汰那些访问频率最低的数据块。这意味着，在 LFU 算法中，我们不仅关注数据是否被使用过（即频率），还会考虑它最近一次被访问的时间（即时间戳）。
具体来说，如果一个页面的访问频率高于其他页面，它是不能被轻易淘汰的。但是，如果多个页面的访问频率相同，我们就面临一个选择：这时，我们会淘汰那个最久没有被使用过的页面（即 LRU，Least Recently Used 页面）。这种在同频情况下的选择，通常是通过 FIFO (First-In-First-Out，先进先出) 的方式来处理的，也就是说，在频率相同的页面中，最早进入缓存（或最久未访问）的那个将被移除。
为了实现这样一个高效的数据结构，我们需要支持以下两个核心操作：
- INLINECODE13e23178: 初始化 LFU 缓存，设定一个正整数容量 INLINECODE2e81d35e。
- INLINECODE83941ed9: 如果缓存中存在该 INLINECODE9db5c9fd，则返回对应的
value；否则返回 -1。 put(key, value): 插入或更新缓存中的键值对。如果在插入时缓存已达到容量上限，我们需要在添加新项之前，淘汰访问频率最低的项。如果有多个项拥有相同的最低频率，则淘汰它们中最久未使用的那个（LRU）。
示例
为了让大家更直观地理解，让我们来看一个具体的操作流程。
> 输入: [LFUCache cache = new LFUCache(2), put(1, 1) , put(2, 2) , get(1) , put(3, 3) , get(2), put(4, 4), get(3) , get(4), put(5, 5)]
> 输出: [1 , -1, -1, 4]
> 解释: 输出中的数值是 get 操作的返回值。
>
> – 初始化 LFUCache 类，容量设为 2。
> – INLINECODEd2cb466c: 插入键值对 INLINECODE2ecffaaf。
> – INLINECODE02138439: 插入键值对 INLINECODE5a327695。此时缓存包含 INLINECODEcf5fc79b 和 INLINECODE0e26f694。
> – cache.get(1): 获取 key 1 的值，返回 1。访问后，key 1 的频率增加为 2。
> – INLINECODE548bc52e: 此时缓存已满（容量为 2）。为了插入新的 INLINECODE8c2fbbea，必须淘汰频率最低的项。key 2 的频率为 1，而 key 1 的频率为 2。因此，key 2（最久未被访问的低频项）被淘汰，插入 (3, 3)，其初始频率为 1。
> – cache.get(2): 返回 -1，因为 key 2 已经被移除了。
> – INLINECODE016f974e: 此时缓存中有 key 1 (频率 2) 和 key 3 (频率 1)。因为 key 3 频率最低，所以淘汰 key 3，插入 INLINECODE6961c6a9，频率为 1。
> – cache.get(3): 返回 -1 (key 3 未找到)。
> – cache.get(4): 获取 key 4 的值，返回 4。访问后，key 4 的频率增加为 2。
> – INLINECODE6646119e: 此时缓存中有 key 1 (频率 2) 和 key 4 (频率 2)。两者的频率相同，发生“平局”。根据规则，我们需要淘汰最久未使用的那个。key 1 比 key 4 更早被存入（或更久未被访问），因此 key 1 被淘汰，插入 INLINECODE17cb2f78，频率为 1。
接下来，我们将探讨几种不同的实现方法，从简单的朴素解法到最优的解法。
目录
- [朴素方法 – 1] 使用节点数组
- [朴素方法 – 2] 使用单链表
- [期望方法] 使用双向链表和哈希
[朴素方法 – 1] 使用节点数组
首先，让我们尝试最直观的方法：使用一个数组来存储节点。在这个方案中，每个节点不仅仅存储 INLINECODEdc929049 和 INLINECODE4779c6ee，还需要额外存储两个重要的元数据：访问频率 和 时间戳。
> 这种方法的主要逻辑是基于线性搜索。由于数组在查找和删除时的特性，我们的 INLINECODEc742392c 和 INLINECODEc23340b4 操作的时间复杂度都会比较高。数组的大小将被设定为缓存的容量上限。
>
> – put(int key, int value)
> – 如果缓存已满，我们需要遍历数组，找到频率最低的节点。如果有多个节点频率相同且均为最低，则根据时间戳找到最久未使用的那个，并用新的 key 和 value 替换它。
> – 如果缓存未满，直接将新节点添加到数组末尾，记录当前插入时间戳，并将初始频率设为 1。
> – 时间复杂度: O(n) (因为我们需要遍历寻找频率最低的节点)。
> – get(int key)
> – 遍历数组寻找匹配的 key。
> – 如果找到了，更新它的时间戳（表示最近被访问过）并将频率加 1，然后返回 value。如果没找到，返回 -1。
> – 时间复杂度: O(n) (因为我们需要检查每一个节点)。
我们初始化一个与缓存容量大小相等的数组。这里，每个数据元素都存储了额外的信息：访问时间戳 和 频率。
- 时间戳：记录了该数据被存储或最后被访问的时间。
- 频率：记录了该数据被访问的总次数。
我们将利用 频率 来找到最不经常使用 (LFU) 的元素，而当多个元素的频率相同时，则利用 时间戳 来打破平局，找出最久未使用 (LRU) 的元素。
下面是使用 C++ 实现的代码示例：
C++
// C++ Program to implement LFU Cache
// using array
#include
using na…