你好呀，我是歪歪。
这篇文章带咱们盘一下 LFU 这个玩意。
为什么忽然想起聊聊这个东西呢，由于前段时刻有个读者给我扔过来一个链接：
我一看，好家伙，这不是我亲爱的老朋友，Dubbo 同学嘛。
点进去一看，便是一个关于 LFU 缓存的 BUG：
github.com/apache/dubb…
你知道的，我就喜欢盘一点开源项意图 BUG，看看有没有时机，捡捡漏什么的。在我辉煌的“捡漏”历中，从前最浓墨重彩的一笔是在 Redisson 里边，发现作者在重构代码的时分，误把某个办法的计数，从默认值为 0，改成了为 1。
这个 BUG 会直接导致 Redission 锁失去可重入的性质。我发现后，源码都没下载，直接在网页上就改回去了：
我以为这或许便是巅峰了。
可是直到我遇到了 Dubbo 的这个 LFUCache 的 BUG，它的修复计划，仅仅需求交换两行代码的次序就完事儿了，愈加简略。
到底怎样回事呢，我带你盘一把。
首要，刚刚说到 BUG，由于这一次针对 LFU 完成的优化提交：
github.com/apache/dubb…
经过链接咱们知道，这次提交的意图是优化 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：
classLFUCache{
publicLFUCache(intcapacity){
}
publicintget(intkey){
}
publicvoidput(intkey,intvalue){
}
}
那么思路应该是怎样的呢？
一个双向链表
假如是我去面试，在彻底没有触摸过 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：
classNode{
intvalue;
intfreq=1;
//结构函数省掉
}
那么现在咱们就能够把前面两个 HashMap ，替换为一个了，即 HashMap<key,Node>。
同理，咱们能够在 Node 里边再加入一个 key 特点：
classNode{
intkey;
intvalue;
intfreq=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 目标呢？
不慌，咱们又接着剖析嘛。
先理一下这个调集需求满意什么条件。
咱们经过 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>
然后还需求保护一个最小拜访频次，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
voidtestPutAndGet(){
LFUCache<String,Integer>cache=newLFUCache<>(5,0.2f);
for(inti=0;i<5;i++){
cache.put(i+"",i);
cache.get(i+"");
}
cache.put("why",18);
Integerwhy=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” 的时分，获取不到。
这个当地的逻辑便是有问题的。
不应该采纳“先放新元素，再判别容量，假如满了，触发筛选机制”的完成计划。
而应该采纳“先判别容量，假如满了，再触发筛选机制，最终再放新元素的”计划。
也便是我需求把这两行代码换个方位：
再次履行测验案例，就没有问题了：
诶，你说这是什么？
这不便是为开源项目贡献源码的好时机吗？
所以…
github.com/apache/dubb…
关于提 pr，有一个小细节，我悄悄的告诉你：合不兼并什么的不重要，重要的是全英文提问，哪怕是中文一键翻译过来的，也要贴上去，逼格要拉满，档次要上去…
至于最终，假如没兼并，阐明我考虑不周，又是新的素材。
假如兼并了，简历上又能够写：熟练运用 Dubbo，并为其贡献过源码。
到时分，我脸皮再厚一点，还能够写成：阅读过 Apache 顶级开源项目源码，屡次为其贡献过中心源码，并写过系列博文，加深学习印象…
不能再说了，剩余的就靠自己悟了！
最终，文章就到这儿了，假如对你有一丝丝的帮助，帮我点个免费的赞，不过分吧？
