一：概述
上一系列文章中介绍了HashMap的一系列原理和方法，本文介绍下LinkedHashMap。LinkedHashMap继承自HashMap，所以HashMap的特性，LinkedHashMap基本上都有；LinkedHashMap还对HashMap做了一些扩展。
在已经存在HashMap的基础上为什么还要引入LinkedHashMap呢？这是因为HashMap的遍历顺序和插入顺序不一致，比如你按顺序插入三个节点：Node1,Node2,Node3，那么遍历HashMap的时候遍历的先后结果可能是Node2,Node1,Node3;有时候需要保证插入顺序和遍历顺序保持一致，这时候HashMap就无能为力了，这就是LinkedHashMap的作用，LinkedHashMap是通过一个双向链表维护这种关系的，从网上拷了一张图来加深理解：
LinkedHashMap结构
在撸源码之前，先看一个demo，了解下HashMap和LinkedHashmap的具体区别：
Map<String , String> hashMap = new HashMap<String, String>();
//存入键值对
hashMap.put("覆盖沙发垫", "a");
hashMap.put("放松放松", "b");
hashMap.put("方式发顺丰", "c");
hashMap.put("各个", "d");
//遍历
for(Iterator<String> it = hashMap.values().iterator();it.hasNext();) {
String value = it.next();
System.out.println(value);
}
输出结果如下：
b
a
c
d
可以看到，HashMap的访问顺序和插入顺序不一定是一样的，这取决于各个元素的key的hash的大小。
再来看看LinkedHashMap：
//创建LinkedHashMap，前面两个是LinkedHashMap的容量和加载因子；注意最后一
//个参数这个参数是accessOrder，他代表访问LinkedHashMap里面的元素的顺序，
//如果是false，那么按照访问的顺序排序；如果为true，那么按照插入的顺序排序
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,false);
//按1 ---> a，2 ---> b，3 ---> c，4 ---> d的顺序插入；
map.put("1", "a");
map.put("2", "b");
map.put("3", "c");
map.put("4", "d");
for(Iterator<String> it = map.values().iterator();it.hasNext();) {
String name = (String)it.next();
System.out.println(name);
}
输出结果如下：
a
b
c
d
可以看到，LinkedHashMap的访问顺序和插入顺序一毛一样；再次修改代码：
//访问
map.get("1");
//更新
map.put("2", "tuhao");
输出结果如下：
a
tuhao
c
d
可以看到，只要accessOrder为false，那么LinkedHashMap的访问顺序就是插入顺序，不管怎么更新或者获取LinkedHashMap的数据，都是这样；再来看个例子:
//跟上面的例子相比，仅仅是accessOrder从false改为true，其他不变
Map<String, String> map1 = new LinkedHashMap<String, String>(16,0.75f,true);
map1.put("1", "a");
map1.put("2", "b");
map1.put("3", "c");
map1.put("4", "d");
for(Iterator<String> it = map1.values().iterator();it.hasNext();) {
String name = (String)it.next();
System.out.println(name);
}
输出结果如下：
a
b
c
d
可以看到，如果是插入全新的元素，那么不管accessOrder是true还是false，访问顺序都是插入顺序，再添加代码如下：
map1.get("1");
map1.put("2", "tuhao");
map1.put("5", "e");
for(Iterator<String> it = map1.values().iterator();it.hasNext();) {
String name = (String)it.next();
System.out.println(name);
}
输出结果如下：
c
d
a
tuhao
可以看到，先访问了1，仅仅是访问了一下，1对应的值a就跑到4对应的值d后面去了；说明如果accessOrder为true，只要访问了LinkedHashMap中的数据，那么这个键值对就跑到LinkedHashMap的尾部了；调用put去更新LinkedHashMap中的数据也会导致更新的键值对跑到LinkedHashMap的尾部，所以LinkedHashMap在put和get的时候，肯定有将目标节点移到链表尾部的过程。
综上可知，LinkedHashMap的访问顺序是和插入/更新的顺序相关的，而HashMap不具备这种特性；LinkedHashMap这种特性在追求有序的场景，比如缓存的地方能派上用场；至于是什么顺序就取决于accessOrder的值了。
看完HashMap和LinkedHashMap的区别，下面就撸一把LinkedHashMap的源码，探究其中的原理：
//LinkedHashMap继承自HashMap，他有数组，有链表，也有红黑树
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
* LinkedHashMap的节点类Entry继承自HashMap的Node类，在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);
}
}
}
LinkedHashMap的节点和HashMap的节点是不一样的，因为LinkedHashMap需要维护一个双线链表，必须具备前驱和后继两个节点，HashMap的节点Node显然胜任不了这样的工作；需要注意的是，红黑树节点TreeNode继承自LinkedHashMap的节点类Entry：
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
......
}
红黑树节点TreeNode继承自LinkedHashMap的节点类Entry，使得在LinkedHashMap中使用红黑树的时候，也能维护双向链表的结构。
二：插入
虽然LinkedHashMap和HashMap的结构有所差异，但是LinkedHashMap的put方法根HashMap一样，LinkedHashMap并没有重写他，差异在创建节点的时候，LinkedHashMap重写了创建节点的方法newNode：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//前面的逻辑一样的
......
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//创建全新的节点并插入节点的尾部；注意这个方法，LinkedHashMap对他进行了重写
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//获取老的值
V oldValue = e.value;
//onlyIfAbsent是传进来的，默认是false；所以进入if
if (!onlyIfAbsent || oldValue == null)
//简单的赋值
e.value = value;
//afterNodeAccess在HashMap中是一个空实现，
//在研究HashMap的时候，这个方法没有分析
afterNodeAccess(e);
return oldValue;
}
}
//修改次数+1，HashMap是线程不安全的，这玩意就是为
//了解决迭代的时候修改HashMap造成的异常，后面分析
++modCount;
//如果HashMap的元素个数超过阈值，就调用resize()进行扩容
if (++size > threshold)
resize();
//在研究HashMap的时候，这个方法没有分析
afterNodeInsertion(evict);
return null;
}
LinkedHashMap和HashMap的putVal方法基本一致，除了几个差异，我们来看下这几个差异：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//创建LinkedHashMap的节点类Entry
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//调用linkNodeLast，从名字都可以看出，是把刚创建的节点插入到链表尾部
linkNodeLast(p);
//返回刚才创建的节点
return p;
}
LinkedHashMap和HashMap的newNode方法除了创建的节点不完全一样外，还多了一个linkNodeLast的调用：
// link at the end of list
//将目标节点插入链表尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
//tail是LinkedHashMap的成员变量，代表双向链表的尾节点
LinkedHashMap.Entry<K,V> last = tail;
//首先将传过来的目标节点赋值给尾节点
tail = p;
//如果尾节点为空，说明双向链表还不存
//在，那么传过来的目标节点当做头节点
if (last == null)
head = p;
//如果尾节点不为空，说明链表已经存在
else {
//p已经是尾节点了，那么将p的前驱节点指向原来的尾节点
p.before = last;
//将原来的尾节点的后继节点指向现在的尾节点p
last.after = p;
}
}
可以看到，LinkedHashMap在创建节点后，把节点插入了双向链表的尾部，并维护了前驱和后继节点的正确指向。在putVal方法里面有个判断if (e != null) ;这个判断是什么意思呢?put一个元素的时候，可能HashMap里面没有这个元素，那么就插入一个全新的节点；也有可能这个元素已经存在，那么就更新对应节点；是插入还是更新，就看e是不是空了；如果e不为空，那么说明是更新节点，跟新后会把这个节点返回；如果e为空，说明是插入一个全新的节点，新插入节点是不会把插入的节点返回回来的；一个节点更新了，也要移到双向链表的尾部，这就是afterNodeAccess的作用；下面分析afterNodeAccess：
//将更新的节点移到链表的尾部(如果是按访问节点的顺序来排序节点的话)
void afterNodeAccess(Node<K,V> e) { // move node to last
//申明一个中间变量，代表尾节点
LinkedHashMap.Entry<K,V> last;
//accessOrder是一个重要的变量，他代表节点的排序方式；如果它为true，说明
//按访问的顺序来排序(更新也是一种访问)，最近一个访问(包括更新)的节点将被放
//到链表尾部；下次访问的时候，这个节点将被最后访问到;如果他为false，那么访
//问的顺序将是插入的顺序，每次访问(包括)节点后，节点之间的顺序不变;
//如果尾节点不是传进来的节点，而且是按访问节点的顺序来排序
if (accessOrder && (last = tail) != e) {
//首先将传进来的节点赋值给p；其次将p的前驱和后继节点赋值给b、a;
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//传进来的节点p(e赋值给他的)将是尾节点，所以首先将后继节点置空
p.after = null;
//如果p的前驱节点是空，那么将p的后继节点置为头结点。注意哦，进入这个
//方法的前提是目标节点e(p)已经存在于链表中了，然后我们刚刚还访问了他
//所以要将他要移到尾节点；既然这个节点已经存在于链表中了，那么他肯定有
//前驱或者后继节点；如果他的前驱节点是空，说明我们刚才访问的是头结点，
//要把头结点移到尾节点去，所以只能把原来的头结点的后继节点置为新的头结点
if (b == null)
head = a;
//如果刚刚访问的节点p有前驱节点，那么将p的前驱
//节点的后继节点指向p自己的后继节点，这没毛病
else
b.after = a;
//如果刚刚访问的节点p的后继节点不为空，说明p不是尾节点
if (a != null)
//那么需要将p的后继节点的前驱节点置为p的前驱节点，没毛病
a.before = b;
else
//如果刚刚访问的节点的后继节点为空，说明我们访问的节点
//就是尾节点，这个时候将访问的节点的前驱节点赋值给last
//last就指向了倒数第二个节点
last = b;
//如果last为空(if里面就对last进行了赋值)，说明尾节点
//是空，说明链表不存在，这时候将传进来的节点置为头结点
if (last == null)
head = p;
//last不为null(他既可能指向尾节点，也可能指向倒数第二个节点)
else {
//将刚才访问的节点的前驱节点指向尾节点
p.before = last;
//将原来尾节点的后继节点指向刚才访问的节点，这样last就不是尾节点了
last.after = p;
}
//将刚才访问的节点p置为尾节点，没毛病
tail = p;
//modCount自增，没毛病
++modCount;
}
}
上面就是当accessOrder为true时，目标节点移到链表尾部的过程；下面再来看下HashMap的putVal中的最后一个方法afterNodeInsertion，这个方法在HashMap里面是个空实现，但是在LinkedHashMap实现了，也就说只有往LinkedHashMap里面put元素的时候，这个方法才会起作用，我们来看下到底是什么作用：
//可能需要删除最老的元素
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//removeEldestEntry的返回值写死了false，所以不会进入if
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
上面的代码初看会有点奇怪，为什么removeEldestEntry写死了返回false呢？这是java留给我们让我们根据具体情况来决定是不是要重写。上面说过，LinkedHashMap适合用于缓存，但是缓存也是有上限的，达到上限后，就应该把最老的，没人访问的元素删掉，给将来新的元素腾坑；如果有这种需求的话，就重写removeEldestEntry方法，比如：：
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > cacheSize;
}
既然要删除，那么删除哪个节点呢？当然是头节点，因为所有的节点在插入和更新后，都是放在链表结尾的；所以头结点才是访问的最少的，所以afterNodeInsertion方法先拿到头节点first的key，然后去删除，删除的方法和HashMap的删除一样，不啰嗦了。
通过HashMap和LinkedHashMap的研究发现，要想理解Java的集合类，一定要先理解常用的数据结构，比如数组，链表，队列，二叉树，红黑树等。
网友评论