源码的魅力 - LinkedHashMap 的工作原理

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

简介

LinkedHashMap继承于HashMap，前面文章中我们解析了HashMap的原理（需要的可以打开历史文章进行查看），由于HashMap中的Entry数组是无序的，但是在一些情况下我们需要保存数据的插入顺序或者访问顺序，所以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()方法，方法简单不再赘述，总之就是将每一个entry通过head与after连在一起。

怎么按照指定的顺序遍历呢

    LinkedHashMap<String, String> map = new LinkedHashMap();
    Set<Map.Entry<String, String>> set = map.entrySet();
    Iterator<Map.Entry<String, String>> iterator = set.iterator();
    while (iterator.hasNext()) {
          Map.Entry<String, String> entry = iterator.next();
    } 

通过使用entrySet方法来获取Entry的Set集合再通过Iterator来进行遍历。

entrySet方法的内部实现

    //上面的map.entrySet()方法最终会调用LinkedHashMap的newEntryIterator方法
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new     EntryIterator(); }
    //而EntryIterator 又继承自LinkedHashIterator，然后通过nextEntry来调用
    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { return nextEntry(); }
    }
    //LinkedHashIterator内部nextEntry方法也是通过after指针一步一步访问
    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;
        }
    }

map.entrySet()方法最终会调用LinkedHashMap的newEntryIterator方法，然后再调用EntryIterator的next方法，内部是调用父类的LinkedHashIterator的nextEntry方法，然后通过header的指向的双向链表after一步一步遍历。