一、Map 各自的適用場景

• 如果需要使用的Map中的key無序，選擇HashMap；

• 如果要求key有序，則選擇TreeMap。

  • 但是選擇TreeMap就會有性能問題，因?yàn)門reeMap的get操作的時(shí)間復(fù)雜度是O(log(n))的，相比于HashMap的O(1)還是差不少的，

• LinkedHashMap的出現(xiàn)就是為了平衡這些因素，使得 能夠以O(1)時(shí)間復(fù)雜度增加查找元素，又能夠保證key的有序性 此外，LinkedHashMap提供了兩種key的排序方式：

  1. 按照訪問順序排序（access order）?？梢允褂眠@種順序實(shí)現(xiàn)LRU（Least Recently Used）緩存
  • 因?yàn)槊看卧L問后的元素會被移到鏈表尾部，實(shí)現(xiàn) LRU 只需要移除 鏈?zhǔn)自?即可
    • 「一次訪問」的定義是什么？
      • put，putIfAbsent，get，getOrDefault，compute，computeIfAbsent，computeIfPresent或merge方法會導(dǎo)致訪問相應(yīng)的條目（假設(shè)它在調(diào)用完成后存在）。如果值被替換，替換方法只會導(dǎo)致條目的訪問
  2. 按照插入順序排序（insertion orde）。注：同一key的多次插入，并不會影響其順序。

注：WeakHashMap 也可以用于實(shí)現(xiàn)緩存，二者的使用場景不同。WeakHashMap無法像 LinkedHashMap 那樣自定義淘汰規(guī)則，它的元素會在 gc 的發(fā)生的時(shí)候被清除。

特別地，對 collection-view 的操作不會影響后臺映射的迭代順序。

• collection-view 是否類似于數(shù)據(jù)庫的視圖？

二、性能

LinkedHashMap 提供了所有可選的Map操作，并允許使用null元素。與HashMap一樣，假設(shè)散列函數(shù)能夠正確地在桶之間分散元素，它為基本操作（添加，包含和刪除）提供了恒定的性能。性能可能略低于HashMap的性能，這是因?yàn)?strong>維護(hù)鏈接列表的成本增加了，但有一個(gè)例外：對LinkedHashMap的collection-view的迭代需要時(shí)間與 map 的size 成比，而不關(guān)其capacity。迭代HashMap可能會更加昂貴，需要的時(shí)間與其capacity成正比。

LinkedHashMap 有兩個(gè)影響其性能的參數(shù)：初始容量和負(fù)載因子。它們的定義與HashMap完全相同。但請注意，對于此類，初始容量選擇過高值對性能的影響不會像HashMap那么嚴(yán)重，因?yàn)榇祟惖牡鷷r(shí)間不受容量影響，迭代只受到 size 的影響。

三、并發(fā)問題（fail-fast）

并發(fā)方式：推薦使用 Map m = Collections.synchronizedMap(new LinkedHashMap(...));進(jìn)行包裝。內(nèi)部是使用一個(gè)內(nèi)置鎖，各個(gè)方法的實(shí)現(xiàn)只是加鎖然后 調(diào)用原來的類。這最好在創(chuàng)建時(shí)就完成「包裝操作」，以防止意外的不同步訪問Map。

結(jié)構(gòu)性修改（A structural modification ） 是指

• 添加或刪除一個(gè)或多個(gè)映射的操作，
• 在訪問有序的LinkedHashMap的情況下會影響迭代順序。
• 在插入有序的LinkedHashMap 中，僅更改與已包含在映射中的鍵相關(guān)的值不是結(jié)構(gòu)修改。
• 在 access-ordered 模式下的 LinkedHashMap中，僅通過get查詢map就是一種結(jié)構(gòu)修改。

迭代遍歷過程中如果發(fā)現(xiàn)結(jié)構(gòu)性修改問題（使用 iterater#remove 方法產(chǎn)生的結(jié)構(gòu)性修改問題除外 ），馬上拋出ConcurrentModificationException，以免造成更大的損失。

「快速失敗」具體實(shí)現(xiàn)是怎么樣的呢？每趟遍歷完成之后都會調(diào)用 checkForComodification 方法進(jìn)行檢查

java.util.ArrayList.Itr#checkForComodification

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

四、實(shí)現(xiàn)

節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

主要基于HashMap的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

static class Entry<K,V> extends HashMap.Node<K,V> {
    //每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，指向前繼節(jié)點(diǎn)與后繼節(jié)點(diǎn)
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

雙向鏈表實(shí)現(xiàn)的LinkedHshMap，所以每個(gè)節(jié)點(diǎn)須在HashMap的基礎(chǔ)上添加指向前繼節(jié)點(diǎn)與后繼節(jié)點(diǎn)指針：before，after。

核心方法

HashMap 中定義了三個(gè)回調(diào)方法供 LinkedHashMap 重寫。

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

LinkedHashMap繼承于HashMap，重新實(shí)現(xiàn)了這3個(gè)函數(shù)，顧名思義這三個(gè)函數(shù)的作用分別是：節(jié)點(diǎn)訪問后、節(jié)點(diǎn)插入后、節(jié)點(diǎn)移除后做一些事情。

1.afterNodeRemoval

雙向鏈表刪除節(jié)點(diǎn)可以參考這樣思路。

// before p after

刪除 p

1.先處理 after 方向

if p 為第一個(gè)節(jié)點(diǎn) before == null head = after

else before.after = after

2.再處理 before 方向

if p 為最后一個(gè)節(jié)點(diǎn) after == null tail = before
else after.before = before;

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)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;
}

2.afterNodeInsertion

evict參數(shù)有什么用？

• if false, the table is in creation mode.
• Creation mode 是什么？剛剛創(chuàng)建時(shí)的模式？

HashMap#的 put 方法，調(diào)用 putVal 方法時(shí)，傳入的 evit 為 true。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

調(diào)用處傳遞 evict 全部為 true。

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

3.afterNodeAccess

與模式相關(guān) final boolean accessOrder

只能在構(gòu)造函數(shù)中指定，默認(rèn)為 false，

• true 表示按訪問順序排序
• false 表示按插入順序排序

把節(jié)點(diǎn)移到鏈表末尾。

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {//如果是按照訪問順序，并且 不是最后一個(gè)元素
        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;
    }
}

4.put

put put函數(shù)在LinkedHashMap中未重新實(shí)現(xiàn)，只是實(shí)現(xiàn)了afterNodeAccess和afterNodeInsertion兩個(gè)回調(diào)函數(shù)。

5.get

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

get函數(shù)重新實(shí)現(xiàn)并加入了afterNodeAccess來保證訪問順序

五、小結(jié)

1. 怎樣保證插入順序？ 使用前驅(qū)和后繼指針，使得原來的HashMap有序，在LinkedHashMap中覆蓋HashMap中newNode 方法，使得每次put數(shù)據(jù)時(shí)，新建的節(jié)點(diǎn)都是LinkedHashMap.Entry<K,v> 類型的，比普通的HsahMap.Entry 多一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼節(jié)點(diǎn)，使用前驅(qū)和后繼保證插入有序。
2. 怎么樣保證訪問順序？ 覆蓋父類HashMap的afterNodeAccess 方法，使得每次訪問后，都改變鏈表順序。使得原鏈表按訪問排序。將最新一次訪問的節(jié)點(diǎn)放到鏈表的最后。

六、參考資料與學(xué)習(xí)資源推薦

• 重識java-LinkedHashMap
• 官方文檔