2018-11-11 LRU 算法一

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]