HashMap的結(jié)構(gòu)式數(shù)組+單向鏈表，LinkedHashMap繼承自HashMap，在原有的基礎(chǔ)上新增了四個主要元素，并重寫了一些HashMap的方法

/**
* 元素
*/
head    //根結(jié)點
before   //前節(jié)點
after    //后節(jié)點
accessOrder //  true-訪問順序  false-插入順序
/**
* 方法
*/
newNode()
replacementNode()
newTreeNode()
replacementTreeNode()
afterNodeRemoval()
afterNodeInsertion()
afterNodeAccess()

所以LinkedHashMap維護(hù)了一個雙向鏈表，并且該鏈表定義了迭代順序，下面分析一下他的存儲方式和結(jié)構(gòu)

LinkedHashMap的構(gòu)造方法均調(diào)用了super()，就是調(diào)用了HashMap的構(gòu)造方法，不過在之后給accessOrder賦值了，默認(rèn)為false

LinkedHashMap并沒有選擇重寫put方法，回顧下HashMap的put方法
put

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);   //1.重寫  
        else {
         //忽略部分代碼
          ...
        }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); //2.重寫
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict); //3.重寫
        return null;

在來看看LinkedHashMap重寫的方法
1.newNode

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMapEntry<K,V> p =
            new LinkedHashMapEntry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

 private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p; //1
        else {
            p.before = last; //2
            last.after = p; //3
        }
    }

主要代碼還是在linkNodeLast中，如果第一次添加或者添加的元素都被清空了，那last==null成立，會給head賦值成為根結(jié)點，之后的put里，last==null永遠(yuǎn)不會成立，通過2、3兩次賦值組成一個雙向鏈表

雙向鏈表結(jié)構(gòu).png

再看看put方法中注釋3的重寫方法，注釋2中的方法會在get的時候被調(diào)用，晚點在看

//這個方法也是HashMap專門為LinkedHashMap提供的，在某些條件下會刪除最早添加進(jìn)來的數(shù)據(jù)
void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMapEntry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

put方法和HashMap的差異并不大，主要的改變是如果選擇順序為訪問順序，那么在get的時候會改變鏈表的節(jié)點位置，方法如下

public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
/**
*accessOrder指的就是順序，默認(rèn)是插入順序，如果是訪問順序的話，會調(diào)用afterNodeAccess
*看到了吧，如果是訪問順序的話，那么每次get，都會重新對鏈表進(jìn)行位置交換
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        //tail保存的是鏈表尾部，因為如果是訪問順序，get后的節(jié)點都會從尾部插入
        //p=當(dāng)前節(jié)點e，那么b=p的上一個節(jié)點，a=p的下一個節(jié)點
        //如果p是根結(jié)點，那么b一定為null，如果p是尾節(jié)點，那么a一定為null
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<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;
        }
    }

用圖片解釋一下轉(zhuǎn)換的過程，如果get的是最后一個的話，那鏈表是不會有變化的
改變節(jié)點的變化如下

結(jié)構(gòu)變化圖.png

其它的方法沒有細(xì)看過，只看了主要的get方法，大家有興趣可以去看看