让人抠脑壳的 LFU

前几天在某APP看到了这样的一个讨论：

看到一个有点意思的评论：

LFU 是真的难，脑壳都给我抠疼了。

如果说 LRU 是 Easy 模式的话，那么把中间的字母从 R（Recently） 变成 F（Frequently），即 LFU ，那就是 hard 模式了。

你不认识 Frequently 没关系，毕竟这是一个英语专八的词汇，我这个英语八级半的选手教你：

所以 LFU 的全称是Least Frequently Used，最不经常使用策略。

很明显，强调的是使用频率。

而 LRU 算法的全称是Least Recently Used。最近最少使用算法。

强调的是时间。

当统计的维度从时间变成了频率之后，在算法实现上发生了什么变化呢？

这个问题先按下不表，我先和之前写过的 LRU 算法进行一个对比。

LRU vs LFU

LRU 算法的思想是如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以，当指定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

也就是淘汰数据的时候，只看数据在缓存里面待的时间长短这个维度。

而 LFU 在缓存满了，需要淘汰数据的时候，看的是数据的访问次数，被访问次数越多的，就越不容易被淘汰。

但是呢，有的数据的访问次数可能是相同的。

怎么处理呢？

如果访问次数相同，那么再考虑数据在缓存里面待的时间长短这个维度。

也就是说 LFU 算法，先看访问次数，如果次数一致，再看缓存时间。

给大家举个具体的例子。

假设我们的缓存容量为 3，按照下列数据顺序进行访问：

如果按照 LRU 算法进行数据淘汰，那么十次访问的结果如下

十次访问结束后，缓存中剩下的是 b，c，d 这三个元素。

你有没有觉得有一丝丝不对劲？

十次访问中元素 a 被访问了 5 次，结果最后元素 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 方案一 - 一个双向链表

如果在完全没有接触过 LFU 算法之前，让我硬想，我能想到的方案也只能是下面这样的：

因为既需要有频次，又需要有时间顺序。

我们就可以搞个链表，先按照频次排序，频次一样的，再按照时间排序。

因为这个过程中我们需要删除节点，所以为了效率，我们使用双向链表。

还是假设我们的缓存容量为 3，还是用刚刚那组数据进行演示。

我们把频次定义为 freq，那么前三次访问结束后，即这三个请求访问结束后：

三个元素的访问频次都是 1。

对于前三个元素来说，value=a 是频次相同的情况下，最久没有被访问到的元素，所以它就是 head 节点的下一个元素，随时等着被淘汰。

接着过来了 1 个 value=a 的请求：

当这个请求过来的时候，链表中的 value=a 的节点的频率（freq）就变成了2。

此时，它的频率最高，最不应该被淘汰。

因此，链表变成了下面这个样子：

接着连续来了 3 个 value=a 的请求：

此时的链表变化就集中在 value=a 这个节点的频率（freq）上：