Java Map原理备忘(二)

接上一次Java Map原理备忘。
LinkedHashMap继承HashMap实现Map接口。
LinkedHashMap比HashMap多维护一个包含所有条目的双向链表。

    /**
     * 双链表的每一个节点，两个指针分别指向前一个节点和后一个节点。
     */
    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);
        }
    }

    /**
     * 双链表的头节点
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 双链表的尾节点
     */
    transient LinkedHashMap.Entry<K,V> tail;

LinkedHashMap重新了newNode和newTreeNode方法，当执行put操作添加新节点时，会把节点插入到尾节点后面，并把尾节点执行该节点。

    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;
    }

    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    // 把节点插入到尾节点后面，并把尾节点执行该节点
    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;
        }
    }

map.keySet()，map.values()和map.entrySet()遍历条目时通过遍历双链表来遍历。保证遍历出来的条目顺序跟插入时的顺序一样。如果条目时重复插入，条目顺序不变。

参考衔接
https://www.baeldung.com/java-linked-hashmap