目的

JDK中已經(jīng)有了HashMap為什么還需要有個LinkedHashMap呢张吉？答案相信大家也知道鸽疾，HashMap是無序的凌箕，而LinkedHashMap是有序的怨喘。那么當HashMap變成LinkedHashMap后它是如何去存儲的气忠？查詢的性能是否是發(fā)生了變化沥阱，如果沒有供炼，它是怎么做到保證了查詢性能的同時又保證了順序的崇摄？這篇文章將深入LinkedHashMap源碼對以上問題進行剖析拉鹃，在了解LinkedHashMap源碼之前請先看《HashMap源碼詳解》辈赋，我們將在它的基礎上進行講解，因為90%都是由HashMap實現(xiàn)的膏燕，對于HashMap的源碼實現(xiàn)部分將直接粗略帶過不再進行細講

HashMap與LinkedHashMap數(shù)據(jù)結構對比

首先炭庙，LinkedHashMap繼承了HashMap，而且LinkedHashMap中定義了三個新字段分別是head煌寇、tail和accessOrder焕蹄，我們將在后面講解它們的作用

LinkedHashMap_UML.png

同時，LinkedHashMap的table使用的也是HashMap的table阀溶，但是LinkedHashMap的table實現(xiàn)類并沒有使用HashMap.Node腻脏，而是使用繼承了HashMap.Node的Entry類鸦泳，Entry類新增了兩個字段before和after，將在后面講解它們的作用

HashMap.Node_UML.png

LinkedHashMap.Node_UML.png

put方法

LinkedHashMap使用的put(K key, V value)繼承至HashMap永品，所以不再進行講解

putVal方法

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);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

LinkedHashMap使用的putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)同樣繼承至HashMap做鹰，所以同樣不再進行講解，這段代碼里面有三個方法是需要講解的分別是第7行的newNode(hash, key, value, null)鼎姐、第33行的afterNodeAccess(e)和第40行的afterNodeInsertion(evict)钾麸，這三個方法LinkedHashMap都進行了重寫

newNode方法

// HashMap.class中的實現(xiàn)
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

// LinkedHashMap.class中的實現(xiàn)
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;
    }
}

HashMap中的newNode(int hash, K key, V value, Node<K,V> next)新創(chuàng)建的數(shù)據(jù)存儲類是HashMap.Node，而LinkedHashMap重寫了該方法炕桨，創(chuàng)建的數(shù)據(jù)存儲類是LinkedHashMap.Entry饭尝。同時在LinkedHashMap中還調用了linkNodeLast(LinkedHashMap.Entry<K,V> p)將LinkedHashMap中的head和tail指向新建的數(shù)據(jù)存儲類，如果又新建一個LinkedHashMap.Entry則將新LinkedHashMap.Entry添加至鏈表尾部

LinkedHashMap.Entry本身是鏈表結構献宫，head和tail分別指向鏈表的頭部和尾部钥平，同時它們也是LinkedHashMap為什么能保證與插入順序一致的原因所在

afterNodeAccess方法

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        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;
    }
}

LinkedHashMap支持兩種排序，一種是默認的按插入順序排序姊途，一種是按最近最少使用排序（LRU）涉瘾。按插入順序排序好理解，這里解釋下按最近最少使用排序（LRU）捷兰，意思是將最近最少使用過的或最少訪問過的排在最前面立叛，方便以后進行淘汰和刪除，經(jīng)常訪問或使用的放在最后面贡茅。那如何才能做到呢秘蛇，其實很簡單就是元素每被使用或訪問過后就把它放到最后面，當經(jīng)過一段時間后經(jīng)常被使用或訪問的就都在后面了友扰，越前面的就表示越?jīng)]被使用或訪問過的彤叉。
afterNodeAccess(Node<K,V> e)就是為了按最近最少使用排序（LRU）而存在庶柿，當accessOrder為true時村怪，默認為false，就會啟用按最近最少使用排序（LRU）算法浮庐，會將最近被使用過或訪問過的元素放到鏈表的最后面甚负，從而改變了原來鏈表的順序也就改變了默認的按插入順序排序

putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)添加新元素也算是被使用訪問，所以當accessOrder為true审残，這時使用的是按最近最少使用排序（LRU）梭域，那么就會將元素移動到最后

afterNodeInsertion方法

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

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

afterNodeInsertion(boolean evict)在HashMap中是空實現(xiàn)，也是留給LinkedHashMap實現(xiàn)的一個鉤子搅轿，該方法的作用是是否刪除最老的元素病涨，在LinkedHashMap中不管是按插入順序排序還是按最近最少使用排序（LRU）在鏈表最前面的就是最老的或最少使用的，所以會將頭部第一個元素進行刪除璧坟。
當是從put(K key, V value)進來時evict是true但是LinkedHashMap中的removeEldestEntry(Map.Entry<K,V> eldest)永遠返回false所以在LinkedHashMap中該方法不會觸發(fā)

remove方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

LinkedHashMap使用的remove(Object key)同樣繼承至HashMap既穆，所以同樣不再進行講解赎懦，這段代碼里面唯一也有一個方法是需要講解的就是afterNodeRemoval(node)，該方法在LinkedHashMap中進行了重寫

afterNodeRemoval方法

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

當從table中刪除了元素后幻工，LinkedHashMap同時調用afterNodeRemoval(Node<K,V> e)刪除維持順序的鏈表中的元素

總結

當LinkedHashMap進行查詢的時候調用的同樣是HashMap的查詢方法励两，同樣是根據(jù)需要查詢的key進行哈希取值從table中進行查找，當我們需要按順序輸出時囊颅，則通過LinkedHashMap中維護的鏈表頭head到鏈表尾tail便能進行順序輸出

傳送門

GitHub該系列教程項目地址当悔，同步更新：
https://github.com/ChenZhiB/tutorial

LinkedHashMap源碼詳解