摘要：擴(kuò)展的節(jié)點(diǎn)包括和，加入兩個(gè)域組織額外的雙向鏈表保存順序。實(shí)現(xiàn)迭代器相關(guān)邏輯，因?yàn)榈魇歉鶕?jù)雙向鏈表順序迭代的。

HashMap作為一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，其根據(jù)key定位元素能達(dá)到平均O(1)的時(shí)間復(fù)雜度。 但是，存儲(chǔ)于HashMap中的元素顯然是無(wú)序的，遍歷HashMap的順序得看臉。。。
那如何使得HashMap里的元素變得有序呢？一種思路是，將存放HashMap元素的節(jié)點(diǎn)，使用指針將他們串起來(lái)。換言之，就像在HashMap里面“嵌入”了一個(gè)鏈表一樣。
實(shí)際上，jdk的LinkedHashMap就是使用這種思路實(shí)現(xiàn)的。

LinkedHashMap中的代碼不算多，這是因?yàn)?，jdk的設(shè)計(jì)使用繼承復(fù)用了代碼，在jdk的設(shè)計(jì)中，LinkedHashMap是HashMap的擴(kuò)展：

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

回想一下HashMap的實(shí)現(xiàn)方式中，將key和value打包成的節(jié)點(diǎn)有兩種：
第一種，傳統(tǒng)分離鏈表法的鏈表節(jié)點(diǎn)。

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

第二種，HashMap為進(jìn)行優(yōu)化，一定情況下會(huì)將鏈表重構(gòu)為紅黑樹(shù)。第二種節(jié)點(diǎn)是紅黑樹(shù)節(jié)點(diǎn)：

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

突然發(fā)現(xiàn)，HashMap的TreeNode是繼承至LinkedHashMap的Entry的。。。
個(gè)人觀點(diǎn)是jdk這種做法不是很優(yōu)雅，本身LinkedHashMap繼承HashMap就使得兩者之間的邏輯混在了一起，而這里的內(nèi)部實(shí)現(xiàn)又反過(guò)來(lái)繼承，邏輯搞得很混亂。

LinkedListHashMap需要將節(jié)點(diǎn)串成一個(gè)“嵌入式”雙向鏈表，因此需要給這兩種節(jié)點(diǎn)增加兩個(gè)字段：

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

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

再來(lái)看下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節(jié)點(diǎn)是最老的，tail節(jié)點(diǎn)是最新的，也即鏈表按照由老到新的順序串起來(lái)。

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

// 指定順序是按照訪問(wèn)順序來(lái)，還是插入順序來(lái)
final boolean accessOrder;

這個(gè)accessOrder指定是否按插入順序來(lái)。

由于對(duì)Map中的節(jié)點(diǎn)進(jìn)行了擴(kuò)展，因此，在創(chuàng)建節(jié)點(diǎn)時(shí)不能使用原來(lái)的節(jié)點(diǎn)了，而應(yīng)該使用重新創(chuàng)建后的。
HashMap將創(chuàng)建節(jié)點(diǎn)的操作抽取出來(lái)放到了多帶帶的函數(shù)中，LinkedHashMap重寫(xiě)即可：

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

接下來(lái)，則需要在LinkedHashMap的操作時(shí)維護(hù)雙向鏈表。

回顧下HashMap的源代碼，我們知道，HashMap在刪除節(jié)點(diǎn)后，會(huì)調(diào)用afterNodeRemoval函數(shù)。
這個(gè)函數(shù)在HashMap中是空的，實(shí)際上jdk是將它設(shè)計(jì)為一個(gè)hook，果然，在LinkedHashMap中，就重寫(xiě)了該函數(shù)，在其中維護(hù)雙向鏈表：

// 當(dāng)有節(jié)點(diǎn)被刪除（即有元素被移除），那么也要將它從雙向鏈表中移除
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;
}

按照類(lèi)似的思路，HashMap中在插入元素后會(huì)調(diào)用afterNodeInsertion，那是不是LinkedHashMap也在這里實(shí)現(xiàn)了相關(guān)邏輯，插入元素后維護(hù)雙向鏈表節(jié)點(diǎn)呢？

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

然而，實(shí)際上在LinkedHashMap中該函數(shù)似乎沒(méi)有什么用。因?yàn)椋?/p>

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

removeEldestEntry始終返回false，afterNodeInsertion相當(dāng)于什么也沒(méi)做。這個(gè)邏輯設(shè)計(jì)目的是什么，還不能很清楚。也許也是為了讓誰(shuí)去繼承？以后再探究。

那插入元素后的在哪里維護(hù)了雙向鏈表呢？回到之前的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;
}

// 尾插雙向鏈表節(jié)點(diǎn)
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中調(diào)用newNode時(shí)候都是為了裝新插入的元素，所以在這里維護(hù)雙向鏈表。
感覺(jué)耦合是不是太緊了。。。如果HashMap由于某個(gè)操作需要臨時(shí)搞個(gè)newNode借用下，豈不是會(huì)出問(wèn)題？

下面是replacementNode和replacementTreeNode。
replacementNode在HashMap中的作用是，該K V之前是被TreeNode包裝的，現(xiàn)在需要拿Node包裝它。這也勢(shì)必會(huì)影響雙向鏈表的結(jié)構(gòu)，所以這里也需要額外維護(hù)下。

獲取的時(shí)候，同樣，是重寫(xiě)了`afterNodeAccess`鉤子，這樣在HashMap的獲取邏輯結(jié)束后，這里的邏輯會(huì)被執(zhí)行，維護(hù)雙向鏈表。
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中的順序有訪問(wèn)序和插入序，只有訪問(wèn)序才需要在訪問(wèn)的時(shí)候更新雙向鏈表結(jié)構(gòu)。也即accessOrder為true才會(huì)執(zhí)行這段邏輯。

最后，注意到：

++modCount;
}

一般來(lái)說(shuō)，只有修改了Map結(jié)構(gòu)的操作，才需要修改modCount以讓正在迭代的迭代器感知到了變化。
但是這里，由于迭代器是使用這里的“嵌入式”雙向鏈表進(jìn)行迭代，而在這里會(huì)改變雙向鏈表的結(jié)構(gòu)，若迭代器繼續(xù)迭代會(huì)造成不可預(yù)測(cè)的結(jié)果。
所以，這里需要改變modCount，阻止迭代器繼續(xù)迭代。

LinkedHashMap的一個(gè)典型應(yīng)用場(chǎng)景是LRU算法。

由于現(xiàn)在夜已深，現(xiàn)在不敢熬夜身體吃不消，想睡覺(jué)了。所以這個(gè)坑以后再填

LinkedHashMap還有其它的一些實(shí)現(xiàn)細(xì)節(jié)，如：

clear的時(shí)候也要同時(shí)維護(hù)雙向鏈表；

根據(jù)雙向鏈表實(shí)現(xiàn)迭代器。

最后，總結(jié)下jdk中對(duì)LinkedHashMap中的實(shí)現(xiàn)思路：

擴(kuò)展HashMap實(shí)現(xiàn)。

擴(kuò)展HashMap的節(jié)點(diǎn)（包括Node和TreeNode），加入兩個(gè)域組織額外的雙向鏈表保存順序。

在產(chǎn)生插入、刪除、訪問(wèn)的地方維護(hù)雙向鏈表，通過(guò)重寫(xiě)某些方法實(shí)現(xiàn)。

實(shí)現(xiàn)迭代器相關(guān)邏輯，因?yàn)榈魇歉鶕?jù)雙向鏈表順序迭代的。