LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”
Java中的LinkedHashMap已经实现了90%的LRU算法。
1、需要理解HashMap的实现包括Hash数组和双向节点链表，HashMap的搜索包括Hash定位和遍历比较两个过程，不同的子节点要求HashCode和equal都不同才算不同。
HashMap的Hash数组和节点链表
2、（错误理解）LRU实现过程如下图示，每次访问提升被访问的节点到所在链表的首位，搜索中，Hash是免不了的，但是遍历过程可以化简：
LRU原理
3、LRU最近最少算法，在本地缓存用的比较多，自带更新和销毁，缓存没有再找其他重方法查询，因此可以叫做一级缓存或者热缓存。缓存的node个数是有限的。
LinkedHashMap重写了迭代器、contain()方法，利用双向链表快速访问；
只需要实现淘汰策略的linkedHashMap就是一个很不错的LRU实现了。
image.png
public class LruMap extends LinkedHashMap {
// 容量
private int cap;
public LruMap(int cap) {
// 初始化，hashMap为指定size
super(cap, 0.7f, true);
this.cap = cap;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
if (size() > cap) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
LruMap lruMap = new LruMap(3);
lruMap.put(1, 1);
System.out.println(lruMap);
lruMap.put(2, 1);
System.out.println(lruMap);
lruMap.put(3, 1);
System.out.println(lruMap);
lruMap.put(4, 1);
System.out.println(lruMap);
lruMap.put(5, 1);
System.out.println(lruMap);
}
}
以上实现的问题：
线程不安全
....