在上一篇博客Java HashMap源碼簡(jiǎn)單解析（JDK 1.8）中，我們分析了HashMap的實(shí)現(xiàn)原理。HashMap內(nèi)部使用數(shù)組+鏈表（或紅黑樹）的形式。結(jié)點(diǎn)的key的hash值決定了該結(jié)點(diǎn)在數(shù)組中的位置（hash值前16位和后16位相與的值再和數(shù)組長(zhǎng)度減1相與，得到的值就是結(jié)點(diǎn)在數(shù)組中的位置），當(dāng)發(fā)生hash碰撞（也就是幾個(gè)結(jié)點(diǎn)都需要放在數(shù)組的同一個(gè)位置，就使用鏈表把他們連接起來）。

LinkedHashMap與HashMap最大的不同之處在于，HashMap存儲(chǔ)的數(shù)據(jù)是無序的，通過迭代器訪問的順序和插入的順序無關(guān)。而LinkedHashMap通過雙向鏈表將結(jié)點(diǎn)連接起來（有人說是循環(huán)鏈表，但是從JDK1.8的源碼來看并不是循環(huán)鏈表），可以通過雙向鏈表可以順序地訪問已存儲(chǔ)的結(jié)點(diǎn)（訪問順序可以是插入順序也可以是LRU順序）。

下面我們來看一下LinkedHashMap內(nèi)部是怎么實(shí)現(xiàn)的。

繼承關(guān)系

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

LinkedHashMap繼承了HashMap，并實(shí)現(xiàn)了Map接口

成員變量

     /**
     * 保存的頭結(jié)點(diǎn)
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 保存的尾結(jié)點(diǎn)
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * 是否按訪問順序排序
     */
    final boolean accessOrder;

LinkedHashMap內(nèi)部保存了雙向鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)，并且有一個(gè)標(biāo)志位accessOrder，用來確定是否按訪問順序排序。

結(jié)點(diǎn)

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

LinkedHashMap使用的結(jié)點(diǎn)繼承了HashMap的結(jié)點(diǎn)，在原來的基礎(chǔ)上增加了before和after兩個(gè)參數(shù)，通過著兩個(gè)參數(shù)可以使結(jié)點(diǎn)形成一個(gè)雙向鏈表。LinkedHashMap和HashMap最大的不同也就是怎么處理這兩個(gè)變量。

構(gòu)造方法

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }


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


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


    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }


    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

LinkedHashMap的構(gòu)造方法中都調(diào)用了HashMap的構(gòu)造方法，可以說從構(gòu)造方法來看，兩個(gè)差距不大。

put方法

你會(huì)發(fā)現(xiàn)在LinkedHashMap中找不到put方法，這是這時(shí)因?yàn)長(zhǎng)inkedHashMap直接使用了父類HashMap的put方法，他只重寫了Node<K,V> newNode(int hash, K key, V value, Node<K,V> e)方法。在HashMap中該方法就是創(chuàng)建了一個(gè)結(jié)點(diǎn)，我們看在LinkedHashMap中該方法做了什么工作。

    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);   //創(chuàng)建結(jié)點(diǎn)
        linkNodeLast(p);
        return p;
    }

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

從上面的代碼我們看出，newNode內(nèi)部也是先創(chuàng)建了一個(gè)結(jié)點(diǎn)，然后調(diào)用了LinkNodeLast函數(shù)。LinkNodeLast函數(shù)中將新結(jié)點(diǎn)插入到雙向鏈表的末尾，并更新head 和tail兩個(gè)成員變量。

put總結(jié)：LinkNodeLast和HashMap的put方法不同之處就是LinkNodeLast對(duì)于插入的每一個(gè)節(jié)點(diǎn)，都將其插入到雙向鏈表中。

get方法

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)          //根據(jù)hash值獲取結(jié)點(diǎn)
            return null;
        if (accessOrder)                                                //如果按照訪問順序排序，更新結(jié)點(diǎn)排序
            afterNodeAccess(e);
        return e.value;
    }


   void afterNodeAccess(Node<K,V> e) {                                            // 將結(jié)點(diǎn)放到雙向鏈表的最后
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

同樣的LinkedHashMap和HashMap的get操作最大的不同也是雙向鏈表這一點(diǎn)。在LinkedHashMap的get方法中，首先根據(jù)hash值獲得結(jié)點(diǎn)，如果雙向鏈表是根據(jù)訪問順序排序的，還需要對(duì)雙向鏈表重新排序，使最新訪問的結(jié)點(diǎn)在鏈表的最后。

迭代器

   abstract class LinkedHashIterator {
        LinkedHashMap.Entry<K,V> next;
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;

        LinkedHashIterator() {
            next = head;
            expectedModCount = modCount;
            current = null;
        }

        public final boolean hasNext() {
            return next != null;
        }

        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            next = e.after;
            return e;
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

由于LinkedHashMap內(nèi)部使用雙向鏈表來順序保存數(shù)據(jù)，所以在使用迭代器內(nèi)部也是通過在雙向鏈表上的移動(dòng)來訪問數(shù)據(jù)的。