共计 8452 个字符，预计需要花费 22 分钟才能阅读完成。
你好呀，我是歪歪。
这篇文章带大家盘一下 LFU 这个玩意。
为什么忽然想起聊聊这个货色呢，因为前段时间有个读者给我扔过去一个链接：
我一看，好家伙，这不是我敬爱的老朋友，Dubbo 同学嘛。
点进去一看，就是一个对于 LFU 缓存的 BUG：
https://github.com/apache/dub…
你晓得的，我就喜爱盘一点开源我的项目的 BUG，看看有没有机会，捡捡漏什么的。在我辉煌的“捡漏”历中，已经最浓墨重彩的一笔是在 Redisson 外面，发现作者在重构代码的时候，误把某个办法的计数，从默认值为 0，改成了为 1。
这个 BUG 会间接导致 Redission 锁失去可重入的性质。我发现后，源码都没下载，间接在网页上就改回去了：
我认为这可能就是巅峰了。
然而直到我遇到了 Dubbo 的这个 LFUCache 的 BUG，它的修复计划，只是须要替换两行代码的程序就完事儿了，更加简略。
到底怎么回事呢，我带你盘一把。
首先，刚刚提到 BUG，因为这一次针对 LFU 实现的优化提交：
https://github.com/apache/dub…
通过链接咱们晓得，这次提交的目标是优化 LFUCache 这个类，使其能通过 frequency 获取到对应的 key，而后删除空缓存。
然而带了个内存泄露的 BUG 下来，那么这个 BUG 是怎么修复的呢？
间接给对应的提交给回滚掉了：
然而，回滚回来的这一份代码，我集体感觉也是有问题的，应用起来，有点不得劲。
在为你解析 Dubbo 的 LFU 实现的问题之前，我必须要先把 LFU 这个货色的思路给你盘明确了，你能力丝滑入戏。
LRU vs LFU
在说 LFU 之前，我先给简略提一句它的好兄弟：LRU，Least Recently Used，最近起码应用。
LRU 这个算法的思维就是：如果一个数据在最近一段时间没有被拜访到，那么在未来它被拜访的可能性也很小。所以，当指定的空间已存满数据时，该当把最久没有被拜访到的数据淘汰。
听形容你也晓得了，它是一种淘汰算法。
如果说 LRU 是 Easy 模式的话，那么把两头的字母从 R（Recently）变成 F（Frequently），即 LFU，那就是 hard 模式了。
如果你不意识 Frequently 没关系，毕竟这是一个英语专八的词汇。
我，英语八级半，我能够教你：
这是一个 adv，副词，是指在句子中示意行为或状态特色的词，用以润饰动词、形容词、其余副词或全句，示意工夫、地点、水平、形式等概念。
在 LFU 外面，示意的就是频率，它翻译过去就是：最不常常应用策略。
LRU 淘汰数据的时候，只看数据在缓存外面待的工夫长短这个维度。
而 LFU 在缓存满了，须要淘汰数据的时候，看的是数据的拜访次数，被拜访次数越多的，就越不容易被淘汰。
然而呢，有的数据的拜访次数可能是雷同的。
怎么解决呢？
如果拜访次数雷同，那么再思考数据在缓存外面待的工夫长短这个维度。
也就是说 LFU 算法，先看拜访次数，如果次数统一，再看缓存工夫。
给你举个具体的例子。
假如咱们的缓存容量为 3，依照下列数据程序进行拜访：
如果依照 LRU 算法进行数据淘汰，那么十次拜访的后果如下：
十次拜访完结后，缓存中剩下的是 b，c，d 这三个元素。
你认真嗦一下，你有没有感觉有一丝丝不对劲？
十次拜访中元素 a 被拜访了 5 次，阐明 a 是一个常常要用到的货色，后果依照 LRU 算法，最初元素 a 被淘汰了？
如果依照 LFU 算法，最初留在缓存中的三个元素应该是 b，c，a。
这样看来，LFU 比 LRU 更加正当，更加巴适。
好的，题目形容结束了。假如，要咱们实现一个 LFUCache：
class LFUCache {public LFUCache(int capacity) { }
public int get(int key) { }
public void put(int key, int value) {}}那么思路应该是怎么的呢？
一个双向链表
如果是我去面试，在齐全没有接触过 LFU 算法之前，面试官出了这么一道题，让我硬想，我能想到的计划也只能是上面这样的。
因为后面咱们剖析了，这个玩意既须要有频次，又须要有工夫程序。
咱们就能够搞个链表，先依照频次排序，频次一样的，再依照工夫排序。
因为这个过程中咱们须要删除节点，所以为了效率，咱们应用双向链表。
还是假如咱们的缓存容量为 3，还是用刚刚那组数据进行演示。
咱们把频次定义为 freq，那么前三次拜访完结后，即这三个申请拜访完结后：
每个元素的频次，即 freq 都是 1。所以链表外面应该是这样的：
因为咱们的容量就是 3，此时曾经满了。
那我问你一个问题：如果此时来任意一个不是 a 的元素，谁会被踢出缓存？
就这问题，你还思考个毛啊，这不是高深莫测的事件吗？
对于目前三个元素来说，value=a 是频次雷同的状况下，最久没有被拜访到的元素，所以它就是 head 节点的下一个元素，随时等着被淘汰。
然而你说巧不巧，
接着过去的申请就是 value=a：
当这个申请过去的时候，链表中的 value=a 的节点的频率（freq）就变成了 2。
此时，它的频率最高，最不应该被淘汰，a 元素实现了自我救赎！
因而，链表变成了上面这个样子，没有任何元素被淘汰了。
链表变动的局部，我用不同于红色的色彩（我色弱不晓得这是个啥色彩，蓝色吗？）标注进去：
接着间断来了三个 value=a 的申请：
此时的链表变动就集中在 value=a 这个节点的频率（freq）上。
为了让你能丝滑跟上，我把每次的 freq 变动都给你画进去。这行为，实锤了，妥妥的暖男作者：
接着，这个 b 申请过去了：
b 节点的 freq 从 1 变成了 2，节点的地位也产生了变动：
而后，c 申请过去：
这个时候就要特地留神了：
你说这个时候会产生什么事件？
链表中的 c 以后的拜访频率是 1，当这个 c 申请过去后，那么链表中的 c 的频率就会变成 2。
你说巧不巧，此时，value=b 节点的频率也是 2。
撞车了，那么你说，这个时候怎么办？
后面说了：频率一样的时候，看工夫。
value=c 的节点是正在被拜访的，所以要淘汰也应该淘汰之前被拜访的 value=b 的节点。
此时的链表，就应该是这样的：
而后，最初一个申请过去了：
d 元素，之前没有在链表外面呈现过，而此时链表的容量也满了。
那么刺激的就來了，该进行淘汰了，谁会被“优化”掉呢？
一看链表，哦，head 的下一个节点是 value=b：
而后把 value=d 的节点插入：
最终，所有申请结束。
留在缓存中的是 d，c，a 这三个元素。
最初，汇个总，整体的流程就是这样的：
当然，这里只是展现了链表的变动。
后面说了，这是缓存淘汰策略，缓存嘛，大家都懂，是一个 key-value 键值对。
所以后面的元素 a,b,c 啥的，其实对应的是咱们放的 key-value 键值对。也就是应该还有一个 HashMap 来存储 key 和链表节点的映射关系。
这个点比较简单，用脚趾头都能想到，我也就不开展来说了。
依照下面这个思路，你缓缓的写代码，应该是能写进去的。
下面这个双链表的计划，就是扣着脑壳硬想，大部分人能间接想到的计划。
然而，面试官如果真的是问这个问题的话，当你给出这个答复之后，他必定会诘问：有没有工夫复杂度为 O(1) 的解决方案呢？
双哈希表
如果咱们要拿出工夫复杂度为 O(1) 的解法，那就得细细的剖析了，不能扣着脑壳硬想了。
咱们先剖析一下需要。
第一点：咱们须要依据 key 查问其对应的 value。
后面说了，这是一个缓存淘汰策略，缓存嘛，用脚趾头都能想到，用 HashMap 存储 key-value 键值对。
查问工夫复杂度为 O(1)，满足。
第二点：每当咱们操作一个 key 的时候，不论是查问还是新增，都须要保护这个 key 的频次，记作 freq。
因为咱们须要频繁的操作 key 对应的 freq，频繁地执行把 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、value、freq 属性的 Node 对象之后，咱们的三个 HashMap 就变成了两个：
一个存储 key 和 Node 的 HashMap，即 HashMap<key,Node>
一个存储 freq 和 Node 的 HashMap，即 HashMap<freq,Node>
你捋一捋这个思路，是不是十分的清晰，有了清晰的思路，去写代码是不是就事倍功半了。
好，当初我通知你，到这一步，咱们还差一个逻辑，而且这个逻辑十分的重要，你当初先别着急往下看，先再回顾一下目前整个推理的过程和最初的思路，想一想到底还差啥？
…
…
…
…
到这一步，咱们还差了一个十分要害的信息没有补全，就是上面这一个点。
第四点：可能有多个 key 具备雷同的最小的 freq，此时移除这一批数据在缓存中待的工夫最长的那个元素。
在这个需要外面，咱们须要通过 freq 查找 Node，那么操作的就是 HashMap<freq,Node> 这个哈希表。
下面说 [多个 key 具备雷同的最小的 freq]，也就是说通过 minFreq，是能够查问到多个 Node 的。
所以 HashMap<freq,Node> 这个哈希表，应该是这样的：HashMap<freq, 汇合 <Node>>。
这个能想明确吧？
一个坑位下，挂了一串节点。
此时的问题就变成了： 咱们应该用什么汇合来装这个 Node 对象呢？
不慌，咱们又接着剖析嘛。
先理一下这个汇合须要满足什么条件。
咱们通过 minFreq 获取这个汇合的时候，也就是队列满了，要从这个汇合中删除数据的时候
首先，须要删除 Node 的时候。
因为这个汇合外面装的是拜访频次一样的数据，那么心愿这批数据能有时序，这样能够疾速的删除待的工夫最久的 Node。
有序，有时序，能疾速查找删除待的工夫最久的 key。
LinkedList，双向链表，能够满足这个需要吧？
另外还有一种大多数状况是一个 Node 被拜访的时候，它的频次必然就会加一。
所以还要思考拜访 Node 的时候。
比方上面这个例子：
假如最小拜访频次，minFreq=5，而 5 这个坑位对应了 3 个 Node 对象。
此时，我要拜访 value=b 的对象，那么该对象就会从 minFreq=5 的 value 中移走。
而后频次加一，即 5+1=6。
退出到 minFreq=6 的 value 汇合中，变成上面这个样子：
也就是说咱们得反对任意 node 的疾速删除。
LinkedList 不反对任意 node 的疾速删除，这玩意须要遍历啊。
当然，你能够本人去手撸一个符合要求的 MySelfLinkedList。
然而，在 Java 汇合类中，其实有一个满足下面说的有序的、反对疾速删除的汇合。
那就是 LinkedHashSet，它是一个基于 LinkedHashMap 实现的有序的、去重汇合列表。
底层还是一个 Map，Map 针对指定元素的删除，O(1)。
所以，HashMap<freq, 汇合 >，就是 HashMap<freq,LinkedHashSet>。
总结一下。
咱们须要两个 HashMap，别离是
- HashMap<key,Node>
- HashMap<freq,LinkedHashSet<Node>>
而后还须要保护一个最小拜访频次，minFreq。
哦，对了，还得来一个参数记录缓存反对的最大容量，capacity。
而后，没了。
有的小伙伴必定要问了：你倒是给我一份代码啊？
这些剖析进去了，代码本人缓缓就撸进去了，这一份代码应该就是绝大部分面试官问 LFU 的时候，想要看到的代码了。
另外，对于 LFU 呈现在面试环节，我忽然想起一个段子，我感觉还有一丝情理：
面试官想要，我会出个两数之和，如果我不想要你，我就让你写 LFU。
我这里次要带大家梳理思路，思路清晰后再去写代码，就算面试的时候没有写出 bug free 的代码，也基本上八九不离十了。
所以具体的代码实现，我这里就不提供了，网上一搜多的很，要害是把思路弄清楚。
这玩意就像是你工作，要害的是把需要梳理明确，而后想想代码大略是怎么样的。
至于具体去写的时候，到处粘一粘，也不是不能够。再或者，把设计文档写进去了，代码落地就让小弟们照着你的思路去干就行了。
应该把工作精力放在更值得破费的中央：比方 battle 需要、写文档、写周报、写 PPT、舔领导啥的 …
Dubbo 的 LFU
到这里，你应该是懂了 LFU 到底是个啥玩意了。
当初我带你看看 Dubbo 外面的这个 LFU，它的实现计划并没有采取咱们后面剖析进去的计划。
它另辟蹊径，搞了一个新花样进去。它是怎么实现的呢？我给你盘一下。
Dubbo 是在 2.7.7 版本之后反对的 LFU，所以如果你要在本地测试一把的话，须要引入这个版本之后的 Maven 依赖。
我这里间接是把 Dubbo 源码拉下来，而后看的是 Master 分支的代码。
首先看一下它的数据结构：
它有一个 Map，是寄存的 key 和 Node 之间的映射关系。而后还有一个 freqTable 字段，它的数据结构是数组，咱们并没有看到一个叫做 minFreq 的字段。
当我的 LFUCache 这样定义的时候：
new LFUCache<>(5, 0.2f);
含意是这个缓存容量是 5，当满了之后，“优化”5*0.2 个对象，即从缓存中踢出 1 个对象。
通过 Debug 模式看，它的构造是这样的：
咱们先次要关注 freqTable 字段。
在上面标号为 ① 的中央，示意它是一个长度为 capacity+1 的数组，即长度为 6，且每个地位都 new 了一个 CacheDeque 对象。
标号为 ② 的中央，实现了一个单向链表的保护动作：
freqTable 具体拿来是干啥用的呢？
用上面这三行代码举个例子：
cache.put("why", 18);
cache.get("why");
cache.get("why");当第一行执行实现之后，why 这个元素被放到了 freqTable 的第一个坑位，即数组的 index=0 外面：
当第二行执行实现之后，why 这个元素被放到了 freqTable 的第二个坑位外面：
当第三行执行实现之后，why 这个元素被放到了 freqTable 的第三个坑位外面：
有没有点感觉了？
freqTable 这个数组，每个坑位就是对应不同的频次，所以，我给你搞个图：
比方 index=3 地位放的 d 和 c，含意就是 d 和 c 在缓存外面被拜访的频次是 4 次。
然而，d 和 c 谁待的工夫更长呢？
我也不晓得，所以得看看源码外面删除元素的时候，是移走 last 还是 first，移走谁，谁就在这个频率下待的工夫最长。
答案就藏在它的驱赶办法外面：
org.apache.dubbo.common.utils.LFUCache#proceedEviction
从数组的第一个坑位开始遍历数组，如果这个坑位下挂的有链表，而后开始一直的移除头结点，直到驱赶指定个数的元素。
移除头结点，所以，d 是在这个频次中待的工夫最长的。
基于这个图片，假如当初队列满了，那么接下来，必定是要把 why 这个节点给“优化”了：
这就是 Dubbo 外面 LFU 实现的最外围的思维，很奇妙啊，基于数组的程序，来示意元素被拜访的频次。
然而，细细的嗦一下滋味之后，你有没有想过这样一个问题，当我拜访缓存中的元素的次数大于 freqTable 数组的长度的时候，会呈现什么神奇的景象？
我还是给你用代码示意:
尽管 mx 元素的拜访次数比 why 元素的次数多得多，然而这两个元素最初都落在了 freqTable 数组的最初一个坑位中。
也就是会呈现这样的场景：
好，我问你一个问题：假如，在这样的状况下，要淘汰元素了，谁会被淘汰？
必定是依照头结点的程序开始淘汰，也就是 why 这个节点。
接下来留神了，我再问一个问题：假如此时 why 有幸再次被拜访了一下，而后才来一个新的元素，触发了淘汰策略，谁会被淘汰？
why 会变成这个坑位下的链表中的 last 节点，从而规避过下一次淘汰。mx 元素被淘汰了。
这玩意忽然就从 LFU，变成了一个 LRU。在同一个实现外面，既有 LFU 又有 LRU，这玩意，常识都学杂了啊。
我就问你 6 不 6？
所以，这就是 Dubbo 的 LFU 算法实现的一个弊病，这个弊病是因为它的设计理念和数据结构决定的，如果想要防止这个问题，我感觉有点麻烦，得颠覆素来。
所以我这里也只是给你形容一下有这个问题的存在。
而后，对于 Dubbo 的 LFU 的实现，还有另外一个神奇的货色，我感觉这纯纯的就是 BUG 了。
我还是给你搞一个测试用例：
@Test
void testPutAndGet() {LFUCache<String, Integer> cache = new LFUCache<>(5, 0.2f);
for (int i = 0; i < 5; i++) {cache.put(i + "", i);
cache.get(i + "");
}
cache.put("why", 18);
Integer why = cache.get("why");
System.out.println("why =" + why);
}一个容量为 5 的 LFUCache，我先放五个元素进去，每个元素 put 之后再 get 一下，所以每个元素的频率变成了 2。
而后，此时我放了一个 why 进去，而后在取出来的时候，why 没了。
你这啥缓存啊，我刚刚放进去的货色，等着马上就要用呢，后果获取的时候没了，这不是 BUG 是啥？
问题就出在它的 put 办法中：
标号为 ① 的中央往缓存外面放，搁置结束之后，判断是否会触发淘汰机制，而后在标号 ② 的中央删除元素。
后面说了，淘汰策略，proceedEviction 办法，是从 freqTable 数组的第一个坑位开始遍历数组，如果这个坑位下挂的有链表，而后开始一直的移除头结点，直到驱赶指定个数的元素。
所以，在刚刚我的示例代码中，why 元素刚刚放进去，它的频率是 1，放在了 freqTable 数组的第 0 个地位。
放完之后，一看，触发淘汰机制了，让 proceedEviction 办法看看是谁应该被淘汰了。
你说，这不是赶巧了嘛，间接又把 why 给淘汰了，因为它的拜访频率最低。
所以，立马去获取“why”的时候，获取不到。
这个中央的逻辑就是有问题的。
不应该采取“先放新元素，再判断容量，如果满了，触发淘汰机制”的实现计划。
而应该采取“先判断容量，如果满了，再触发淘汰机制，最初再放新元素的”计划。
也就是我须要把这两行代码换个地位：
再次执行测试案例，就没有问题了：
诶，你说这是什么？
这不就是为开源我的项目奉献源码的好机会吗？
于是 …
https://github.com/apache/dub…
对于提 pr，有一个小细节，我悄悄的通知你：合不合并什么的不重要，重要的是全英文发问，哪怕是中文一键翻译过去的，也要贴上去，逼格要拉满，品位要下来 …
至于最初，如果没合并，阐明我考虑不周，又是新的素材。
如果合并了，简历上又能够写：纯熟应用 Dubbo，并为其奉献过源码。
到时候，我脸皮再厚一点，还能够写成：浏览过 Apache 顶级开源我的项目源码，屡次为其奉献过外围源码，并写过系列博文，加深学习印象 …
不能再说了，剩下的就靠本人悟了！
最初，文章就到这里了，如果对你有一丝丝的帮忙， 帮我点个收费的赞 ，不过分吧？
