【算法】LFU最近最少使用算法原理分析和编码实战

什么是LFU

• Least Frequently Used 最近最少使用，表示以次数为参考，淘汰一定时期内被访问次数最少的数据
• 如果数据过去被访问多次，那么将来被访问的频率也更高
• 比LRU多了一个频次统计，需要时间和次数两个维度进行判断是否淘汰
• 关键流程
  • 新加入数据插入到队列尾部，需要吧引用计数初始值为 1
  • 当队列中的数据被访问后，对应的元素引用计数 +1，队列按【次数】重新排序，如果相同次数则按照时间排序
  • 当需要淘汰数据时，将排序的队列末尾的数据删除，即访问次数最少

编码实战

public class LFUCache<K,V> {

    //定义缓存容量
    private  int capacity;

    //定义存储key，value数值
    private Map<K,V> cacheValue;

    //存储key的使用频次
    private Map<K, CacheObj> count;

    //定义构造方法
    public LFUCache(int capacity){
        this.capacity = capacity;
        cacheValue =  new HashMap<>();
        count =  new HashMap<>();
    }

    //存储数据
    public void put(K key, V value) {
        V objValue = cacheValue.get(key);
        if(objValue == null){
            //新元素插入，需要判断是否超过缓存容量大小
            if (cacheValue.size() == capacity) {
                removeElement();
            }
            count.put(key, new CacheObj(key, 1, System.currentTimeMillis()));
        } else {
            addCount(key);
        }
        cacheValue.put(key, value);
    }

    //读取某个key，如果这个key存在就count++
    public V get(K key) {
        V value = cacheValue.get(key);
        //如果key获取的value不为空，则对这个key的使用次数++
        if (value != null) {
            addCount(key);
        }
        return value;
    }

    //删除元素
    private void removeElement() {
        CacheObj cacheObj = Collections.min(count.values());
        cacheValue.remove(cacheObj.getKey());
        count.remove(cacheObj.getKey());
    }

    //更新相关统计频次和时间
    private void addCount(K key) {
        CacheObj cacheObj = count.get(key);
        cacheObj.setCount(cacheObj.getCount()+1);
        cacheObj.setLastTime(System.currentTimeMillis());
    }

    //展示信息
    public void showInfo(){
        cacheValue.forEach((key,value)->{
            CacheObj cacheObj = count.get(key);
            System.out.println("key:"+key+",value:"+value+",count:"+cacheObj.getCount()+",lastTime:"+cacheObj.getLastTime());
        });
    }

    //定义比较对象
    class CacheObj implements Comparable<CacheObj>{

        //定义使用的key
        private K key;
        //定义访问次数
        private int count;
        //定义最后访问的时间
        private long lastTime;

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        public long getLastTime() {
            return lastTime;
        }

        public void setLastTime(long lastTime) {
            this.lastTime = lastTime;
        }

        //定义构造方法
        public CacheObj(K key, int count, long lastTime) {
            this.key = key;
            this.count = count;
            this.lastTime = lastTime;
        }

        //用于比较大小，如果使用次数一样，则比较时间大小
        @Override
        public int compareTo(CacheObj o) {
            int value = Integer.compare(this.count,o.count);
            return value == 0 ? Long.compare(this.lastTime,o.lastTime): value;
        }
    }

    public static void main(String[] args) {
        LFUCache<String,String> cache = new LFUCache(2);
        cache.put("A","任务A");
        cache.put("A","任务AA");
        cache.showInfo();
        System.out.println("---------");

        String cacheValue = cache.get("A");
        System.out.println(cacheValue);
        cache.showInfo();
        System.out.println("---------");

        cache.put("B","任务B");
        cache.put("B","任务BB");
        cache.showInfo();
        System.out.println("---------");
        //插入新元素，由于a的count是3，b的count是2，所以淘汰了b
        cache.put("C","任务C");
        cache.showInfo();
    }
}