比如下面这个例子：

假设最小访问频次就是 5，而 5 对应了 3 个 Node 对象。

此时，我要访问 value=b 的对象，那么该对象就会从 key=5 的 value 中移走。

然后频次加一，即 5+1=6。

加入到 key=6 的 value 集合中，变成下面这个样子：

也就是说我们得支持任意 node 的快速删除。

我们可以针对上面的需求，自定义一个双向链表。

但是在 Java 集合类中，有一个满足上面说的有序且支持快速删除的条件的集合。

那就是 LinkedHashSet。

所以，HashMap<freq,集合>，就是HashMap<freq,LinkedHashSet>。

总结一下。

我们需要两个 HashMap，分别是 HashMap<key,Node> 和 HashMap<freq,LinkedHashSet>。

然后还需要维护一个最小访问频次，minFreq。

哦，对了，还得来一个参数记录缓存支持的最大容量，capacity。

没了。

有的小伙伴肯定要问了：你倒是给我一份代码啊？

这些分析出来了，代码自己慢慢就撸出来了。

思路清晰后再去写代码，就算面试的时候没有写出 bug free 的代码，也基本上八九不离十了。

Dubbo 中的 LFU 算法

Dubbo 在 2.7.7 版本之后支持了 LFU 算法：

其源码的位置是：org.apache.dubbo.common.utils.LFUCache

代码不长，总共就 200 多行，和我们上面说的 LFU 实现起来还有点不一样。

你可以看到它甚至没有维护 minFreq。

但是这些都不重要，打个断点调试一下很快就能分析出来作者的代码思路。

重要的是，我在看 Dubbo 的 LFU 算法的时候发现了一个 bug。

不是指这个 LFU 算法实现上的 bug，算法实现我看了是没有问题的。

bug 是 Dubbo 虽然加入了 LFU 缓存算法的实现，但是作为使用者，却不能使用。

问题出在哪里呢？

我带你瞅一眼。

源码里面告诉我这样配置一下就可以使用 lfu 的缓存策略：

但是，当我这样配置，发起调用之后，是这样的：

可以看到当前请求的缓存策略确实是 lfu。

但是会抛出一个错误：

No such extension org.apache.dubbo.cache.CacheFactory by name lfu

没有 lfu 这个策略。

这不是玩我吗？

再看一下具体的原因。

在org.apache.dubbo.common.extension.ExtensionLoader#getExtensionClasses处只获取到了 4 个缓存策略，并没有我们想要的 LFU:

所以，在这里抛出了异常：

为什么没有找到我们想要的 LFU 呢？

那就的看你熟不熟悉 SPI 了。

在 SPI 文件中，确实没有 lfu 的配置：

这就是 bug。

所以怎么解决呢？

非常简单，加上就完事了。

害，一不小心又给 Dubbo 贡献了一行源码。

最后说一句（求关注）

才疏学浅，难免会有纰漏，如果你发现了错误的地方，可以在后台提出来，我对其加以修改。

感谢您的阅读，我坚持原创，十分欢迎并感谢您的关注。

我是 why，一个主要写代码，经常写文章，偶尔拍视频的程序猿。