LinkedHashMap源码分析

继之前看完hashMap的源码之后，最近又看以了一下LinkedHashMap的源码。发现LinkedHash的代码很简单，他是HashMap的子类，自然具有父类的所以特性，除此之外他也有自己的特点。详细来说，它包含两种数据结构：1、从父类HashMap继承来的数据链表结构(见HashMap源码分析这篇文章)。2、自己的双向循环链表结构。前一种数据结构的由来显而易见，后一种数据结构是怎么实现的呢？这久要从LinkedMap的对象创建说起：
LinkedHashMap最简单的构造函数是这样的：

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

看出跟双向链表又任何关系，关键是下面这个方法：

   @Override
    void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

这个方法是对HashMap中的init的覆盖，在HashMap的构造方法中调用。注意这里的Entry类是LinkedHashMap继承HashMap.Entry类的实现类：

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

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

成员变量多了before和after，还增加了一个addBefore方法。双向链表的初始化就是init方法中这行代码：

   header.before = header.after = header;

即这个双向链表初始化完之后，只有一个header节点，header节点的key、value都为null。初始化完之后的结构是这样的：

再向LinkedHashMap添加一个元素之后的结构是这样的：

依次类推，最近添加的节点在最前面，紧跟在header节点之后。LinkedHashMap双向链表元素的添加主要是下面这段代码：

    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

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

LinkedHashMap的这两个方法也是对HashMap的方法的覆盖，是由HashMap的put方法引起的调用。
LinkedHashMap的构造说完了，那它又是怎么迭代遍历元素的呢？同样LinkedHashMap实现了自己的迭代器：

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

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

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

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }

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

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

同样关键是nextEntry方法，故知LinkedHashMap是按照元素的放入顺序来迭代的，如果按before来迭代就是逆向迭代了。
LinkedHashMap作为一种特殊的HashMap，它也有随机访问的特性。看它的get方法代码：

    public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

跟HashMap的大同小异，访问方式同HashMap(见HashMap源码分析)。这个recordAccess方法值得注意，源码：

    void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

从代码来看，若构造LinkedHashMap的时候accessOrder=true，那么在每次调用get访问的元素都会放到链表的最前端，即把最后后一次get访问的元素放在最前面，这种情况下LinkedHashMap就不是按元素的放入顺序来存放的，而是最近访问的在最前面。

Chin的博客

程序的世界多奇妙

LinkedHashMap源码分析

Comments