Java - LinkedHashMap 源码阅读笔记

in Tech Java

简介

  LinkedHashMap提供带顺序HashMap。可以基于插入顺序访问顺序来进行遍历。直接继承HashMap,并实现Map接口。其核心是重写了newNode()、newTreeNode()这两个方法及Entry、TreeNode类。在实例化节点后,使用双向链表来记录数据的插入顺序。通过accessOrder变量来控制使用插入顺序还是访问顺序。

数据结构

  同HashMap一致。
HashMap

源码

构造方法

    public LinkedHashMap() {
        // 直接调用HashMap
        super();
        // false 插入顺序,先入先出;true 访问顺序,最新访问的最后出。
        accessOrder = false;
    }
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        // 控制使用插入顺序还是访问顺序
        this.accessOrder = accessOrder;
    }

新增or修改节点

  直接调用HashMap中的put(K key, V value)方法。接下来看看是如何记录顺序的。

    // LinkedHashMap重写了newNode()方法
    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;
    }
    // 使用双向链表来记录节点顺序
    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;
        }
    }
    static class Entry<K,V> extends HashMap.Node<K,V> {
        //before指向上一个链表节点;after指向下一个链表节点。
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

查找节点

    public V get(Object key) {
        Node<K,V> e;
        // 直接调用HashMap的方法
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            // 默认是插入顺序。这里将链表节点移到链尾,来实现访问顺序。最新访问的最后出。
            afterNodeAccess(e);
        return e.value;
    }

    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;
            // 断开p节点的链接
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            // 插入到链尾
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

删除节点

  直接调用HashMap中删除相关方法即可。删除节点之后回调afterNodeRemoval(Node<K,V> p)方法,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.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }