3.LinkedHashMap

LinkedHashMap是继承了HashMap，在维护HashMap的数组，链表，红黑树的基础上，加入了一个双向链表，让插入的数据，根据时间的先后，有了顺序。

transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

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

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

每当创建节点的时候，无论是树节点，还是链表节点，都会调用linkNodeLast，然后进行节点的双向的绑定。

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

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

其他操作与hashMap一样

不同的是forEach方法

hashmap维护的数组是很大的，所以遍历起来就会很慢，而LinkedHashMap直接遍历节点，所以更快。

//LinkedHashMap的
public void forEach(BiConsumer<? super K, ? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key, e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
//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;
            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();
        }
    }

test

public static void main(String[] args) {
        LinkedHashMap<Integer,Integer> linkedHashMap = new LinkedHashMap<>();
        for(int i = 0 ; i < 10; i++){
            linkedHashMap.put(i,i);
        }
        long start = System.nanoTime();
        linkedHashMap.forEach((K,V)->{System.out.print(V);});
        long end = System.nanoTime();
        System.out.println();
        System.out.println(end - start);
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i = 0 ; i < 10; i++){
            hm.put(i,i);
        }
        System.out.println();
        start = System.nanoTime();
        hm.forEach((K,V)->{System.out.print(V);});
        end = System.nanoTime();
        System.out.println();
        System.out.println(end - start);
    }

结果

0123456789
55960500

0123456789
476600

总结，相比于HashMap，LinkedHashMap在增删的上会慢，但是在遍历上有优势。因为LinkedHashMap的get方法是调用了HashMap的方法，所以get方法的速率应该是一样的。