LinkedHashMap如何保证顺序性(2)

我们发现除了多了一个变量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方法

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/3eb4244de1c9d5f59a015a258f1dceca.html