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。
转自: