你说这个时候会发生什么事情？
链表中的 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 被访问，那么它的频次必然就会加一。
