LRU（Least recently used，最近最少使用）算法是目前广泛使用的缓存淘汰算法。算法思想是如果数据最近被访问（读或写），那么将来被访问的概率也更高。所以长期不被访问的数据将会被淘汰。
LeetCode的146题要求实现这一算法。
public class LRUCache {
private final int capacity;
private Map<Integer, Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<Integer, Integer>() {
private static final long serialVersionUID = 23L;
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
return size() > LRUCache.this.capacity;
}
};
}
public int get(int key) {
Integer value = map.get(key);
if (value != null) {
map.remove(key);
map.put(key, value);
} else {
value = -1;
}
return value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
map.remove(key);
}
map.put(key, value);
}
}
上面这段代码可以继续优化。
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<Integer, Integer>(32, 0.75f, true) {
private static final long serialVersionUID = 23L;
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
return size() > LRUCache.this.capacity;
}
};
}
LinkedHashMap本就可以按照访问访问顺序排序，当时没有注意到这个构造方法。其余代码略去。
从LinkedHashMap的构造方法来看，可以分成两类：按插入顺序排序，按访问顺序排序。
我的提交代码非常依赖LinkedHashMap这种数据结构，从类名上看来，它和HashMap必然有所关系。其实它是HashMap的子类，在HashMap基础上增加排序功能，让输出顺序与插入顺序或者访问顺序相同，即最后一个插入（或访问）的元素最后一个输出。
HashMap的实现依赖链表数组（数组的每个元素是链表），但里面的元素是无序的。LinkedHashMap在其基础之上，增加了一个链表来记录元素的顺序。
通过对比这两类，完美体现了面向对象编程的继承机制，需要深刻体会！
学习一个类的最基本最重要的方法就是JDK文档。一段官方文档，胜过千句啰嗦。
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.
LinkedHashMap还可以在某种特点条件下removeEldestEntry，这也是实现LRU算法的一个关键。
Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest entry each time a new one is added. This is useful if the map represents a cache: it allows the map to reduce memory consumption by deleting stale entries.
常见用法：
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
原题：LRU Cache
