LinkedHashMap如何保证顺序性

一. 前言

先看一个例子，我们想在页面展示一周内的消费变化情况，用echarts面积图进行展示。如下：


我们在后台将数据构造完成
HashMap<String, Integer> map = new HashMap<>(); map.put("星期一", 40);
map.put("星期二", 43); map.put("星期三", 35); map.put("星期四", 55); map.put("星期五", 45);
map.put("星期六", 35); map.put("星期日", 30);
然而页面上一展示，发现并非如此，我们打印出来看，发现顺序并非我们所想，先put进去的先get出来
for (Map.Entry<String, Integer> entry : map.entrySet()){
System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
} /** * 结果如下： * key: 星期二, value: 40 * key: 星期六, value: 35 * key: 星期三, value: 50
* key: 星期四, value: 55 * key: 星期五, value: 45 * key: 星期日, value: 65 * key: 星期一,
value: 30 */
那么如何保证预期展示结果如我们所想呢，这个时候就需要用到LinkedHashMap实体。

二. 初识LinkedHashMap

首先我们把上述代码用LinkedHashMap进行重构
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(); map.put("星期一",
40); map.put("星期二", 43); map.put("星期三", 35); map.put("星期四", 55); map.put("星期五",
45); map.put("星期六", 35); map.put("星期日", 30); for (Map.Entry<String, Integer>
entry : map.entrySet()){ System.out.println("key: " + entry.getKey() + ",
value: " + entry.getValue()); }
这个时候，结果正如我们所预期
key: 星期一, value: 40 key: 星期二, value: 43 key: 星期三, value: 35 key: 星期四, value:
55 key: 星期五, value: 45 key: 星期六, value: 35 key: 星期日, value: 30

LinkedHashMap继承了HashMap类，是HashMap的子类，LinkedHashMap的大多数方法的实现直接使用了父类HashMap的方法，关于HashMap在前面的章节已经讲过了，
《HashMap原理(一) 概念和底层架构》 <https://www.cnblogs.com/LiaHon/p/11142958.html>，
《HashMap原理(二) 扩容机制及存取原理》 <https://www.cnblogs.com/LiaHon/p/11149644.html>。


LinkedHashMap可以说是HashMap和LinkedList的集合体，既使用了HashMap的数据结构，又借用了LinkedList双向链表的结构（关于LinkedList可参考
Java集合 LinkedList的原理及使用 <https://www.cnblogs.com/LiaHon/p/11107245.html>
）,那么这样的结构如何实现的呢，我们看一下LinkedHashMap的类结构



我们看到LinkedHashMap中定义了一个Entry静态内部类，定义了5个构造器，一些成员变量，如head，tail，accessOrder，并继承了HashMap的方法，同时实现了一些迭代器方法。我们先看一下Entry类
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); } }

我们看到这个静态内部类很简单，继承了HashMap的Node内部类，我们知道Node类是HashMap的底层数据结构，实现了数组+链表/红黑树的结构，而Entry类保留了HashMap的数据结构，同时通过before，after实现了双向链表结构（HashMap中Node类只有next属性，并不具备双向链表结构）。那么before，after和next到底什么关系呢。



看上面的结构图，定义了头结点head，当我们调用迭代器进行遍历时，通过head开始遍历，通过before属性可以不断找到下一个，直到tail尾结点，从而实现顺序性。而在同一个hash（在上图中表现了同一行）链表内部after和next效果是一样的。不同点在于before和after可以连接不同hash之间的链表。

前面我们发现数据结构已经完全支持其顺序性了，接下来我们再看一下构造方法，看一下比起HashMap的构造方法是否有不同。
// 构造方法1，构造一个指定初始容量和负载因子的、按照插入顺序的LinkedList public LinkedHashMap(int
initialCapacity, float loadFactor) { super(initialCapacity, loadFactor);
accessOrder = false; } // 构造方法2，构造一个指定初始容量的LinkedHashMap，取得键值对的顺序是插入顺序 public
LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder =
false; } // 构造方法3，用默认的初始化容量和负载因子创建一个LinkedHashMap，取得键值对的顺序是插入顺序 public
LinkedHashMap() { super(); accessOrder = false; } //
构造方法4，通过传入的map创建一个LinkedHashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值
public LinkedHashMap(Map<? extends K, ? extends V> m) { super(m); accessOrder =
false; } // 构造方法5，根据指定容量、装载因子和键值对保持顺序创建一个LinkedHashMap public LinkedHashMap(int
initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
我们发现除了多了一个变量accessOrder之外，并无不同，此变量到底起了什么作用？
/** * The iteration ordering method for this linked hash map: <tt>true</tt> *
for access-order, <tt>false</tt> for insertion-order. * * @serial */ final
boolean accessOrder;

通过注释发现该变量为true时access-order，即按访问顺序遍历，如果为false，则表示按插入顺序遍历。默认为false，在哪些地方使用到该变量了，同时怎么理解？我们可以看下面的方法介绍

二. put方法


