LinkedHashMap 如何保证插入顺序的(jdk8)

HashMap 大家知道,索引是(length-1) & hash 算出来的,是无序的,那么LinkedHashList是如何保证顺序的呢?

答案就是LInkedHashMap的一个内部类,可以看到这个是一个双向列表,那下个问题,是如何维护呢?

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

那想想之前的HashMap里有一些未实现的方法

    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

看名称其实就是在访问,插入和删除后的操作,这个其实就是为了LInkedHashMap维护链表而调用的,如果没有这些方法,LInkedHashMap就要重写putVal方法,这很没必要。挑一个方法来看。

    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;
        // 前驱节点为空,那么该节点的后继节点就为head
        if (b == null)
            head = a;
        // 不为空,前驱节点的后继节点为该节点的后继节点
        else
            b.after = a;
        // 后继节点为空,尾巴就是前驱节点
        if (a == null)
            tail = b;
        //不为空,则后继节点的前驱节点,为该节点的前驱节点
        else
            a.before = b;
    }

接下来就是foreach遍历了,可以看下和LInkedHashMap是重写了这个方法的,和HashMap的不同

    //HashMap:
    public void forEach(BiConsumer<? super K, ? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            //  是用tab循环
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key, e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }


    //LInkedHashMap
    public void forEach(BiConsumer<? super K, ? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        //遍历的是这个双向链表,从head开始,所以是有序的,就是插入顺序
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key, e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
上一篇:java-如何保存LinkedHashMap?


下一篇:javascript-仅当元素失去焦点时才调用onChange