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

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();
    }
}