LinkedHashMap

因?yàn)楣ぷ髦杏玫搅薒inkedHashMap來保證服務(wù)器初始化數(shù)據(jù)的順序事扭，但是卻不是很了解其特點(diǎn)和原理，今天特地翻一翻LinkedHashMap的源碼（JDK8）來看一看它究竟有什么不同棉饶。

首先，來看一下JDK的對(duì)LinkedHashMap的介紹：

Hash table and linked list implementation of the <tt>Map</tt> interface,with predictable iteration order. This implementation differs from <tt>HashMap</tt> in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (<i>insertion-order</i>). Note that insertion order is not affected if a key is <i>re-inserted</i> into the map.(A key <tt>k</tt> is reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to the invocation.)
哈希表和鏈表實(shí)現(xiàn)了Map接口魄眉，具有可預(yù)測(cè)的迭代順序（有序的）砰盐。這個(gè)實(shí)現(xiàn)與HashMap的不同之處在于，它維護(hù)一個(gè)貫穿其所有條目的雙鏈接列表坑律。這個(gè)鏈表定義了迭代順序岩梳，通常是鍵插入到映射中的順序(插入順序)。注意晃择，如果一個(gè)鍵重新插入到映射中冀值，插入順序不會(huì)受到影響。(map中put一個(gè)已經(jīng)插入過的key值宫屠，containsKey將返回true)

This implementation spares its clients from the unspecified, generally chaotic ordering provided by {@link HashMap} (and {@link Hashtable}), without incurring the increased cost associated with {@link TreeMap}. It can be used to produce a copy of a map that has the same order as the original, regardless of the original map's implementation:
這個(gè)實(shí)現(xiàn)使其客戶端免受{@link HashMap}(和{@link Hashtable})提供的未指定的列疗、通常混亂的排序（無序）浪蹂，而不會(huì)增加與{@link TreeMap}相關(guān)的成本抵栈。無論原始Map怎么實(shí)現(xiàn)，它都可以用來產(chǎn)生一個(gè)與原始Map具有相同的順序的Map副本:

 void foo(Map m) {
     Map copy = new LinkedHashMap(m);
     ...
 }

This technique is particularly useful if a module takes a map on input, copies it, and later returns results whose order is determined by that of the copy.(Clients generally appreciate having things returned in the same order they were presented.)
這個(gè)是一個(gè)特別有用的技術(shù)坤次，輸入一個(gè)map古劲，復(fù)制它，返回結(jié)果缰猴，它的順序取決于原復(fù)制對(duì)象产艾。 （客戶一般都傾向于返回順序跟插入順序一致）

A special {@link #LinkedHashMap(int,float,boolean) constructor} is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (<i>access-order</i>). This kind of map is well-suited to building LRU caches. Invoking the {@code put}, {@code putIfAbsent}, {@code get}, {@code getOrDefault}, {@code compute}, {@code computeIfAbsent}, {@code computeIfPresent}, or {@code merge} methods results in an access to the corresponding entry (assuming it exists after the invocation completes). The {@code replace} methods only result in an access of the entry if the value is replaced. The {@code putAll} method generates one entry access for each mapping in the specified map, in the order that key-value mappings are provided by the specified map's entry set iterator. <i>No other methods generate entry accesses.</i> In particular, operations on collection-views do <i>not</i> affect the order of iteration of the backing map.
提供了一個(gè)特殊的{@link LinkedHashMap（int，float，boolean）構(gòu)造函數(shù)}來創(chuàng)建LinkedHashMap闷堡，其迭代順序是上次訪問其條目的順序隘膘，從最少訪問到最遠(yuǎn)訪問（<I>存取順序</ i>的）。這種map非常適合構(gòu)建LRU緩存杠览。調(diào)用{@code put}弯菊，{@ code putIfAbsent}，{@code get}踱阿，{@ code getOrDefault}误续，{@ code compute}，{@ code computeIfAbsent}扫茅，{@ code computeIfPresent}或{@code merge}方法會(huì)導(dǎo)致訪問相應(yīng)的條目（假設(shè)它存在于調(diào)用完成）。如果替換了值育瓜，{@code replace}方法只會(huì)導(dǎo)致訪問該替換條目葫隙。 {@code putAll}方法為指定映射中的每個(gè)映射生成一個(gè)條目訪問，按照指定映射的條目集迭代器提供鍵 - 值映射的順序躏仇。 <i>沒有其他方法可以生成條目訪問恋脚。特別是，對(duì)集合視圖的操作 不 會(huì)影響后備映射的迭代順序焰手。

The {@link #removeEldestEntry(Map.Entry)} method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
可以重寫{@link removeEldestEntry（Map.Entry）}方法糟描，以強(qiáng)制在將新映射添加到map時(shí)自動(dòng)刪除過時(shí)映射的策略。

This class provides all of the optional <tt>Map</tt> operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and <tt>remove</tt>), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.
這個(gè)類提供了所有可選的映射操作书妻，并允許空元素船响。與HashMap一樣，它為基本操作(添加躲履， 包含和除去)提供恒定時(shí)間的性能见间，假設(shè)哈希函數(shù)將元素正確地分散到bucket中。性能可能僅略低于HashMap,因?yàn)槠湫枰S護(hù)鏈表的額外費(fèi)用,但有一個(gè)例外: 對(duì)LinkedHashMap的集合視圖的迭代需要的時(shí)間與Map的大小成比例工猜，而與它的容量無關(guān)米诉。在HashMap上的迭代可能更昂貴，需要的時(shí)間與其容量成比例篷帅。

A linked hash map has two parameters that affect its performance: <i>initial capacity</i> and <i>load factor</i>. They are defined precisely as for HashMap. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashMap, as iteration times for this class are unaffected by capacity.

一個(gè)鏈接哈希映射有兩個(gè)參數(shù)影響其性能:初始容量和負(fù)載因數(shù)史侣。它們的定義與HashMap一樣精確。但是請(qǐng)注意魏身，為初始容量選擇過高的值對(duì)該類的影響要小于對(duì)HashMap的影響惊橱，因?yàn)樵擃惖牡鷷r(shí)間不受容量的影響。

Note that this implementation is not synchronized.If multiple threads access a linked hash map concurrently, and at least one of the threads modifies the map structurally, it <em>must</em> be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map.

注意叠骑，這個(gè)實(shí)現(xiàn)沒有同步李皇。如果多個(gè)線程并發(fā)地訪問一個(gè)鏈接的哈希映射，并且至少有一個(gè)線程修改了映射的結(jié)構(gòu)，那么它 必須在外部同步掉房。這通常是通過在自然封裝映射的某個(gè)對(duì)象上同步來實(shí)現(xiàn)的茧跋。

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with <tt>get</tt> is a structural modification.)

結(jié)構(gòu)修改是添加或刪除一個(gè)或多個(gè)映射的操作，或者在訪問順序鏈接哈希映射的情況下影響迭代順序的操作卓囚。在插入順序鏈接哈希映射中瘾杭，僅僅改變與映射中已經(jīng)包含的鍵相關(guān)聯(lián)的值不是結(jié)構(gòu)修改。在訪問順序鏈接哈希映射中哪亿，僅僅使用get查詢映射是一種結(jié)構(gòu)修改粥烁。