前面我们提到LinkedHashMap的put方法沿用了父类HashMap的put方法，但我们也提到了像LinkedHashMap的Entry类就是继承了HashMap的Node类，同样的，HashMap的put方法中调用的其他方法在LinkedHashMap中已经被重写。我们先看一下HashMap的put方法，这个在
《HashMap原理(二) 扩容机制及存取原理》 <https://www.cnblogs.com/LiaHon/p/11149644.html>
中已经有说明，我们主要关注于其中的不同点
/** * Implements Map.put and related methods * * @param hash hash for key *
@param key the key * @param value the value to put * @param onlyIfAbsent if
true, don't change existing value * @param evict if false, the table is in
creation mode. * @return previous value, or null if none */ final V putVal(int
hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab;
Node<K,V> p; int n, i; /** *
如果当前HashMap的table数组还未定义或者还未初始化其长度，则先通过resize()进行扩容, * 返回扩容后的数组长度n */ if ((tab =
table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
//通过数组长度与hash值做按位与&运算得到对应数组下标，若该位置没有元素，则new Node直接将新元素插入 if ((p = tab[i = (n -
1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
//否则该位置已经有元素了，我们就需要进行一些其他操作 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不同的情况下，判断当前Node是否是TreeNode,如果是则执行putTreeVal将新的元素插入 * 到红黑树上。 */ else if (p
instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key,
value); //如果不是TreeNode,则进行链表遍历 else { for (int binCount = 0; ; ++binCount) {
/** * 在链表最后一个节点之后并没有找到相同的元素，则进行下面的操作，直接new Node插入， * 但条件判断有可能转化为红黑树 */ if ((e =
p.next) == null) { //直接new了一个Node p.next = newNode(hash, key, value, null); /**
* TREEIFY_THRESHOLD=8,因为binCount从0开始，也即是链表长度超过8（包含）时， * 转为红黑树。 */ if (binCount
>= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } /** *
如果在链表的最后一个节点之前找到key值相同的（和上面的判断不冲突，上面是直接通过数组 * 下标判断key值是否相同），则替换 */ 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为true时:当某个位置已经存在元素时不去覆盖 if (!onlyIfAbsent || oldValue == null)
e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount;
//最后判断临界值，是否扩容。 if (++size > threshold) resize(); afterNodeInsertion(evict);
return null; }
1. newNode方法

首先：LinkedHashMap重写了newNode()方法，通过此方法保证了插入的顺序性。
/** * 使用LinkedHashMap中内部类Entry */ 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; } /** * 将新创建的节点p作为尾结点tail， *
当然如果存储的第一个节点，那么它即是head节点，也是tail节点，此时节点p的before和after都为null *
否则，建立与上一次尾结点的链表关系，将当前尾节点p的前一个节点（before）设置为上一次的尾结点last, *
将上一次尾节点last的后一个节点（after）设置为当前尾结点p * 通过此方法实现了双向链表功能，完成before,after,head,tail的值设置
*/ 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; } }
2. afterNodeAccess方法


