相关博客链接：
图解LinkedHashMap原理
1 前言
LinkedHashMap内部维护了一个双向链表，能保证元素按照插入的顺序访问，也能以访问顺序访问，可以用来实现LRU缓存策略。
LinkedHashMap可以看成是 LinkedList + HashMap。
支持两种顺序：
- 插入顺序：先添加的在前面，后添加的在后面，修改操作不影响顺序。
- 访问顺序：所谓访问指的是get/put操作，对一个键执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
继承体系：
添加删除元素的时候需要同时维护在HashMap中的存储，也要维护在LinkedList中的存储，所以性能上来说比HashMap稍慢。
存储结构图：
2 源码解析
2.1 主要属性
/**
* 双向链表头节点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双向链表尾节点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 是否按照访问顺序排序
* @serial
*/
final boolean accessOrder;
（1）head
双向链表的头节点，旧数据存在头节点。
（2）tail
双向链表的尾节点，新数据存在尾节点。
（3）accessOrder
是否需要按访问顺序排序，如果为false则按插入顺序存储元素，如果是true则按访问顺序存储元素。
2.2 内部类
// 位于LinkedHashMap中
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
存储节点，继承自HashMap的Node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。
2.3 构造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
前四个构造方法accessOrder都等于false，说明双向链表是按插入顺序存储元素。
最后一个构造方法accessOrder从构造方法参数传入，如果传入true，则就实现了按访问顺序存储元素，这也是实现LRU缓存策略的关键。
2.4 方法
<1> afterNodeInsertion(boolean evict)方法
在节点插入后做些什么，在HashMap中的putVal()方法中被调用，HashMap中这个方法的实现为空。
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);
}
}
（1）如果evict为true，且头节点不为空，且确定移除最老的元素，那么就去调用HashMap.removeNode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）
（2）HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法
（3）afterNodeRemoval()方法在LinkedHashMap中也有实现，用来在移除元素后修改双向链表
（4）默认removeEldestEntry()方法返回false，也就是不删除元素。
<2> afterNodeAccess(Node e)方法
在节点方位之后被调用，即get()或者getOrDefault()，如果accessOrder为true，调用这个方法把访问到的节点移动到双向链表的末尾。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果accessOrder为true，并且访问的节点不是尾节点
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 把p节点从双向链表中删除
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
// 把p节点放到双向链表的末尾
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
// 尾节点等于p
tail = p;
++modCount;
}
}
（1）如果accessOrder为true，并且访问的节点不是尾节点；
（2）从双向链表中移除访问的节点
（3）把访问的节点加到双向链表的末尾；（末尾是最新访问的元素）
<3> afterNodeRemoval(Node e)方法
在节点被删除之后调用的方法。
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 把节点p从双向链表中拿出来,unlink
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
经典的把节点从双向链表中删除的方法。
<4> get(Object key)方法
获取元素
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
如果查找到了元素，且accessOrder为true，则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。
3.总结
（1）LinkedHashMap继承自HashMap，具有HashMap的所有特性
（2）LinkedHashMap内部维护了一个双向链表存储所有的元素
（3）如果accessOrder为false，则可以按插入元素的顺序遍历元素
（4）如果accessOrder为true，则可以按访问元素的顺序遍历元素；
（5）LinkedHashMap的实现非常精妙，很多方法都是在HashMap中留的钩子（Hook），直接实现这些Hook就可以实现对应的功能了，并不需要再重写put()等方法；
（6）默认的LinkedHashMap并不会移除旧元素，如果需要移除旧元素，则需要重写removeEldestEntry()方法设定移除策略；
（7）LinkedHashMap可以用来实现LRU缓存淘汰策略；
4.面试题
如何使用LinkedHashMap实现LRU缓存淘汰策略？
LRU策略：Least Recently Used，最近最少使用，也就是优先淘汰最近最少使用的元素。
如果使用LinkedHashMap，我们把accessOrder设置为true是不是就差不多能实现这个策略了呢？答案是肯定的。
public class LRUTest {
public static void main(String[] args) {
// 创建一个只有5个元素的缓存
LRU<Integer,Integer> lru=new LRU<>(5,0.75f);
lru.put(1,1);
lru.put(2,2);
lru.put(3,3);
lru.put(4,4);
lru.put(5,5);
lru.put(6,6);
lru.put(7,7);
System.out.println(lru);
System.out.println(lru.get(4));
System.out.println(lru);
lru.put(6,666);
System.out.println(lru);
}
}
class LRU<K,V> extends LinkedHashMap<K,V>{
// 保存缓存的容量
private int capacity;
public LRU(int capacity,float loadFactor){
super(capacity,loadFactor,true);
this.capacity=capacity;
}
/**
* 重写该方法设置何时移除旧元素
* @param eldest
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当元素个数大于缓存的容量,就移除元素
return size() > this.capacity;
}
}
结果显示：
