什么是LFU
- Least Frequently Used 最近最少使用，表示以次数为参考，淘汰一定时期内被访问次数最少的数据
- 如果数据过去被访问多次，那么将来被访问的频率也更高
- 比LRU多了一个频次统计，需要时间和次数两个维度进行判断是否淘汰
- 关键流程
- 新加入数据插入到队列尾部，需要吧引用计数初始值为 1
- 当队列中的数据被访问后，对应的元素引用计数 1，队列按【次数】重新排序，如果相同次数则按照时间排序
- 当需要淘汰数据时，将排序的队列末尾的数据删除，即访问次数最少
在这里插入图片描述编码实战
代码语言：java复制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();
}
}
在这里插入图片描述
