你说这个时候会发生什么事情？

链表中的 c 当前的访问频率是 1，当这个 c 请求过来后，那么链表中的 c 的频率就会变成 2。

你说巧不巧，此时，value=b 节点的频率也是 2。

撞车了，那么你说，这个时候怎么办？

前面说了：频率一样的时候，看时间。

value=c 的节点是正在被访问的，所以要淘汰也应该淘汰之前被访问的 value=b 的节点。

此时的链表，就应该是这样的：

d 元素，之前没有在链表里面出现过，而此时链表的容量也满了。

该进行淘汰了。

于是把 head 的下一个节点（value=b）淘汰，并把 value=d 的节点插入：

最终，所有请求完毕。

留在缓存中的是 d，c，a 这三个元素。

整体的流程就是这样的：

当然，这里只是展示了链表的变化。

其实我们放的是 key-value 键值对。

所以应该还有一个 HashMap 来存储 key 和链表节点的映射关系。

这个简单，用脚趾头都能想到，我也就不展开来说了。

按照上面这个思路，你慢慢的写代码，应该是能写出来的。

上面这个双链表的方案，就是扣着脑壳硬想，大部分人能直接想到的方案。

面试官要的肯定是时间复杂度为 O(1) 的解决方案。

现在的这个解决方案时间复杂度为 O(N)。

O(1) 解法

如果我们要拿出时间复杂度为 O(1) 的解法，我们就得细细的分析了，不能扣着脑壳硬想了。

先分析一下需求。

第一点：我们需要根据 key 查询其对应的 value。

用脚趾头都能想到，用 HashMap 存储 key-value 键值对。

查询时间复杂度为 O(1)，满足。

第二点：每当我们操作一个 key 的时候，不论是查询还是新增，都需要维护这个 key 的频次，记作 freq。

因为我们需要频繁的操作 key 对应的 freq，也就是得在时间复杂度为 O(1) 的情况下，获取到指定 key 的 freq。

来，请你大声的告诉我，用什么数据结构？

是不是还得再来一个 HashMap 存储 key 和 freq 的对应关系？

第三点：如果缓存里面放不下了，需要淘汰数据的时候，把 freq 最小的 key 删除掉。

注意啊，上面这句话：[把 freq 最小的 key 删除掉]。

freq 最小？

我们怎么知道哪个 key 的 freq 最小呢？

前面说了，有一个 HashMap 存储 key 和 freq 的对应关系。

当然我们可以遍历这个 HashMap，来获取到 freq 最小的 key。

但是啊，朋友们，遍历出现了，那么时间复杂度还会是 O(1) 吗？

那怎么办呢？

注意啊，高潮来了，一学就废，一点就破。

我们可以搞个变量来记录这个最小的 freq 啊，记为 minFreq，不就行了？

现在我们有最小频次（minFreq）了，需要获取到这个最小频次对应的 key，时间复杂度得为 O(1)。

来，朋友，请你大声的告诉我，你又想起了什么数据结构？

是不是又想到了 HashMap？

好了，我们现在有三个 HashMap 了，给大家介绍一下：

• 一个存储 key 和 value 的 HashMap，即HashMap<key,value>。
• 一个存储 key 和 freq 的 HashMap，即HashMap<key,freq>。
• 一个存储 freq 和 key 的 HashMap，即HashMap<freq,key>。

它们每个都是各司其职，目的都是为了时间复杂度为 O(1)。

但是我们可以把前两个 HashMap 合并一下。

我们弄一个对象，对象里面包含两个属性分别是value、freq。

假设这个对象叫做 Node，它就是这样的，频次默认为 1：

class Node {
    int value;
    int freq = 1;
    //构造函数省略
}

那么现在我们就可以把前面两个 HashMap ，替换为一个了，即 HashMap<key,Node>。

同理，我们可以在 Node 里面再加入一个 key 属性：

class Node {
    int key;
    int value;
    int freq = 1;
    //构造函数省略
}

因为 Node 里面包含了 key，所以可以把第三个 HashMap<freq,key> 替换为 HashMap<freq,Node>。

到这一步，我们还差了一个非常关键的信息没有补全，就是下面这一个点。

第四点：可能有多个 key 具有相同的最小的 freq，此时移除这一批数据在缓存中待的时间最长的那个元素。

这个需求，我们需要通过 freq 查找 Node，那么操作的就是 HashMap<freq,Node> 这个哈希表。

上面说[多个 key 具有相同的最小的 freq]，也就是说通过 minFreq ，是可以查询到多个 Node 的。

所以HashMap<freq,Node> 这个哈希表，应该是这样的：

HashMap<freq,集合>。

此时的问题就变成了：我们应该用什么集合来装这个 Node 对象呢？

不慌，我们先理一下这个集合需要满足什么条件。

首先，需要删除 Node 的时候。

因为这个集合里面装的是访问频次一样的数据，那么希望这批数据能有时序，这样可以快速的删除待的时间最久的 Node。

有时序，能快速查找删除待的时间最久的 key，你能想到什么数据结构？

这不就是双向链表吗？

然后，需要访问 Node 的时候。

一个 Node 被访问，那么它的频次必然就会加一。