The iterators returned by the iterator method of the collections returned by all of this class's collection view methods are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a {@link ConcurrentModificationException}. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
這個(gè)類的所有集合視圖方法返回的迭代器都是快速失敗的: 如果Map是創(chuàng)建迭代器后修改了結(jié)構(gòu),任何時(shí)候以任何方式刪除結(jié)點(diǎn)(除非通過迭代器的刪除方法),迭代器都會(huì)拋出一個(gè){@link ConcurrentModificationException}。因此蝇棉，在面對(duì)并發(fā)修改時(shí)讨阻，迭代器會(huì)快速而干凈地失敗，而不是在未來某個(gè)不確定的時(shí)間冒險(xiǎn)做出任意的篡殷、不確定的行為钝吮。（不是線程安全的）

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
注意，迭代器的快速失敗行為不能得到保證板辽，因?yàn)橐话銇碚f奇瘦，在存在非同步并發(fā)修改時(shí)不可能做出任何硬性保證【⑾遥快速失敗迭代器盡最大努力拋出ConcurrentModificationException耳标。因此，如果要編寫一個(gè)依賴于這個(gè)異常來保證其正確性的程序邑跪，那就錯(cuò)了:迭代器的快速失敗行為應(yīng)該僅用于檢測(cè)錯(cuò)誤次坡。

然后看一下LinkedHashMap類的代碼：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

可以看出，LinkedHashMap是繼承HashMap的画畅，然后觀察它里面的結(jié)構(gòu)會(huì)發(fā)現(xiàn)它有以下幾個(gè)變量：

/**
* HashMap.Node subclass for normal LinkedHashMap entries.
* 比HashMap多了before, after兩個(gè)結(jié)點(diǎn)贸毕，表示該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)與后一個(gè)結(jié)點(diǎ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);
    }
}
/**
* The head (eldest) of the doubly linked list.
* 雙鏈表的頭(最大的)夜赵，雙向鏈表的表頭
*/
transient LinkedHashMap.Entry<K,V> head;

/**
* The tail (youngest) of the doubly linked list.
* 雙鏈表的尾部(最年輕的)明棍，雙向鏈表的表尾
*/
transient LinkedHashMap.Entry<K,V> tail;

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* 該LinkedHashMap的迭代排序方法:true為訪問順序，為false為插入順序寇僧。
* 默認(rèn)為false摊腋，即插入順序。
*
* @serial
*/
final boolean accessOrder;

然后來看LinkedHashMap的構(gòu)造方法函數(shù)：

// 無參構(gòu)造函數(shù)嘁傀，默認(rèn)調(diào)用HashMap的構(gòu)造函數(shù)兴蒸，將accessOrder默認(rèn)為false
public LinkedHashMap() {
    super();
    accessOrder = false;
}
/**
指定初始容量的構(gòu)造函數(shù)，accessOrder默認(rèn)為false
*/
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
/**
指定初始容量和加載因?yàn)榈臉?gòu)造函數(shù)细办，將accessOrder默認(rèn)為false
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

/**
指定初始容量橙凳、加載因子和accessOrder的構(gòu)造函數(shù)
*/
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

