LinkedHashMap 的工作原理（Android 7.1源码）

简介

LinkedHashMap继承于HashMap，由于HashMap并不能按照插入的顺序进行遍历，所以后来就有了LinkedHashMap。

怎样保存插入的顺序呢

    private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        LinkedHashMapEntry<K,V> before, after;
        ...
    }

在前面的HashMap篇中我们讲过HashMapEntry，在LinkedHashMap中就对于这个HashMapEntry再封装了一下，添加了before、after两个指针，这两个指针就是用于保存插入顺序的。

插入顺序如何保存的呢

    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> old = table[bucketIndex];
        LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

在前面的HashMap篇中我们讲过插入数据中会调用CreateEntry，LinkedHashMap重写了这一方法，增加了一步addBefore()方法，方法简单不再赘述。

怎么遍历时按照插入顺序呢

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        LinkedHashMapEntry<K,V> nextEntry    = header.after;
        LinkedHashMapEntry<K,V> lastReturned = null;

        ...

        public boolean hasNext() {
            return nextEntry != header;
        }
        ...

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            LinkedHashMapEntry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }

通过LinkedHashIterator，然后通过header的指向的双向链表遍历，达到插入的顺序遍历。