Java 源码分析 数据结构

简介

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

数据结构

　　同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)方法。接下来看看是如何记录顺序的。

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

查找节点

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

本文由 Administrator 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站部分文章采集自互联网，因某些原因未注明出处，如有侵权，请留言告知。