[toc]
前言
本篇文章介绍容器类的另一个哈希表LinkedHashMap，这是HashMap的关门弟子，直接继承了HashMap的衣钵，拥有HashMap的全部特性，并且有着HashMap没有的特性，下面就介绍有多大能耐。
LinkedHashMap简介与简单使用
先看看LinkedHashMap的继承结构：
image
LinkedHashMap属于Map大家族的一员，直接继承了HashMap，所以有着HashMap的全部特性，如高效查找元素，同时，LinkedHashMap保持了内部元素的顺序，有两种顺序模式，保持元素插入顺序/访问顺序，因此适用于保持元素顺序的场景，另外由于LinkedHashMap保持元素访问顺序，所以常被用作LRU缓存(即最近最少使用缓存策略)
LinkedHashMap的结构以及HashMap的对比
LinkedHashMap中的结构比HashMap更加复杂，首先他有着HashMap相同的结构，元素用数组+链表+红黑树形式存储，除此之外，所有元素还使用了双链表进行连接，相当于HashMap和LinkedList两种结构的结合体，也正是因为元素之间使用了链表连接，所以才能让其中的元素可以保持某种顺序，但也增加了维护这个链表的卡爱笑，每次进行增加和删除元素时，除了需要调整HashMap的结构，还需要调整链表结构，不过链表调整的开销并不大，除了数据量特别大场景，一般可以小到忽略不计。另一方面，由于所有元素使用链表相连，所以遍历的效率略高于HashMap，因为HashMap遍历时，需要每个桶中先遍历到链表尾部，然后在遍历到下一个桶，当元素不多而桶数量很多时，就会有很多次无效访问，所以理论上来说，LinkedHashMap的遍历效率要比HashMap高的，说了这么多，好像LinkedHashMap处理要比HashMap好，为啥不都用LinkedHashMap呢？
这个问题就跟LinkedList和ArrayList对比一样，两者都有适用的场景，并没有绝对的优势，所以还需要分情况分析。
LinkedHashMap中的节点
image
image
谜一样的继承关系，看完这个图，会想贵圈真乱，父类的TreeNode继承子类的Entry，子类中Entry又继承了父类中的Node，先别慌，这样做自然有他的道理，先来回顾一下Node结构，Node是HashMap中普通节点类，内部是这样的：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
/**
* 指向下一个节点的引用
*/
Node<K,V> next;
......省略部分代码
}
最上面的那个Entry是Map接口中的一个内部接口，只是规定了Entry该有的方法，并没有成员变量，在LinkedHashMap中，Entry内部类是这样的：
static class Entry<K,V> extends Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
增加了before和after引用，这样便可以和其他Entry一起组成一个双向链表，节点不仅存储了键值对信息，还可以是用next，before，after来链接前后节点，next引用仅用HashMap结构中链接同一个桶中的后一个元素而before和after引用则是用来链接LinkedHashMap中所有元素，将其链接成一个双向链表形式，接下来看根HashMap结构对比就很清晰了：
- HashMap结构图
image
- LinkedHashMap结构图
image
回到之前问题，为什么TreeNode要继承自LinkdeHashMap中的Entry引用而不是直接继承Node呢，毕竟在HashMap中并不需要使用这样的链表性质，增加after和before两个引用只会浪费空间,原因如下：
- 首先自然是为了复用代码，如果TreeNode直接继承Nnode，则失去了链表的特性，LinkedHashMap继承HashMap后，需要在使用拎一个内部类来继承TreeNode来使得其具有链表特性，并且相关方法均需要重写，大大增加工作量，并且代码的可维护性会下降很多。
- 其次，HashMap只会在桶中元素达到一定数量时候才会将节点转换为TreeNode，在哈希表散列良好的情况下，TreeNode很少被使用，所以这一点浪费是值的的。
LinkedHashMap可以看成由两部分组成，一部分与HashMap结构完全一致，另一部分则是一个双向链表，由于LinkedHashMap是直接继承自HashMap的，所以哈希表的维护结构就在HashMap中代码里进行，在LinkedHashMap中仅进行双链表的维护，这样也能很好的划分职能，使得代码结构更加清晰。
两个哈希表插入同样元素，使用同样的变量方式进行遍历，HashMap的得到的是无序结构，而LinedHashMap得到的是跟插入顺序一致的结构，而产生这样的区别的根源就在于LinkedHashMap中的那个双向链表。
LinkdeHashMap的插入和删除
如果没看过源码，会想LinkedHashMap应该是通过重写put和remove方法来实现的，但事实上LinkedHashMap并没有覆盖插入和删除方法，这一点可以通过观察LinkedHashMap代码结构发现。
put方法
既然没有覆盖put方法，调用LinkdeHashMap中put方法为什么会跟HashMap中put方法得到结构不一样呢？让我们看一下put方法。
//插入新的值，主要调用putVal方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//插入新值核心函数
//如果参数onlyIfAbsent是true，那么不会覆盖相同key的值value
//如果evict是false表示是在初始化时候调用的此函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//首先检查table是否为null并且容量是否大于0，即有没有初始化table
//如果没有初始化就进行resize
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//先定位到桶的位置，p为该桶的头结点
//如果p为null则说明该桶还没有节点，直接将新的键值对存入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
//newNode方法被LinkdeHashMap重写了
tab[i] = newNode(hash, key, value, null);
//p不为null，即发生了hash碰撞，进一步处理
else {
Node<K,V> e; K k;
//比较头结点的扰动值，及key的值
//如果相同则说明存入接地昂key已经存在，而且就是头结点
//先获取该接地昂，是否覆盖其值进一步处理
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//头结点的key和插入的key不相同
//先判断桶内数据结构是否是红黑树，如果是则以红黑树的方式插入到树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//桶内节点不是红黑树，即链表结构
else {
//循环遍历链表
//直到找到与插入节点key相同的节点，如果没有找到直接插入到尾结点
for (int binCount = 0; ; ++binCount) {
//已经遍历到尾结点，说明插入的key不存在，直接插入到尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果桶内节点数量达到了树型化阈值，则进行树型化，
//因为binCount从0开始所以TREEIFY_THRESHOLD-1
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//插入的key已存在，先获取该节点，是否覆盖其值进一步处理
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果获取到节点不为null则进行操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
//方法出入的onlyIfAbsennt参数为false，获取旧值为null则直接替换掉旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkdeHashMap的关键方法，HashMap中是空方法
afterNodeAccess(e);
return oldValue;
}
}
//以上操作及全部完成，并且已经成功插入或者更改一个节点的值
//修改modCount的值，记录修改次数
++modCount;
//更新size,并且判断是否超过阈值则进行扩容
if (++size > threshold)
resize();
//LinkdeHashMap的关键方法，HashMap中是空方法
afterNodeInsertion(evict);
return null;
}
//HashMap的newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
//LinkdeHashMap的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;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
在put方法中调用putVal方法时，其中tab[i] = newNode(hash, key, value, null);被LinkedHashMap覆盖了,还有两个值的注意的方法：
//元素访问之后调用
afterNodeAccess(e);
//元素被插入之后调用
afterNodeInsertion(evict);
这个两个方法分别在元素被访问之后和元素被插入之后调用，而这两个回调方法，在HashMap中没有具体实现，只有一个空壳，留给LinkdeHashMap来覆盖，以下是HashMap中的定义：
// Callbacks to allow LinkedHashMap post-actions
//节点访问后
void afterNodeAccess(Node<K,V> p) { }
//节点插入后
void afterNodeInsertion(boolean evict) { }
//节点删除后
void afterNodeRemoval(Node<K,V> p) { }
以下是LinkdeHashMap的实现这几个方法的实现：
//节点删除后的操作
void afterNodeRemoval(Node<K,V> e) { // unlink
//将e转为LinkedHashMap.Entry，获取他的上一个节点b，下一个节点a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//将p的上下节点都释放掉
p.before = p.after = null;
//如果上一个节点是空，那么说明p节点是头结点，去掉之后a节点变为链表头部，否则就是b节点的下一个指向a节点
if (b == null)
head = a;
else
b.after = a;
//判断尾部的情况
if (a == null)
tail = b;
else
a.before = b;
}
//节点插入后进行双链表的调整，插入节点会判断是否需要移除链表头节点，默认实现是不移除，可以通过继承LinkdeHashMap并覆盖removeEldesEntry改变这个特性
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//removeEldestEntry()方法默认是false
//意思是是否删掉最旧的元素，头节点是最旧的元素，如果在缓存时候使用可以被用到
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//在节点被访问之后进行双链表的调整(仅在accessOrder为true时候进行，把当前元素移动到尾部)
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
现在在梳理一下逻辑，插入节点的时候，会调用覆盖过的newNode方法，将插入的元素连接到链表尾部，删除节点的时候，改节点的前后节点相连即可，当节点被访问时，可以将其放到链表尾部。
删除remove
以下是HashMap的删除方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
//LinkedHashMap使用
afterNodeRemoval(node);
return node;
}
}
return null;
}
其中afterNodeRemoval(上面已经有对该方法的注释)方法就是LinkdeHashMap使用会进行双向链表节点的移动
LinkdeHashMap的构造方法
//构造一个空的保持插入顺序的LinkedHashMap实例，使用指定的initialCapacity和loadFactor
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//构造一个空的保持插入顺序的LinkedHashMap实例，使用指定容量，默认负载因子(0.75)
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//构造一个空的保持插入顺序的LinkedHashMap，使用默认容量16和默认负载因子0.75
public LinkedHashMap() {
super();
accessOrder = false;
}
//使用指定Map的所有映射构造一个保持插入顺序的LinkedHashMap实例，使用默认的装载因子和可以容纳指定map中所有映射的合适的容量。
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
//使用指定的容量负载因子和指定顺序(true是访问顺序，false是插入顺序)来创建一个空的LinkedMap实例
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkdeHashMap与HashMap的区别
LinkedHashMap是HashMap的子类，他们最大的区别是，HashMap的迭代是无序的，而LinkedHashMap是有序的，并且有按照插入顺序和访问顺序两种方式(默认是按照插入顺序)，为了实现有序的迭代，LinkedHashMap相比HashMap，额外维护了一个双向链表。
网友评论