最近接触LRU(Least Recently Used)，即最近最少使用，也称淘汰算法，在JDK中LinkedHashMap有相关实现，下面针对LRU及LinkedHashMap的LRU实现进行详细讲解
1. 为什么使用LRU有些数据需要缓存在内存中，以便高效查询。但是当缓存的数据量很大，并且某一时间段只有某小部分缓存数据被频繁使用(称之为热点数据)，而其他缓存数据暂时没有访问，这时就需要LRU策略对热点数据进行保留，对非热点数据进行及时下线，保证缓存空间健康。
应用场景: 商城分时段商品秒杀
2. LRU的LinkedHashMap实现创建LRULinkedHashMap继承LinkedHashMap并重写removeEldestEntry方法，该方法返回的boolean代表是否删除最早使用/存放的Entry。
LRULinkedHashMap代码语言：javascript代码运行次数：0运行复制public class LRULinkedHashMap
private int threshold;
public LRULinkedHashMap(int threshold) {
super(16, 0.75f, true);
this.threshold = threshold;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > threshold;
}
}使用get操作，会将节点移动到队尾。put操作，如果key不存在，则节点放置队尾，如果节点存在，会将节点移动到队尾。代码语言：javascript代码运行次数：0运行复制public static void main(String[] args) {
LRULinkedHashMap
lruLinkedHashMap.put("1", null);
lruLinkedHashMap.put("2", null);
lruLinkedHashMap.put("3", null);
lruLinkedHashMap.put("4", null);
lruLinkedHashMap.put("5", null);
lruLinkedHashMap.put("6", null);
lruLinkedHashMap.put("7", null);
System.out.println(lruLinkedHashMap);
lruLinkedHashMap.get("4");
System.out.println(lruLinkedHashMap);
lruLinkedHashMap.put("5", null);
System.out.println(lruLinkedHashMap);
out => {3=null, 4=null, 5=null, 6=null, 7=null}
out => {3=null, 5=null, 6=null, 7=null, 4=null}
out => {3=null, 6=null, 7=null, 4=null, 5=null}
}3. LinkedHashMap实现Map有序 - 源码分析LinkedHashMap继承自HashMap，HashMap采用数组加链表的结构存储数据，存储节点为HashMap.Node，分别存放hash值，key，value，以及指向下一个Node节点的next指针，链表结构是单项链表，HashMap并没有维护有序性。
HashMap
image.png
LinkedHashMap继承了HashMap，也是采用了数据加链表的结构，不同的是LinkedHashMap的存储节点(Entry)继承自HashMap.Node，多维护了before和after指针，用来指向上一个和下一个节点，实现双向链表。这个双向链表就可以实现Map有序性(access-order:访问顺序/insertion-order插入顺序，默认是insertion-order)。
LinkedHashMap
image.png
重点代码HashMap.Node代码语言：javascript代码运行次数：0运行复制static class Node
final int hash;
final K key;
V value;
Node
...
}LinkedHashMap.Entry代码语言：javascript代码运行次数：0运行复制static class Entry
Entry
...
}HashMap - newNode代码语言：javascript代码运行次数：0运行复制Node
return new Node<>(hash, key, value, next);
}LinkedHashMap - newNode代码语言：javascript代码运行次数：0运行复制// 重写了HashMap - newNode
Node
LinkedHashMap.Entry
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p); // 添加节点到队尾
return p;
}HashMap - forEach
先遍历数组，再顺序遍历链表代码语言：javascript代码运行次数：0运行复制@Override
public void forEach(BiConsumer action) {
Node
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (Node
for (; e != null; e = e.next) //再书序遍历链表
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}LinkedHashMap - forEach
直接遍历双向链表，实现有序性。代码语言：javascript代码运行次数：0运行复制// Map overrides
public void forEach(BiConsumer action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry
action.accept(e.key, e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}4. LinkedHashMap实现LRU - 源码分析下面是设置LinkedHashMap为访问顺序时的示意图。
image.png
LinkedHashMap - 构造器
accessOrder默认为false，即维护插入顺序，设置为true时，维护访问顺序。代码语言：javascript代码运行次数：0运行复制* @param accessOrder the ordering mode - {@code true} for access-order, {@code false} for insertion-order
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}代码语言：javascript代码运行次数：0运行复制public LinkedHashMap() {
super();
accessOrder = false; // 默认为插入顺序
}LinkedHashMap - get
当设置为访问顺序时，在get/put的时候调用afterNodeAccess方法，将节点移动到队尾。代码语言：javascript代码运行次数：0运行复制public V get(Object key) {
Node
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);// 将节点移动到队尾
return e.value;
}LinkedHashMap - put - 更新值
下面是HashMap的put操作，调用LinkedHashMap 的afterNodeAccess方法代码语言：javascript代码运行次数：0运行复制final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
....
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 将节点移动到队尾
return oldValue;
}
....
}LinkedHashMap - put - 插入新值
插入新值， 调用linkNodeLast添加节点到队尾代码语言：javascript代码运行次数：0运行复制// 重写了HashMap - newNode
Node
LinkedHashMap.Entry
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p); // 添加节点到队尾
return p;
}相关参考LeetCode – LRU Cache (Java)玩转Redis：8 种数据淘汰策略及近似LRU、LFU原理！