/**
Constructs an insertion-ordered LinkedHashMap instance with the same mappings as the specified map.  The LinkedHashMap instance is created with a default load factor (0.75) and an initial capacity sufficient to hold the mappings in the specified map.
使用與指定Map相同的Map構(gòu)造一個(gè)插入有序的LinkedHashMap實(shí)例蕾殴。創(chuàng)建LinkedHashMap實(shí)例時(shí)使用的是默認(rèn)加載因子(0.75)和足以容納指定映射中的映射的初始容量。
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

接下來岛啸，直接找到LinkedHashMap的get()方法：

public V get(Object key) {
    Node<K,V> e;
    // 調(diào)用父類HashMap的getNode()方法得到key對(duì)應(yīng)的value
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 判斷LinkedHashMap的排序方式钓觉，true為訪問順序，為false為插入順序坚踩。
    if (accessOrder)
        // 按訪問順序排序
        afterNodeAccess(e);
    // 按插入順序排序
    return e.value;
}

而訪問順序又是什么呢荡灾，我們繼續(xù)看afterNodeAccess()的實(shí)現(xiàn)：

// move node to last, 將結(jié)點(diǎn) e 移到LinkedHashMap的最后
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        // LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
        // LinkedHashMap.Entry<K,V> b = p.before;
        // LinkedHashMap.Entry<K,V> a = p.after;
        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;
    }
}

可以看到afterNodeAccess()就是將新插入的結(jié)點(diǎn)放在LinkedHashMap的最后，也就是說accessOrder為true時(shí)（訪問順序排序）瞬铸，會(huì)按照這樣來排序：最近被訪問的結(jié)點(diǎn)會(huì)被移動(dòng)到LinkedHashMap的最后一個(gè)結(jié)點(diǎn)批幌。

講到這里發(fā)現(xiàn)還是沒有看到LinkedHashMap在調(diào)用put()的時(shí)候怎么實(shí)現(xiàn)有序的，因?yàn)樗]有重寫put()方法嗓节，但是通過上面觀察LinkedHashMap的變量時(shí)發(fā)現(xiàn)它的Entry是繼承HashMap.Node的荧缘，而在HashMap的put()方法中可以找到一個(gè)重要的方法：

// Create a regular (non-tree) node 創(chuàng)建一個(gè)常規(guī)的結(jié)點(diǎn)
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

而在LinkedHashMap中也有這個(gè)方法，證明LinkedHashMap重寫了HashMap的newNode()方法：

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

因此拦宣，可以得知LinkedHashMap是利用它重寫的Entry和newNode()方法來保證有序的胜宇，而其中重點(diǎn)保證有序的排序的方法就是linkNodeLast()：

// link at the end of list 將結(jié)點(diǎn)鏈接在LinkedHashMap的末尾
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        // p的前一個(gè)結(jié)點(diǎn)設(shè)置為last，last的下一個(gè)結(jié)點(diǎn)設(shè)置為p 
        p.before = last;
        last.after = p;
    }
}

總結(jié)：

1. LinkedHashMap是有序的恢着，維護(hù)了一個(gè)雙向鏈表來保證迭代的順序，通常是插入順序财破。
2. LinkedHashMap可以通過重寫removeEldestEntry(Map.Entry)方法來規(guī)定新結(jié)點(diǎn)插入到Map時(shí)自動(dòng)刪除過時(shí)結(jié)點(diǎn)的策略掰派，也就是說可以通過該方法實(shí)現(xiàn)LRU算法來插入新結(jié)點(diǎn)。
3. LinkedHashMap與HashMap一樣允許空元素左痢。
4. 一般情況下靡羡，LinkedHashMap的性能可能低于HashMap，因?yàn)長inkedHashMap需要額外維護(hù)一個(gè)雙向鏈表俊性，但是在對(duì)LinkedHashMap進(jìn)行迭代所需要的時(shí)間與LinkedHashMap的大小成正比而與LinkedHashMap的容量無關(guān)時(shí)略步，LinkedHashMap的性能可能會(huì)優(yōu)于HashMap，HashMap進(jìn)行迭代時(shí)定页，需要的時(shí)間與其容量成正比趟薄。
5. LinkedHashMap并沒有實(shí)現(xiàn)同步，所以是非線程安全的典徊，如果多個(gè)線程并發(fā)訪問一個(gè)LinkedHashMap時(shí)杭煎，且至少有一個(gè)線程修改了其結(jié)構(gòu)，那么必須對(duì)LinkedHashMap進(jìn)行同步操作卒落。
6. LinkedHashMap實(shí)現(xiàn)有序的關(guān)鍵在于它重寫了HashMap的Entry結(jié)構(gòu)（增加了header羡铲、tail結(jié)點(diǎn)，以及其他結(jié)點(diǎn)的before儡毕、after的轉(zhuǎn)換）也切、newNode()方法以及重要的linkNodeLast()方法，使得在調(diào)用LinkedHashMap的put()方法時(shí)，默認(rèn)會(huì)按照插入順序進(jìn)行結(jié)點(diǎn)的添加雷恃。