摘要：擴展的節點包括和，加入兩個域組織額外的雙向鏈表保存順序。實現迭代器相關邏輯，因為迭代器是根據雙向鏈表順序迭代的。

HashMap作為一種經典的數據結構，其根據key定位元素能達到平均O(1)的時間復雜度。 但是，存儲于HashMap中的元素顯然是無序的，遍歷HashMap的順序得看臉。。。
那如何使得HashMap里的元素變得有序呢？一種思路是，將存放HashMap元素的節點，使用指針將他們串起來。換言之，就像在HashMap里面“嵌入”了一個鏈表一樣。
實際上，jdk的LinkedHashMap就是使用這種思路實現的。

LinkedHashMap中的代碼不算多，這是因為，jdk的設計使用繼承復用了代碼，在jdk的設計中，LinkedHashMap是HashMap的擴展：

public class LinkedHashMap
    extends HashMap
    implements Map
{
    /* ... */
}

回想一下HashMap的實現方式中，將key和value打包成的節點有兩種：
第一種，傳統分離鏈表法的鏈表節點。

static class Node implements Map.Entry {
    /* ... */
}

第二種，HashMap為進行優化，一定情況下會將鏈表重構為紅黑樹。第二種節點是紅黑樹節點：

static final class TreeNode extends LinkedHashMap.Entry {
    /* ... */
}

突然發現，HashMap的TreeNode是繼承至LinkedHashMap的Entry的。。。
個人觀點是jdk這種做法不是很優雅，本身LinkedHashMap繼承HashMap就使得兩者之間的邏輯混在了一起，而這里的內部實現又反過來繼承，邏輯搞得很混亂。

LinkedListHashMap需要將節點串成一個“嵌入式”雙向鏈表，因此需要給這兩種節點增加兩個字段：

static class Entry extends HashMap.Node {
    Entry before, after;
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

擴展HashMap.Node，增加雙向鏈表字段。
由于TreeNode是繼承自LinkedListMap.Entry的，所以它也有這兩個字段。

再來看下LinkedHashMap中的屬性，很少：

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry tail;

記錄雙向鏈表的表頭和表尾。從注釋中可以看出，head節點是最老的，tail節點是最新的，也即鏈表按照由老到新的順序串起來。

最后，由于LinkedHashMap是可以設置它組織元素的順序。一種是鏈表中的元素是按插入時候的順序排序，另外一種是按照訪問的順序排序。

// 指定順序是按照訪問順序來，還是插入順序來
final boolean accessOrder;

這個accessOrder指定是否按插入順序來。

由于對Map中的節點進行了擴展，因此，在創建節點時不能使用原來的節點了，而應該使用重新創建后的。
HashMap將創建節點的操作抽取出來放到了多帶帶的函數中，LinkedHashMap重寫即可：

    Node newNode(int hash, K key, V value, Node e) {
        LinkedHashMap.Entry p =
            new LinkedHashMap.Entry(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    Node replacementNode(Node p, Node next) {
        LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;
        LinkedHashMap.Entry t =
            new LinkedHashMap.Entry(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    // HashMap的TreeNode是繼承自LinkedHashMap.Entry的，因此能夠參與組織雙向鏈表
    TreeNode newTreeNode(int hash, K key, V value, Node next) {
        TreeNode p = new TreeNode(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    TreeNode replacementTreeNode(Node p, Node next) {
        LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;
        TreeNode t = new TreeNode(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

接下來，則需要在LinkedHashMap的操作時維護雙向鏈表。

回顧下HashMap的源代碼，我們知道，HashMap在刪除節點后，會調用afterNodeRemoval函數。
這個函數在HashMap中是空的，實際上jdk是將它設計為一個hook，果然，在LinkedHashMap中，就重寫了該函數，在其中維護雙向鏈表：

// 當有節點被刪除（即有元素被移除），那么也要將它從雙向鏈表中移除
void afterNodeRemoval(Node e) { // unlink
    LinkedHashMap.Entry p =
        (LinkedHashMap.Entry)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

按照類似的思路，HashMap中在插入元素后會調用afterNodeInsertion，那是不是LinkedHashMap也在這里實現了相關邏輯，插入元素后維護雙向鏈表節點呢？

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

然而，實際上在LinkedHashMap中該函數似乎沒有什么用。因為：

protected boolean removeEldestEntry(Map.Entry eldest) {
    return false;
}

removeEldestEntry始終返回false，afterNodeInsertion相當于什么也沒做。這個邏輯設計目的是什么，還不能很清楚。也許也是為了讓誰去繼承？以后再探究。

那插入元素后的在哪里維護了雙向鏈表呢？回到之前的newNode和newTreeNode：

Node newNode(int hash, K key, V value, Node e) {
    LinkedHashMap.Entry p =
        new LinkedHashMap.Entry(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

TreeNode newTreeNode(int hash, K key, V value, Node next) {
    TreeNode p = new TreeNode(hash, key, value, next);
    linkNodeLast(p);
    return p;
}

// 尾插雙向鏈表節點
private void linkNodeLast(LinkedHashMap.Entry p) {
    LinkedHashMap.Entry last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

由于HashMap中調用newNode時候都是為了裝新插入的元素，所以在這里維護雙向鏈表。
感覺耦合是不是太緊了。。。如果HashMap由于某個操作需要臨時搞個newNode借用下，豈不是會出問題？

下面是replacementNode和replacementTreeNode。
replacementNode在HashMap中的作用是，該K V之前是被TreeNode包裝的，現在需要拿Node包裝它。這也勢必會影響雙向鏈表的結構，所以這里也需要額外維護下。

獲取的時候，同樣，是重寫了`afterNodeAccess`鉤子，這樣在HashMap的獲取邏輯結束后，這里的邏輯會被執行，維護雙向鏈表。
void afterNodeAccess(Node e) { // move node to last
    LinkedHashMap.Entry last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)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中的順序有訪問序和插入序，只有訪問序才需要在訪問的時候更新雙向鏈表結構。也即accessOrder為true才會執行這段邏輯。

最后，注意到：

++modCount;
}

一般來說，只有修改了Map結構的操作，才需要修改modCount以讓正在迭代的迭代器感知到了變化。
但是這里，由于迭代器是使用這里的“嵌入式”雙向鏈表進行迭代，而在這里會改變雙向鏈表的結構，若迭代器繼續迭代會造成不可預測的結果。
所以，這里需要改變modCount，阻止迭代器繼續迭代。

LinkedHashMap的一個典型應用場景是LRU算法。

由于現在夜已深，現在不敢熬夜身體吃不消，想睡覺了。所以這個坑以后再填

LinkedHashMap還有其它的一些實現細節，如：

clear的時候也要同時維護雙向鏈表；

根據雙向鏈表實現迭代器。

最后，總結下jdk中對LinkedHashMap中的實現思路：

擴展HashMap實現。

擴展HashMap的節點（包括Node和TreeNode），加入兩個域組織額外的雙向鏈表保存順序。

在產生插入、刪除、訪問的地方維護雙向鏈表，通過重寫某些方法實現。

實現迭代器相關邏輯，因為迭代器是根據雙向鏈表順序迭代的。