LinkedHashMap了解一下
前言
本文使用用的是jdk1.8
LinkedHashMap类继承图
我们先来了解一下LinkedHashMap的继承实现图吧。
LinkedHashMap简述
归纳整理一下：
- 底层实现是散列表和双向链表。其实LinkedHashMap就是HashMap和LinkedList结合。底层还是HashMap，只是各节点Entry另外的还添加了两个属性before和after，通过双向列表来链接。
- 迭代有序。默认就是链表的元素插入顺序，可通过accessOrder变量修改迭代顺序，是插入顺序还是访问顺序。
- 当映射中已经存在key对应的一组Entry。再来一组key对应的Entry插入，会替换掉原来的Entry。元素顺序不受影响。
- 使用LinkedHashMap可以不用像HashMap一样元素杂乱无序，而保证元素一定的有序性，做到TreeMap的功能却不用TreeMap的成本。
- 提供了
LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)这个构造函数来构建LinkedHashMap，这样的LinkedHashMap的元素迭代顺序是从最近访问最少到最多(LRU算法)。 - 和HashMap一样允许键值为NULL的元素。
- 由于增加了双向链表的维护，大多数情况下其性能很可能比 HashMap 稍逊一筹。不过有一点例外的是LinkedHashMap 的 元素集迭代所需时间与映射Entry的数量 成比例，因为其迭代的时候是对其维护的双向列表进行迭代，有几个Entry迭代几次，而不是迭代其桶数。HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量成比例。
- 和HashMap一样有两个重要参数影响它的性能，初始容量和加载因子。为初始容量选择非常高的值对LinkedHashMap的影响比对 HashMap 要小，因为此类的迭代时间不受容量的影响，所以影响程度减少一些，但其他方面还是会有影响。
- 该类是非同步的。如果要使用该映射需要外部手动同步。或者在其初始化的时候外部封装
Map m = Collections.synchronizedMap(new LinkedHashMap(...))。 - 在按插入顺序组成的LinkedHashMap中，修改Entry的key对应的value不是结构修改。
- 在按访问顺序组成的LinkedHashMap中，仅通过get函数访问元素就已经算结构修改了。
LinkedHashMap的属性
image
注释给出的解释很清楚，和LinkedHashMap继承HashMap一样，我们知道HashMap维护的是一个单链表。而LinkedHasshMap对其的扩展就是保证了元素的有序性，其维护的是一个双向链表。即图中Entry，其多了两个属性before和after即双向链表中节点的前驱指针后后继指针。
更多的它还维护了两个节点变量即head和tail，即双向链表的头尾指针，保证了迭代的时候性能。这一点和LinkedList的实现一致。所以说根本上LinkedHashMap就是LinkedList和HashMap的一种结合实现。有HashMap存取增删时的性能，同时规避了HashMap迭代时性能的缺陷，有LinkedList迭代时的性能优势。
accessOrder属性则代表着LinkedHashMap的迭代顺序。该变量默认情况下是false，即代表插入顺序。为true的时候代表LinkedHashMap的迭代顺序是访问顺序(最近最久未使用优先)。在LinkedHashMap构造的时候统一赋值。
LinkedHashMap的构造函数
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;
}
LinkedHashMap有5个构造函数，根本上都是调用了其父类HashMap的构造函数，唯一不同的就是多了一个accessOrder变量的赋值。上面我们已经对accessOrder进行了解读
LinkedHashMap常见Api解析
put(K key, V value)
image
可以从类结构图中看出。LinkdeHashMap的所有put函数都是继承自自己的父类HashMap，AbstractMap以及实现的Map接口。
我们知道HashMap的put函数的具体逻辑最后都封装到了putVal函数中。而putVal函数中节点的创建则落在了newNode函数中。由于LinkedHashMap重写了newNode函数，所以新创的节点链接在内部双向链表的尾部。
get(Object key)
image
可以从LinkedHashMap类结构图看出其重写了HashMap的get函数和getOrDefault函数，继承了getNode函数。
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;
}
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
LinkedHashMap重写了get()和getOrDefault()函数。调用继承自HashMap的getNode函数来找到哈希表中key对应的Entry。
对比HashMap中的实现,LinkedHashMap只是增加了在成员变量(构造函数时赋值)accessOrder为true的情况下，要去回调afterNodeAccess(Node<K,V> e)函数的判断。
HashMap的实现：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;//原尾节点
// 如果accessOrder 是true ，且原尾节点不等于e
if (accessOrder && (last = tail) != e) {
// 节点e强转成双向链表节点p
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// p现在是尾节点， 后置节点一定是null
p.after = null;
// 如果p的前置节点是null，则p以前是头结点，所以更新现在的头结点是p的后置节点a
if (b == null)
head = a;
else // 否则更新p的前直接点b的后置节点为 a
b.after = a;
// 如果p的后置节点不是null，则更新后置节点a的前置节点为b
if (a != null)
a.before = b;
else // 如果原本p的后置节点是null，则p就是尾节点。 此时 更新last的引用为 p的前置节点b
last = b;
if (last == null) // 原本尾节点是null 则，链表中就一个节点
head = p;
else { // 否则 更新 当前节点p的前置节点为 原尾节点last， last的后置节点是p
p.before = last;
last.after = p;
}
// 尾节点的引用赋值成p
tail = p;
// 修改modCount。
++modCount;
}
}
需要注意的是：
afterNodeAccess()函数中，会修改modCount变量,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
remove(Object key)
image
LinkedHashMap也没有重写remove()方法，因为它的删除逻辑和HashMap并无区别。
在remove函数中无论是节点的查找时的逻辑判断以及真正的节点删除时的逻辑处理在单链表以及双向链表中的逻辑都是一致的，
但它重写了afterNodeRemoval()这个回调方法。该方法会在真正封装了删除逻辑的Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)方法中回调，用来保证双向链表的结构性。并且该remove函数(5参)会在所有涉及到删除节点的方法中被调用因为其是删除节点操作的真正执行者。
containsValue(Object value)
它重写了该方法，相比HashMap的实现，更为高效。
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
遍历一遍链表，去比较有没有value相等的节点，并返回
HashMap实现：
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
双重for循环。相对低效
LinkedHashMap只重写了HashMap的containsValue函数并没有重写其containsKey函数。是因为如果按containsValue的重写逻辑来做，需要遍历整个KeySet来找。
而HashMap的实现是通过hash算法来找的。效率要高很多
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
afterNode *()
我们在看HashMap源码的时候就曾看到这些函数的存在。注释也给的很清楚，专门为LinkedHashMap准备的回调函数。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
从LinkedHashMap中也可以看出也确实重写了这三个函数。分别作用在函数的访问，插入和删除后的回调。
image
afterNodeAccess函数在LinkedHashMap指定迭代顺序是访问顺序的时候获取元素时会回调。来保证双向链表的顺序。
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);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
-
afterNodeInsertion：回调函数，新节点插入之后回调，根据evict来 判断是否需要删除最早插入的节点。如果实现LruCache会用到这个方法。 -
removeEldestEntry：LinkedHashMap中默认返回false 则不删除最早节点。 返回true 代表要删除最早的节点。通常构建一个LruCache会在达到Cache的上限时返回true
afterNodeInsertion(boolean evict)以及removeEldestEntry(Map.Entry<K,V> eldest)是构建LruCache需要的回调，在LinkedHashMap里可以忽略它们。
LinkedHashIterator()
image
从图中可以看出HashMap的迭代规则是遍历哈希表。从第一个桶存在元素的桶开始遍历。所以当初始容量大了之后，桶数也会上去。迭代的时候数据量就会上去
而LinkedHashMap迭代时是迭代的双向链表。从head节点开始一直到tail结束。并不是遍历每个桶，只是遍历双向链表的每个节点。所以受初始容量影响小。
LinkedHashMap 示意图；
总结
LinkedHashMap继承了HashMap，相比于HashMap仅重写了几个方法，以改变它迭代遍历时的顺序。这也是其与HashMap相比最大的不同。
在每次插入数据，或者访问、修改数据时，会增加节点、或者调整链表的节点顺序。以决定迭代时输出的顺序。
- accessOrder ,默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。为true时，可以在这基础之上构建一个LruCache.
- LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法.在每次构建新节点时，将新节点链接在内部双向链表的尾部
- accessOrder=true的模式下,在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。值得注意的是，afterNodeAccess()函数中，会修改modCount,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
- nextNode() 就是迭代器里的next()方法 。
该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。以满足按照插入顺序输出，还是访问顺序输出。 - 它与HashMap比，还有一个小小的优化，重写了containsValue()方法，直接遍历内部链表去比对value值是否相等。
