浅析LinkedHashMap源码

青旅半醒 2022-12-05 09:53 237阅读 0赞

上一篇文章对[HashMap][]的重要属性和常用方法进行了详细的分析，`LinkedHashMap`很多东西都直接继承自HashMap，所以本文只分析一些`LinkedHashMap`的特性。`LinkedHashMap`通过维护双向链表解决了HashMap不能保持顺序插入和顺序遍历的问题，在一些场景下，这个特性很有用，比如缓存、LRU算法等。

##### 链表建立的过程 #####

因为LinkedHashMap直接继承自HashMap，数据插入的过程也是直接使用的是HashMap的方法，但是却不负责链表的维护。链表的建立过程是在插入键值对节点时开始的，初始情况下，让 `LinkedHashMap` 的 `head` 和 `tail` 引用同时指向新节点，链表就算建立起来了。随后不断有新节点插入，通过将新节点接在 `tail` 引用指向节点的后面，即可实现链表的更新。

/** * The head (eldest) of the doubly linked list. */
    transient LinkedHashMap.Entry<K,V> head;
    
    /** * The tail (youngest) of the doubly linked list. */
    transient LinkedHashMap.Entry<K,V> tail;

// HashMap 中实现
    public V put(K key, V value) { 
        return putVal(hash(key), key, value, false, true);
    }
    
    // HashMap 中实现
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) { 
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0) { ...}
        // 通过节点 hash 定位节点所在的桶位置，并检测桶中是否包含节点引用
        if ((p = tab[i = (n - 1) & hash]) == null) { ...}
        else { 
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode) { ...}
            else { 
                // 遍历链表，并统计链表长度
                for (int binCount = 0; ; ++binCount) { 
                    // 未在单链表中找到要插入的节点，将新节点接在单链表的后面
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) { ...}
                        break;
                    }
                    // 插入的节点已经存在于单链表中
                    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;
                if (!onlyIfAbsent || oldValue == null) { ...}
                afterNodeAccess(e);    // 回调方法，后续说明
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold) { ...}
        afterNodeInsertion(evict);    // 回调方法，后续说明
        return null;
    }
    
    // HashMap 中实现
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { 
        return new Node<>(hash, key, value, next);
    }
    
    // LinkedHashMap 中覆写
    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);
        // 将 Entry 接在双向链表的尾部
        linkNodeLast(p);
        return p;
    }
    
    // LinkedHashMap 中实现
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { 
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        // last 为 null，表明链表还未建立
        if (last == null)
            head = p;
        else { 
            // 将新节点 p 接在链表尾部
            p.before = last;
            last.after = p;
        }
    }

整段插入数据的源码最红要的是`Node<K,V> newNode(int hash, K key, V value, Node<K,V> e)`方法，LinkedHashMap复写了HashMap的方法，在这个方法中，LinkedHashMap建立了Entry，并通过 `linkNodeLast` 方法将 `Entry` 接在双向链表的尾部，实现了双向链表的建立。数据顺出插入之后，就可以顺序的去遍历了。

##### 链表节点删除的过程 #####

与插入操作一样，`LinkedHashMap` 删除操作相关的代码也是直接用父类的实现。在删除节点时，父类的删除逻辑并不会修复 `LinkedHashMap` 所维护的双向链表，而是在`LinkedHashMap`中复写了`afterNodeRemoval`方法。

// HashMap 中实现
    public V remove(Object key) { 
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    // HashMap 中实现
    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) { ...}
                else { 
                    // 遍历单链表，寻找要删除的节点，并赋值给 node 变量
                    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) { ...}
                // 将要删除的节点从单链表中移除
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);    // 调用删除回调方法进行后续操作
                return node;
            }
        }
        return null;
    }
    
    // LinkedHashMap 中覆写
    void afterNodeRemoval(Node<K,V> e) {  // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 将 p 节点的前驱后后继引用置空
        p.before = p.after = null;
        // b 为 null，表明 p 是头节点
        if (b == null)
            head = a;
        else
            b.after = a;
        // a 为 null，表明 p 是尾节点
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

总结一下删除的过程如下：

1.  根据 hash 定位到桶位置
2.  遍历链表或调用红黑树相关的删除方法
3.  从 LinkedHashMap 维护的双链表中移除要删除的节点

##### 顺序访问LinkedHashMap #####

默认情况下，LinkedHashMap 是按插入顺序维护链表。不过我们可以在初始化 LinkedHashMap，指定 accessOrder 参数为 true，即可让它按访问顺序维护链表。访问顺序的原理上并不复杂，当我们调用get/getOrDefault/replace等方法时，只需要将这些方法访问的节点移动到链表的尾部即可。

*  可以先看下构造方法

/** * Constructs an empty <tt>LinkedHashMap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) { 
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }

*  顺序访问的源码

// LinkedHashMap 中覆写
    public V get(Object key) { 
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        // 如果 accessOrder 为 true，则调用 afterNodeAccess 将被访问节点移动到链表最后
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
    
    // LinkedHashMap 中覆写
    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;
            // 如果 b 为 null，表明 p 为头节点
            if (b == null)
                head = a;
            else
                b.after = a;
                
            if (a != null)
                a.before = b;
            /* * 这里存疑，父条件分支已经确保节点 e 不会是尾节点， * 那么 e.after 必然不会为 null，不知道 else 分支有什么作用 */
            else
                last = b;
        
            if (last == null)
                head = p;
            else { 
                // 将 p 接在链表的最后
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

[HashMap]: https://blog.csdn.net/wangchengming1/article/details/108472515