LRU(Least Recently Used)算法,旨在一个固定大小的容器盛满时,当要再次放入元素时,淘汰掉最久没有使用的元素。
在读者的上一篇博客中,分析了LinkedHashMap的原理,我们把总结再发一次:
put新元素时,会把元素放到双向链表的尾部,并且调用removeEldestEntry()方法:若为true,把首元素从双向链表中移除;为false,不做处理。
put旧元素时,当accessOrder为true时,把对应的元素移到双向链表的尾部;为false时,不做处理。
get元素时,当accessOrder为true时,把对应的元素移到双向链表的尾部;为false时,不做处理。
借助该特性,我们可以用如下思路实现:新建一个类,继承自LinkedHashMap,重写其removeEldestEntry()方法,方法中判断:如果当前放入的元素的个数大于某个值,就返回true,否则返回false。并且该类的实例要设置accessOrder为true。
具体代码如下:
import java.util.LinkedHashMap; import java.util.Map; public class LRUextends LinkedHashMap { public LRU(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor, accessOrder); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { if(size() > 5) { return true; } return false; } }
使用如下:
public static void main(String[] args) {
LRU map = new LRU<>(16, 0.75f, true);
char[] arr = "abcde".toCharArray();
for(int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
map.put('f', 5);
//不能用keySet(),否则报错
//Set set = map.keySet();
//for (Character c : set) {
// System.out.println("key:" + c + ",value:" + map.get(c));
//}
for (Map.Entry entry: map.entrySet()) {
System.out.println("key:" + entry.getKey() + ",value:" + entry.getValue());
}
}
运行结果为:
而如果在map.put(‘f’, 5);前添加代码:
则运行结果为:
因为put(‘a’, 6);或get(‘a’)都是对a元素的一次使用,此时按照距今没有使用的时间,从大到小排列:b、c、d、e、a;当要再放入f元素时,会淘汰b。



