LFU 的全称是Least Frequently Used，最不经常使用策略。
很明显，强调的是使用频率。
而 LRU 算法的全称是Least Recently Used。最近最少使用算法。
强调的是时间。
当统计的维度从时间变成了频率之后，在算法实现上发生了什么变化呢？
这个问题先按下不表，我先和之前写过的 LRU 算法进行一个对比。
LRU vs LFU
LRU 算法的思想是如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以，当指定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
也就是淘汰数据的时候，只看数据在缓存里面待的时间长短这个维度。
而 LFU 在缓存满了，需要淘汰数据的时候，看的是数据的访问次数，被访问次数越多的，就越不容易被淘汰。
但是呢，有的数据的访问次数可能是相同的。
怎么处理呢？
如果访问次数相同，那么再考虑数据在缓存里面待的时间长短这个维度。
也就是说 LFU 算法，先看访问次数，如果次数一致，再看缓存时间。
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 的时候。
因为这个集合里面装的是访问频次一样的数据，那么希望这批数据能有时序，这样可以快速的删除待的时间最久的 Node。
有时序，能快速查找删除待的时间最久的 key，你能想到什么数据结构？
这不就是双向链表吗？
然后，需要访问 Node 的时候。
一个 Node 被访问，那么它的频次必然就会加一。
比如下面这个例子：
假设最小访问频次就是 5，而 5 对应了 3 个 Node 对象。
此时，我要访问 value=b 的对象，那么该对象就会从 key=5 的 value 中移走。
然后频次加一，即 5+1=6。
加入到 key=6 的 value 集合中，变成下面这个样子：
也就是说我们得支持任意 node 的快速删除。
我们可以针对上面的需求，自定义一个双向链表。
但是在 Java 集合类中，有一个满足上面说的有序且支持快速删除的条件的集合。
那就是 LinkedHashSet。
所以，HashMap<freq,集合
总结一下。
我们需要两个 HashMap，分别是 HashMap<key,Node> 和 HashMap<freq,LinkedHashSet<Node>
然后还需要维护一个最小访问频次，minFreq。
哦，对了，还得来一个参数记录缓存支持的最大容量，capacity。
没了。
这些分析出来了，代码自己慢慢就撸出来了。
我这里主要带大家梳理思路。
思路清晰后再去写代码，就算面试的时候没有写出 bug free 的代码，也基本上八九不离十了。
Dubbo 中的 LFU
Dubbo 在 2.7.7 版本之后支持了 LFU 算法：
其源码的位置是：org.apache.dubbo.common.utils.LFUCache
代码不长，总共就 200 多行，和我们上面说的 LFU 实现起来还有点不一样。
你可以看到它甚至没有维护 minFreq。
转自：
