注：源码系列文章主要是对某付费专栏的总结记录。如有侵权，请联系删除。
1 LinkedHashMap 整体架构
HashMap 是无序的，TreeMap 可以按照 key 进行排序，那有木有 Map 是可以维护插入的顺序的呢？接下来我们看看 LinkedHashMap。
LinkedHashMap 本身是继承 HashMap 的，所以它拥有 HashMap 的所有特性，在此基础上，还提供了两大特性：
- 按照插入顺序进行访问；
- 实现了访问最小最先删除功能，其目的是把很久都没有访问的 key 自动删除。
1.1 按照插入顺序访问
1.1.1 LinkedHashMap 链表结构
// 链表头
transient LinkedHashMap.Entry<K,V> head;
// 链表尾
transient LinkedHashMap.Entry<K,V> tail;
// 继承 Node，为数组的每个元素增加了 before 和 after 属性
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);
}
}
// 控制两种访问模式的字段，默认 false
// true: 按照访问顺序，会把经常访问的 key 放到队尾
// false: 按照插入顺序提供访问
final boolean accessOrder;
从新增的属性可以看到，LinkedHashMap 的数据结构很像是把 LinkedList 每个元素换成了 HashMap 的 Node，像是两者的结合体，也正是因为增加了这些结构，从而能把 Map 的元素都串联起来，形成一个链表，而链表就可以保证顺序了，就可以维护元素插入进来的顺序。
1.1.2 按照顺序新增
LinkedHashMap 初始化时，默认的 accessOrder 是 false，就是会按照插入顺序提供访问，插入方法使用的是父类 HashMap 的 put 方法，不过覆写了 put 方法执行中调用的 newNode/newTreeNode 和 afterNodeAccess 方法。
newNode/newTreeNode 方法，控制新增节点追加到链表的尾部，这样每次新节点都追加到尾部，即可保证插入顺序了，我们以 newNode 源码为例：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 初始化一个新增的节点
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 追加到链表的尾部
linkNodeLast(p);
return p;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 缓存旧的尾节点
LinkedHashMap.Entry<K,V> last = tail;
// 赋值尾节点为新增节点
tail = p;
// 如果旧的尾节点为null则表示当前链表为空，直接将新增节点赋值于头节点
if (last == null)
head = p;
// 链表有数据，将旧的尾节点和新的尾节点互联
else {
p.before = last;
last.after = p;
}
}
LinkedHashMap 通过新增头节点、尾节点，给每个节点增加 before、after 属性，每次新增时，都把节点追加到尾节点等手段，在新增的时候，就已经维护了按照插入顺序的链表结构了。
1.1.3 按照顺序访问
LinkedHashMap 只提供了单向访问，即按照插入的顺序从头到尾进行访问，不能像 LinkedList 那样可以双向访问。
我们主要通过迭代器进行访问，迭代器初始化的时候，默认从头节点开始访问，在迭代的过程中，不断访问当前节点的 after 节点即可。
Map 对 key、value 和 entity（节点）都提供了迭代的方法，假设women携带 entity，就可以使用 LinkedHashMap.entrySet().iterator() 这种写法直接返回 LinkedHashIterator，LinkedHashIterator 是迭代器，我们通过调用迭代器的 nextNode() 方法就可以得到下一个节点，迭代器的源码如下：
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
// 初始化时，默认从头节点开始访问
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
// 当前遍历的节点
LinkedHashMap.Entry<K,V> e = next;
// 判断 modCount
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
// 通过链表的 after 结构，找到下一个迭代的节点
next = e.after;
return e;
}
}
在新增节点时，我们就已经维护了元素之间的插入顺序了，所以迭代访问是非常简答的，只需要不断的访问当前节点的下一个节点即可。
1.2 访问最少删除策略
1.2.1 演示
这种策略也叫做 <a href="https://baike.baidu.com/item/LRU/1269842?fr=aladdin">LRU</a>（least recently used，最近最少使用），大概的意思就是经常访问的元素会被追加到队尾，这样不经常访问的数据自然就靠近队头，然后我们可以设置删除策略，比如当 Map 元素个数大于多少时，把头节点删除，如下：
@Test
public void accessOrderTest() {
// 使用带参构造函数，分别指定初始化大小，加载因子，访问模式(accessOrder)
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(5, 0.75f, true) {
{
put(1, 1);
put(2, 2);
put(3, 3);
put(4, 4);
put(5, 5);
}
// 覆写了删除策略方法，我们设定当节点个数大于 4 时，就开始删除头节点
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > 4;
}
};
System.out.println("初始化: " + JSON.toJSONString(map));
map.get(3);
System.out.println("map.get(3): " + JSON.toJSONString(map));
map.get(2);
System.out.println("map.get(2): " + JSON.toJSONString(map));
}
执行结果：
初始化: {2:2,3:3,4:4,5:5}
map.get(3): {2:2,4:4,5:5,3:3}
map.get(2): {4:4,5:5,3:3,2:2}
可以看到，map 初始化的时候，我们放进去五个元素，但结果只有四个元素， 1 不见了，这个主要是因为我们覆写了 removeEldestEntry 方法，我们实现了如果 map 中元素个数大于 4 时，则就把队头的元素删除，当 put(5,5) 执行的时候，正好把队头的 1 删除，这个体现了当达到我们设定的删除策略时，会自动删除头节点。
当我们调用 map.get(3) 方法时，元素 3 移动到了队尾，调用 map.get(2) 方法时，元素 2 被移动到了队尾，这个体现了经常被访问的节点会被移动到队尾。
这个例子就很好的说明了访问最少删除策略，接下来看看原理。
1.2.2 元素被转移到队尾
为什么 get 时，元素会被移动到队尾：
public V get(Object key) {
Node<K,V> e;
// 调用 HashMap get 方法
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果设置了 LRU 策略
if (accessOrder)
// 这个方法把当前 key 移动到队尾
afterNodeAccess(e);
return e.value;
}
从上述源码中，可以看到，通过 afterNodeAccess 方法把当前访问节点移动到了队尾，其实不仅仅是 get 方法，执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时，也会这么做，通过不断的把经常访问的节点移动到队尾，那么靠近队头的节点，自然就是很少被访问的元素了。
1.2.3 删除策略
上述例子中我们在执行 put 方法时，发现队头元素被删除了，LinkedHashMap 本身是没有 put 方法实现的，调用的是 HashMap 的 put 方法，但 LinkedHashMap 实现了 put 方法中的调用 afterNodeInsertion 方法，这个方法实现了删除，源码如下：
// 删除很少被访问的元素，被 HashMap 的 put 方法所调用
void afterNodeInsertion(boolean evict) { // possibly remove eldest
// 得到链表的头节点
LinkedHashMap.Entry<K,V> first;
// 如果队列不为空，并且删除策略允许的情况下. removeEldestEntry 为我们覆写的删除策略
if (evict && (first = head) != null && removeEldestEntry(first)) {
// 得到头节点的 key
K key = first.key;
// 删除头节点
removeNode(hash(key), key, null, false, true);
}
}
1.3 小结
LinkedHashMap 提供了两个很有意思的功能：按照插入顺序访问和删除最少访问元素策略，简单的通过链表的结构就实现了，设计的非常巧妙。
LinkedHashMap 在 HashMap 的基础上简单的增加了链表结构，就形成了节点的顺序，非常巧妙。
------------------------------------- END -------------------------------------
