如何动手撸一个简单的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缓存算法的实现代码：
package algorithm.cache_algorithm;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
/****
* 实现一个 LFU 缓存
* Least Frequently Used，最不经常使用策略
*/
public class LFUCache {
private int capacity;//缓存队列的容量值
private Map<Integer,AccessRate> cache;//保存缓存数据
public LFUCache(int capacity) {
this.capacity = capacity;
cache=new HashMap<>();
}
public void put(int key,int value){
AccessRate v=cache.get(key);
if(v==null){//第一次插入
if(cache.size()==capacity){//容量已超
cache.remove(getEvictKey());//驱逐被淘汰的数据
}
//新增
v=new AccessRate(key,value,1,System.nanoTime());
cache.put(key,v);
log("add",v);
}else{
//更新状态
v.value=value;
v.hitCount=v.hitCount+1;
v.lastTime=System.nanoTime();
cache.put(key,v);
log("update",v);
}
}
public int get(int key){
AccessRate v=cache.get(key);
if(v!=null){
v.hitCount=v.hitCount+1;
v.lastTime=System.nanoTime();
log("query",v);
return v.value;
}
log("query",new AccessRate(key));
return -1;
}
public void remove(int key){
AccessRate v=cache.remove(key);
if(v!=null){
log("remove",v);
}else{
log("remove",new AccessRate(key));
}
}
//记录操作明细，方便理解
public void log(String operator,AccessRate accessRate){
if(accessRate.isNotNull()){
System.out.println(operator+" => "+accessRate.toString()+" "+deatail());
}else {
System.out.println(operator+" => the key "+accessRate.key+" not exist"+" "+deatail());
}
}
public String deatail(){
StringBuilder sb=new StringBuilder();
sb.append("当前缓存中有效的key=");
for (AccessRate accessRate:cache.values()){
sb.append(accessRate.key+"，");
}
return sb.deleteCharAt(sb.length()-1).toString();
}
//获取缓存里面，需要被淘汰的数据，复杂度O（N），可用优先级队列（堆）进行优化
public Integer getEvictKey(){
AccessRate min= Collections.min(cache.values());
log("evict",min);
return min.key;
}
class AccessRate implements Comparable<AccessRate> {
private Integer key;//访问的数据key
private Integer value;//访问数据的value
private Integer hitCount;//记录访问次数
private Long lastTime;//最新的访问时间
public AccessRate(Integer key, Integer value, Integer hitCount, Long lastTime) {
this.key = key;
this.value = value;
this.hitCount = hitCount;
this.lastTime = lastTime;
}
public AccessRate() {
}
public AccessRate(Integer key) {
this.key=key;
}
public boolean isNotNull(){
return key!=null&&value!=null;
}
@Override
public int compareTo(AccessRate o) {
int firstSort=hitCount.compareTo(o.hitCount);
if(firstSort!=0){////如果命中次数不相等，使用命中次数排序
return firstSort;
}else {//如果命中次数相等，就使用访问的时间进行排序
return lastTime.compareTo(o.lastTime);
}
}
@Override
public String toString() {
return "AccessRate{" +
"key=" + key +
", value=" + value +
", hitCount=" + hitCount +
", lastTime=" + lastTime +
'}';
}
}
}（友情提示：代码块可左右滑动）
代码并不复杂，为了方便大家观察到细节，我特意在代码里面加了相关log输出，下面我们来测试这个缓存算法：
public static void main(String[] args) {
//构建一个容量为3的LFU缓存实例
LFUCache cache=new LFUCache(3);
cache.put(1,1);// 添加 1
cache.put(2,2);// 添加 2
cache.get(1);// 访问 1
cache.get(2);// 访问 2
cache.put(3,3);// 添加 3
cache.put(4,4);// 缓存满，先淘汰访问次数少的3，然后再添加 4
cache.get(5);// 访问 5
cache.remove(4); // 移除 4
cache.remove(4);// 移除 4
}完整代码，请访问我的github：https://github.com/qindongliang/Java-Note/blob/master/src/main/java/algorithm/cache_algorithm/LFUCache.java
运行上面的代码，我们的控制台输出信息如下：
add => AccessRate{key=1, value=1, hitCount=1, lastTime=113379228623808} 当前缓存中有效的key=1
add => AccessRate{key=2, value=2, hitCount=1, lastTime=113379229329163} 当前缓存中有效的key=1，2
query => AccessRate{key=1, value=1, hitCount=2, lastTime=113379229389607} 当前缓存中有效的key=1，2
query => AccessRate{key=2, value=2, hitCount=2, lastTime=113379229445363} 当前缓存中有效的key=1，2
add => AccessRate{key=3, value=3, hitCount=1, lastTime=113379229493594} 当前缓存中有效的key=1，2，3
evict => AccessRate{key=3, value=3, hitCount=1, lastTime=113379229493594} 当前缓存中有效的key=1，2，3
add => AccessRate{key=4, value=4, hitCount=1, lastTime=113379229660888} 当前缓存中有效的key=1，2，4
query => the key 5 not exist 当前缓存中有效的key=1，2，4
remove => AccessRate{key=4, value=4, hitCount=1, lastTime=113379229660888} 当前缓存中有效的key=1，2
remove => the key 4 not exist 当前缓存中有效的key=1，2可以看到结果是没问题的，在上面的测试中，我们设置缓存的容量大小为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缓存。