LRU全称是Least Recently Used，即最近最久未使用的意思。
LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
LRU目前有很多种实现，下面的是java中基于LinkedHashMap的一种实现。下面的实现是线程不安全的，如想要线程安全，只需在对应方法前加锁 即可。当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
利用LinkedHashMap 实现lru，只需要重写removeEldestEntry（）方法，即当缓存超过容量时，删除缓存。
具体代码如下：
package java算法;
import java.util.LinkedHashMap;
/**
*
* @author 刘慧丽
* LinkedHashMap实现LRU最近最久未访问算法
*
* 线程不安全，如若要线程安全则在需要的防范前加锁即可
* @param <K>
* @param <V>
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
//支持序列化
private static final long serialVersionUID = 1L;
//缓存大小
private int cacheSize;
//加载因子，0.75 表示当缓存到达四分之三时，开始扩容
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
public LRUCache(int cacheSize) {
//true accessOrder,ordering mode ，true 访问顺序排列，false插入顺序排列
super(cacheSize, DEFAULT_LOAD_FACTOR, true);
this.cacheSize=cacheSize;
}
//使用linkedHashMap 实现lru 时必须重写removeEldestEntry方法
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
//如果当前容量大于缓存容量，清空缓存
return size()>cacheSize;
}
public static void main(String[] args) {
LRUCache<Integer, String> lru = new LRUCache<>(4);
for(int i=0;i<4;i++) {
lru.put(i+1, "liuhuili"+i);
}
System.out.println("初始化缓存数据："+lru.keySet());
lru.get(2);//访问二
//目前缓存顺序，最近访问的会放在队列末尾
System.out.println(lru.keySet());
//添加一个元素，此时容量超出，删除第一个元素
lru.put(5, "adbc");
System.out.println(lru.keySet());
}
}
运行结果:
初始化缓存数据：[1, 2, 3, 4]
[1, 3, 4, 2]
[3, 4, 2, 5]
网友评论