如何动手撸一个简单的LFU缓存

前面的文章已经介绍过，关于缓存置换算法的来由和理论知识，如果还没了解的同学，可点击下面的链接进行查看：

什么是缓存置换算法?

什么是操作系统的虚拟内存？

今天我们来看下，如何用代码来实现一个简单的LFU缓存。

我们知道缓存置换算法主流的有三种，分别是：

(1) FIFO：First In First Out，先进先出策略

(2) LFU：Least Frequently Used，最不经常使用策略

(3) LRU：Least Recently Used，最近最少使用策略

关于第一种FIFO策略的实现，比较简单，可采用固定长度的数组和链表来处理，这里就不重点说了。今天我们的重点是LFU缓存的实现。

LFU 全称 Least Frequently Used，从名字上我们就能看出来这个算法是基于数据访问频率（次数）来淘汰数据的，也就是说系统会记录一段时间内所有数据的访问次数，当缓存区满的时候，会优先淘汰访问次数最少的数据。其核心思想：如果一个数据在最近一段时间内访问次数很少，则在将来一段时间内被访问的可能性也很小。显然，这是一种合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。缓存的每个数据都有引用计数，所有数据按照引用计数排序，具有相同引用计数的数据按照时间排序。

我们来看下LFU缓存算法的实现代码：

（友情提示：代码块可左右滑动）

代码并不复杂，为了方便大家观察到细节，我特意在代码里面加了相关log输出，下面我们来测试这个缓存算法：

完整代码，请访问我的github：https://github.com/qindongliang/Java-Note/blob/master/src/main/java/algorithm/cache_algorithm/LFUCache.java

运行上面的代码，我们的控制台输出信息如下：

可以看到结果是没问题的，在上面的测试中，我们设置缓存的容量大小为3，然后先添加了两条数据1，2，然后接着分别对1和2进行了查询，注意这个时候1和2的引用计数会增加2，并且他们的时间也会更新，接着我们添加了3和4，注意在添加4的时候由于缓存容量已经满了，为了能让4添加进来，我们必须根据淘汰一条数据，那么这个淘汰数据应该是谁呢？毫无疑问就是3了，因为3的访问次数最少。注意如果这里3的次数也是2，那么算法会根据时间选择一条时间最早的数据，这个时候淘汰的数据就是1了，最后我们访问了一条不存在的数据5，并且对同一个key=4的数据，删除了2次，可以看到结果也是没有问题的。

该算法的时间复杂度最坏的情况为O（N），原因在于在淘汰数据的时候，我们偷了个懒，用的是Collections.min方法，这个函数内部会迭代整个values里面的数据来找到需要被淘汰的数据，当数据量大的时候性能不会太好，所以在这个地方，我们可以使用堆这种数据结构来优化性能，从而让时间复杂度降至O（logN），如果是在Java里面，我们可以直接借助优先级队列（底层结构堆）来实现，并提供相关的自定义排序策略。

本文主要介绍了LFU缓存算法的简单实现和复杂度分析，LFU算法可以避免偶发性的、周期性的批量操作会导致LRU算法命中率急剧下降，缓存污染情况比较严重的问题。但其缺点也很明显，面对一段时间内热点数据，其效果没有LRU好，LFU在存在大量的历史数据的高频访问时，如果此时新来了很多访问频次略低于历史数据的时候，新的热点数据由于频次略低，在容量有限的时候很有可能就被淘汰了，从而造成缓存miss，此外从实现的复杂度上来分析，LFU 需要维护一个队列记录所有数据的访问记录，每个数据都要维护引用计数，内存消耗和性能消耗都较高。LFU整体上在空间和时间复杂度上均高于LRU算法，这也是为什么LRU算法更受欢迎的原因，在下篇文章我们会重点介绍下如何实现一个LRU缓存。