LRU算法（Last Recently Used），是缓存淘汰算法的其中一种，即最近最久未使用。
在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。
事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来更新和访问其中的元素。
下面说一下LRU算法的核心思想，LRU算法的设计原则是：
如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰
这里提供两种使用Java的实现方式
使用LinkedHashMap
具体实现源码：
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int CACHE_SIZE;
/**
* 构造器，构造缓存的大小，即最多能缓存多少参数
*
* 初始化的 initialCapacity 结果+1，是为了在cacheSize小于0.75时除的结果为0，但是这时候要有能存储的元素，所以+1
* accessOrder：控制访问顺序。用于设置LinkedHashMap在调用 get() 之后的操作。如果设置为true，则每次调用get后会将该元素移动到末尾
* removeEldestEntry：默认返回为false，在调用 afterNodeInsertion()的内部，调用该方法。也就是说，每次添加元素之后，检查并移除最后一个元素
*
*
* @param cacheSize
*/
public LRUCache(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75)+1, 0.75F, true);
CACHE_SIZE = cacheSize;
}
/**
* 重写removeEldestEntry
* 当map中的数据大于指定缓存大小的时候，就删除最老的数据
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > CACHE_SIZE;
}
}
LinkedHashMap中关键方法的源码：
// 添加Node之后的操作，可以看到调用了 removeEldestEntry，移除头部元素
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 访问Node之后的操作，可以看到，当设置了accessOrder以后，访问元素之后，会把该Node放到尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
可以看到，LinkedHashMap事实上已经提供了内存置换的功能，我们利用了其中内置的功能并重写了部分方法后，实现了LRUCache。
需要注意两点：
1、构造器中调用父方法的第三个参数 accessOrder（默认为false），通过源码注释可以知道，这个表示元素的访问模式。true为access-order，false为insertion-order
当accessOrder=true时，用于搭配方法 removeEldestEntry(Map.Entry<K, V> eldest) 使用。
2、受保护方法 removeEldestEntry(Map.Entry<K, V> eldest)，用于判断是否移除最老一个元素。使得Cache可以在元素满之后移除最老的元素。
使用HashMap 编码实现LRUCache
具体实现源码：
public class LRUCacheCustom<K,V> {
// 双链表
static class CacheNode{
CacheNode before;
CacheNode after;
Object key;
Object val;
public CacheNode(){}
}
/** 头节点 */
private CacheNode head;
/** 尾节点 */
private CacheNode tail;
/** 最大元素数 */
private int maxCapacity;
/** 用于存储节点数据 */
private HashMap<K, CacheNode> caches;
/** 初始化 */
public LRUCacheCustom(int maxCapacity){
this.maxCapacity = maxCapacity;
caches = new HashMap<>(maxCapacity);
head = new CacheNode();
tail = new CacheNode();
head.after = tail;
tail.before = head;
}
public void put(K k, V v){
CacheNode node = caches.get(k);
if(node == null){
node = new CacheNode();
node.key = k;
}
node.val = v;
moveToFirst(node);
caches.put(k, node);
if(caches.size() > maxCapacity){
caches.remove(tail.before.key);
removeLast();
}
}
public V get(K k){
CacheNode node = caches.get(k);
if(node == null){
return null;
}
Object val = node.val;
moveToFirst(node);
return (V) val;
}
public void removeLast(){
CacheNode last = tail.before;
CacheNode secondLast = tail.before.before;
secondLast.after = tail;
tail.before = secondLast;
// 手动释放内存
caches.remove(last.key);
last = null;
}
public void moveToFirst(CacheNode node){
// 先把原来node的前后连起来，如果前后不为null的话。（注意顺序不能错）
CacheNode nodeBefore = node.before;
if(node.after != null){
node.after.before = nodeBefore;
}
if(nodeBefore != null ){
nodeBefore.after = node.after;
}
// 然后把node放前面
CacheNode tmp = head.after;
head.after = node;
node.before = head;
tmp.before = node;
node.after = tmp;
}
@Override
public String toString() {
return caches.toString();
}
public String getCache(){
StringBuilder bu = new StringBuilder();
CacheNode dummy = head;
while(dummy.after != null){
bu.append("{key=" + dummy.key);
bu.append(", val=" + dummy.val);
bu.append("\n -->");
dummy = dummy.after;
}
return bu.toString();
}
}
以上代码我已经自测通过
测试代码：
@Test
public void lruCacheTest(){
LRUCacheCustom cacheCustom = new LRUCacheCustom(3);
cacheCustom.put(1,"AAA");
cacheCustom.put(2,"BBB");
cacheCustom.put(3,"CCC");
System.out.println(cacheCustom.getCache()); // 3 2 1
cacheCustom.put(4,"DDD");
System.out.println(cacheCustom.getCache()); // 4 3 2
// get(2) 将2提升到顶部
cacheCustom.get(2);
System.out.println(cacheCustom.getCache()); // 2 4 3
cacheCustom.put(5,"DDD");
System.out.println(cacheCustom.getCache()); // 5 2 4
}
参考：
LRU Cache
