LinkedHashMap如何保证顺序性

2019-08-09 00:00:00 linkedhashmap 顺序 保证

一. 前言

先看一个例子,我们想在页面展示一周内的消费变化情况,用echarts面积图进行展示。如下:
《LinkedHashMap如何保证顺序性》

我们在后台将数据构造完成

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原理(一) 概念和底层架构》,《HashMap原理(二) 扩容机制及存取原理》。

LinkedHashMap可以说是HashMap和LinkedList的集合体,既使用了HashMap的数据结构,又借用了LinkedList双向链表的结构(关于LinkedList可参考Java集合 LinkedList的原理及使用),那么这样的结构如何实现的呢,我们看一下LinkedHashMap的类结构
《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到底什么关系呢。
《LinkedHashMap如何保证顺序性》

看上面的结构图,定义了头结点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原理(二) 扩容机制及存取原理》中已经有说明,我们主要关注于其中的不同点

/**
 * 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的解释,以及常用方法的阐释,若有不对之处,请批评指正,望共同进步,谢谢!

相关文章