专栏首页我是攻城师如何动手撸一个简单的LFU缓存

如何动手撸一个简单的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缓存。

本文分享自微信公众号 - 我是攻城师(woshigcs),作者:攻城师在路上

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关于Java里面的嵌套类,你了解多少?

    最近在看《Core Java for the Impatient》这本书,当然为了方便我看的是英文电子版的PDF格式(有需要的朋友,可以后台留言给我),期间又重...

    我是攻城师
  • Spark历险记之编译和远程任务提交

    我是攻城师
  • 什么是线程安全?

    线程安全在多线程编程时是一个比较重要的概念,我们下先来看下维基百科是如何定义这个概念的:

    我是攻城师
  • 4-SII--☆Android缓存文件(带有效时长)封装

    张风捷特烈
  • 调用链系列四:调用链上下文传递

    在之前的调用链系列文章中,我们已经对调用链进行了详细介绍,相信大家已经对调用链技术有了基本的了解。

    宜信技术学院
  • Guava Cache -- Java 应用缓存神器

    Guava 作为Google开源Java 库中的精品成员,在性能、功能上都十分出色,本文将从实际使用的角度,来对Guava进行讲解。

    特鲁门
  • Python多线程编程中使用Barrier对象进行同步

    Barrier常用来实现这样的线程同步,多个线程运行到某个时间点以后每个线程都需要等着其他线程都准备好以后再同时进行下一步工作。类似于赛马时需要先用栅栏拦住,每...

    Python小屋屋主
  • Java并发编程:synchronized和锁优化

    1. 使用方法 synchronized 是 java 中最常用的保证线程安全的方式,synchronized 的作用主要有三方面: 确保线程互斥的访问代码块,...

    butterfly100
  • 干货:Java并发编程系列之synchronized(一)

    技术zhai
  • 十面阿里,屌丝逆袭阿里之路

    Java架构

扫码关注云+社区

领取腾讯云代金券