其次：关于afterNodeAccess()方法，在HashMap中没给具体实现，而在LinkedHashMap重写了，目的是保证操作过的Node节点永远在最后，从而保证读取的顺序性，在调用put方法和get方法时都会用到。
/** * 当accessOrder为true并且传入的节点不是最后一个时，将传入的node移动到最后一个 */ void
afterNodeAccess(Node<K,V> e) { //在执行方法前的上一次的尾结点 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：当前节点 //b：当前节点的前一个节点 //a：当前节点的后一个节点；
//将p.after设置为null，断开了与后一个节点的关系，但还未确定其位置 p.after = null; /** *
因为将当前节点p拿掉了，那么节点b和节点a之间断开了，我们先站在节点b的角度建立与节点a *
的关联，如果节点b为null,表示当前节点p是头结点，节点p拿掉后，p的下一个节点a就是头节点了； * 否则将节点b的后一个节点设置为节点a */ if (b
== null) head = a; else b.after = a; /** *
因为将当前节点p拿掉了，那么节点a和节点b之间断开了，我们站在节点a的角度建立与节点b *
的关联，如果节点a为null,表示当前节点p为尾结点，节点p拿掉后，p的前一个节点b为尾结点， *
但是此时我们并没有直接将节点p赋值给tail,而是给了一个局部变量last(即当前的最后一个节点)，因为 *
直接赋值给tail与该方法最终的目标并不一致；如果节点a不为null将节点a的前一个节点设置为节点b * * （因为前面已经判断了(last = tail)
!= e，说明传入的节点并不是尾结点，既然不是尾结点，那么 * e.after必然不为null，那为什么这里又判断了a == null的情况？ *
以我的理解，java可通过反射机制破坏封装，因此如果都是反射创建出的Entry实体，可能不会满足前面 * 的判断条件） */ if (a != null)
a.before = b; else last = b; /** * 正常情况下last应该也不为空，为什么要判断，原因和前面一样 *
前面设置了p.after为null,此处再将其before值设置为上一次的尾结点last,同时将上一次的尾结点 * last设置为本次p */ if
(last == null) head = p; else { p.before = last; last.after = p; }
//最后节点p设置为尾结点，完事 tail = p; ++modCount; } }
我们前面说到的linkNodeLast(Entry e)方法和现在的afterNodeAccess(Node
e)都是将传入的Node节点放到最后，那么它们的使用场景如何呢？

在前面讲解HashMap时，提到了HashMap的put流程，如果在对应的hash位置上还没有元素，那么直接new
Node()放到数组table中，这个时候对应到LinkedHashMap中，调用了newNode()方法，就会用到linkNodeLast()，将新node放到最后，而如果对应的hash位置上有元素，进行元素值的覆盖时，就会调用afterNodeAccess()，将原本可能不是最后的node节点拿到了最后。如
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("1月", 20); //此时就会调用到linkNodeLast()方法，也会调用afterNodeAccess()方法，但会被阻挡在
//if (accessOrder && (last = tail) != e) 之外 map.put("2月", 30); map.put("3月",
65); map.put("4月", 43);
//这时不会调用linkNodeLast()，会调用afterNodeAccess()方法将key为“1月”的元素放到最后 map.put("1月",
35); //这时不会调用linkNodeLast()，会调用afterNodeAccess()方法将key为“2月”的元素放到最后
map.get("2月"); //调用打印方法 for (Map.Entry<String, Integer> entry :
map.entrySet()){ System.out.println("key: " + entry.getKey() + ", value: " +
entry.getValue()); }
结果如下：
key: 3月, value: 65 key: 4月, value: 43 key: 1月, value: 35 key: 2月, value: 30
而如果是执行下面这段代码，将accessOrder改为false
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, false);
map.put("1月", 20); //此时就会调用到linkNodeLast()方法，也会调用afterNodeAccess()方法，但会被阻挡在
//if (accessOrder && (last = tail) != e) 之外 map.put("2月", 30); map.put("3月",
65); map.put("4月", 43);
//这时不会调用linkNodeLast()，会调用afterNodeAccess()方法将key为“1月”的元素放到最后 map.put("1月",
35); map.get("2月"); //调用打印方法 for (Map.Entry<String, Integer> entry :
map.entrySet()){ System.out.println("key: " + entry.getKey() + ", value: " +
entry.getValue()); }
结果如下：
key: 1月, value: 35 key: 2月, value: 30 key: 3月, value: 65 key: 4月, value: 43

大家看到区别了吗，accessOrder为false时，你访问的顺序就是按照你第一次插入的顺序；而accessOrder为true时，你任何一次的操作，包括put、get操作，都会改变map中已有的存储顺序。

3. afterNodeInsertion方法

我们看到在LinkedHashMap中还重写了afterNodeInsertion(boolean
evict)方法，它的目的是移除链表中最老的节点对象，也就是当前在头部的节点对象，但实际上在JDK8中不会执行，因为removeEldestEntry方法始终返回false。看源码：
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; }
三. get方法

LinkedHashMap的get方法与HashMap中get方法的不同点也在于多了afterNodeAccess()方法
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; }
在这里就不再多讲了，getNode()方法在HashMap章节已经讲过，而前面刚把afterNodeAccess讲了。

四.remove方法


remove方法也直接使用了HashMap中的remove，在HashMap章节并没有讲解，因为remove的原理很简单，通过传递的参数key计算出hash，据此可找到对应的Node节点，接下来如果该Node节点是直接在数组中的Node，则将table数组该位置的元素设置为node.next；如果是链表中的，则遍历链表，直到找到对应的node节点，然后建立该节点的上一个节点的next设置为该节点的next。

LinkedHashMap重写了其中的afterNodeRemoval(Node
e)，该方法在HashMap中没有具体实现，通过此方法在删除节点的时候调整了双链表的结构。
void afterNodeRemoval(Node<K,V> e) { LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//将待删除节点的before和after都设置为null p.before = p.after = null; /** *
如果节点b为null，表示待删除节点p为头部节点，该节点拿掉后，该节点的下一个节点a就为头部节点head *
否则设置待删除节点的上一个节点b的after属性为节点a */ if (b == null) head = a; else b.after = a; /**
* 如果节点a为null，表示待删除节点p为尾部节点，该节点拿掉后，该节点的上一个节点a就为尾部节点tail *
否则设置待删除节点的下一个节点a的before属性为节点b */ if (a == null) tail = b; else a.before = b; }
五. 总结


LinkedHashMap使用的也较为频繁，它基于HashMap，用于HashMap的特点，又增加了双链表的结构，从而保证了顺序性，本文主要从源码的角度分析其如何保证顺序性，accessOrder的解释，以及常用方法的阐释，若有不对之处，请批评指正，望共同进步，谢谢！

• « 上一篇：Cloud Studio初体验（一）
• » 下一篇：还在美化博客吗？试试一键更换博客主题吧！