前言

今天寫(xiě)一下經(jīng)常拿來(lái)與HashMap對(duì)比的LinkedHashMap源碼分析。那么LinkedHashMap存在的意義在哪？我們從HashMap文章里可以知道HashMap是無(wú)序的再悼，而LinkedHashMap正是為了解決這一問(wèn)題的镊绪。LinkedHashMap是繼承自HashMap诱建，因此HashMap的相關(guān)操作其實(shí)在HashMap中都已經(jīng)實(shí)現(xiàn)了。它對(duì)于HashMap的擴(kuò)展主要是其內(nèi)部還維護(hù)了一個(gè)雙向鏈表鞭缭，在每次插入數(shù)據(jù)，或者訪問(wèn)魏颓、修改數(shù)據(jù)時(shí)缚去，會(huì)增加節(jié)點(diǎn)、或調(diào)整鏈表的節(jié)點(diǎn)順序琼开。以決定迭代時(shí)輸出的順序易结，也就是說(shuō)LinkedHashMap在HashMap的基礎(chǔ)上實(shí)現(xiàn)了有序性。
（以下分析注重于LinkedHashMap的對(duì)于HashMap擴(kuò)展）

對(duì)于Node的封裝

LinkedHashMap中Entry<K,V>繼承于Map.Node，在父類(lèi)基礎(chǔ)上增加了before與aftre用于實(shí)現(xià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);
        }
    }

accessOrder字段

構(gòu)造函數(shù)增加了accessOrder字段搞动，用于標(biāo)記迭代順序是否與訪問(wèn)順序有關(guān)
accessOrder為false：迭代時(shí)輸出的順序是插入節(jié)點(diǎn)的順序（先->后）
accessOrder為true：迭代時(shí)輸出的順序是訪問(wèn)節(jié)點(diǎn)的順序（元素每次被訪問(wèn)都置于尾部）

重寫(xiě)newNode方法

每次put元素躏精，都將其他置于雙向鏈表尾部

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

實(shí)現(xiàn)HashMap中用于回調(diào)的三個(gè)鉤子方法

在相應(yīng)操作發(fā)生后得到回調(diào)，更新雙向鏈表
void afterNodeAccess(Node<K,V> p) { } // 訪問(wèn)（查）
void afterNodeInsertion(boolean evict) { } // 插入（增）
void afterNodeRemoval(Node<K,V> p) { } // 移除（刪）

afterNodeAccess方法

每當(dāng)有元素被訪問(wèn)時(shí)鹦肿，更新集合順序

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) { // accessOrder為true且末尾不是當(dāng)前傳入節(jié)點(diǎn)
    // 刪除節(jié)點(diǎn)在雙向鏈表中的位置
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // p現(xiàn)在是尾節(jié)點(diǎn)矗烛，所以after為null
    p.after = null;
    // 如果b為null，表示p以前是頭節(jié)點(diǎn)
        if (b == null)
            head = a; // 將頭節(jié)點(diǎn)設(shè)置為a
        else
            b.after = a; // 將下個(gè)節(jié)點(diǎn)設(shè)置為a
    // 如果a不是null箩溃，則更新其前置節(jié)點(diǎn)為b
        if (a != null)
            a.before = b;
    // a為null表示p以前是尾節(jié)點(diǎn)瞭吃，將last設(shè)置為b
        else
            last = b; 
    // a與b均為null，則表示之前鏈表只有一個(gè)節(jié)點(diǎn)
        if (last == null)
            head = p;
        else { // 否則將p放到末尾
            p.before = last;
            last.after = p;
        }
        tail = p; // 更新尾節(jié)點(diǎn)
        ++modCount; // 修改modCount
    }
}

afterNodeInsertion方法

根據(jù) evict與removeEldestEntry返回值判斷是否需要?jiǎng)h除最早添加的節(jié)點(diǎn)（最老）,其實(shí)就是LRUCache的實(shí)現(xiàn)涣旨，LRUCache就是利用了LinkedHashMap

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
// evict 默認(rèn)為true歪架，在put方法中得知
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false; // 默認(rèn)不刪除
}

afterNodeRemoval方法

在刪除元素后同時(shí)將其他從雙向鏈表中移除

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) // 目標(biāo)節(jié)點(diǎn)之前是頭
        head = a; // 將頭節(jié)點(diǎn)設(shè)置為a
    else
        b.after = a;
    if (a == null) // 目標(biāo)節(jié)點(diǎn)之前是尾
        tail = b; // 將尾設(shè)置為b
    else
        a.before = b;
}

重寫(xiě)get等方法

重寫(xiě)了相關(guān)查詢方法，在條件滿足情況下調(diào)用afterNodeAccess

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

重寫(xiě)containsValue

利用雙向鏈表循環(huán)霹陡，比HashMap的雙重循環(huán)高效

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

元素迭代

使用雙向鏈表和蚪，保證有序性

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;
    ......
// 從雙向鏈表表頭開(kāi)始循環(huán)
    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;
    }
｝

特性總結(jié)

LinkedHashMap是HashMap子類(lèi)，在父類(lèi)基礎(chǔ)上維護(hù)了雙向鏈表烹棉，重寫(xiě)了相關(guān)方法攒霹，保證集合元素的有序性（重寫(xiě)newNode方法，每次put元素放置到雙向鏈表尾部浆洗；重寫(xiě)查詢相關(guān)方法催束，保證能夠?qū)⒈辉L問(wèn)元素置于雙向鏈表尾部；重寫(xiě)了afterNodeAccess伏社、afterNodeInsertion抠刺、afterNodeRemoval方法，順序調(diào)整回調(diào)洛口，操作雙向鏈表）
提供了accessOrder屬性矫付，可設(shè)置元素順序是否與訪問(wèn)順序有關(guān)
優(yōu)化了containsValue方法，直接使用雙向鏈表進(jìn)行循環(huán)查找
Android中LruCache的實(shí)現(xiàn)即是通過(guò)LinkedHashMap進(jìn)行實(shí)現(xiàn)
（LRU（Least recently used第焰，最近最少使用）算法）