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