漏掉一個(gè)Map输拇，補(bǔ)一下
LinkedHashMap是HashMap的子類，此實(shí)現(xiàn)與HashMap的不同之處在于它維護(hù)了一個(gè)貫穿其所有條目的雙向鏈表贤斜。 此鏈表定義迭代排序策吠，通常是鍵插入映射的順序（插入順序）。 請(qǐng)注意瘩绒，如果將鍵重新插入Map猴抹，則不會(huì)影響插入順序。
定義及說明
定義如下：
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{}
它繼承于HashMap草讶，底層使用哈希表和鏈表來維護(hù)集合洽糟。
構(gòu)造方法為：
//此鏈表哈希映射的迭代排序方法：true表示訪問順序炉菲，false表示插入順序堕战。
final boolean accessOrder;
//使用指定的初始容量和加載因子構(gòu)造一個(gè)空的插入排序的LinkedHashMap實(shí)例
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//使用指定的初始容量和默認(rèn)加載因子（0.75）構(gòu)造一個(gè)空的插入排序的LinkedHashMap實(shí)例
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//使用默認(rèn)初始容量（16）和加載因子（0.75）構(gòu)造一個(gè)空的插入順序LinkedHashMap實(shí)例坤溃。
public LinkedHashMap() {
super();
accessOrder = false;
}
//構(gòu)造一個(gè)插入有序的LinkedHashMap實(shí)例，其具有與指定映射相同的映射嘱丢。 LinkedHashMap實(shí)例使用默認(rèn)加載因子（0.75）和足以保存指定映射中的映射的初始容量創(chuàng)建薪介。
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
//使用指定的初始容量，加載因子和排序模式構(gòu)造一個(gè)空的LinkedHashMap實(shí)例越驻。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
我們可以看到汁政，LinkedHashMap是調(diào)用父類的構(gòu)造函數(shù)做初始化。其構(gòu)造函數(shù)中的accessOrder屬性決定了迭代順序缀旁，true表示訪問順序记劈，false表示插入順序。默認(rèn)使用插入順序并巍，即使用通過put或其類似方法插入的順序進(jìn)行排序目木。
源碼及簡(jiǎn)析
按照慣例應(yīng)該是分析put()方法了，但是懊渡，很尷尬刽射，LinkedHashMap并沒有重寫put()方法，也就是說剃执，它的put()方法跟HashMap是相同的誓禁。但是，他重寫了putVal()方法中調(diào)用的afterNodeAccess()和afterNodeInsertion()方法肾档，我們看一下：
//LinkedHashMap自己的Entry
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
//雙向鏈表的頭部
transient LinkedHashMapEntry<K,V> head;
//雙向鏈表的尾部
transient LinkedHashMapEntry<K,V> tail;
//將節(jié)點(diǎn)移動(dòng)到最后
void afterNodeAccess(Node<K,V> e) {
LinkedHashMapEntry<K,V> last;
//如果是按訪問順序排序摹恰，且e不是鏈表的尾部
if (accessOrder && (last = tail) != e) {
//將e節(jié)點(diǎn)賦值給p，將e的前節(jié)點(diǎn)賦值給b阁最，將e的后節(jié)點(diǎn)賦值給a戒祠，將tail賦值給last
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//將p的后一個(gè)節(jié)點(diǎn)置為空
p.after = null;
//如果p為鏈表頭部
if (b == null)
//將a置為鏈表頭部
head = a;
else
//否則，將a置為b的后一個(gè)元素
b.after = a;
//如果p不是鏈表的尾部
if (a != null)
//將a的上一個(gè)元素置為b
a.before = b;
else
//否則速种，將b賦值給last
last = b;
//當(dāng)前鏈表如果為空
if (last == null)
//將p置為鏈表的頭部
head = p;
else {
//否則姜盈，將p置為last的下一個(gè)元素
p.before = last;
last.after = p;
}
//將p置為鏈表的尾部
tail = p;
++modCount;
}
}
//在HashMap中傳過來的evict為true
void afterNodeInsertion(boolean evict) {
LinkedHashMapEntry<K,V> first;
//判斷是否刪除過時(shí)的條目
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//調(diào)用HashMap的方法
removeNode(hash(key), key, null, false, true);
}
}
//如果此映射應(yīng)刪除其最舊條目，則返回true配阵。它允許映射通過刪除過時(shí)條目來減少內(nèi)存消耗馏颂。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
//糟老頭子壞的很，它直接返回了falseＦ灏＞壤！
return false;
}
通過上面分析瘫拣，我們發(fā)現(xiàn)亿絮，如果是按照訪問順序排序，則經(jīng)過一系列的判斷和賦值后，將新元素插入到鏈表的尾部派昧。也就是說黔姜，如果按照訪問的順序排序，則排序靠后的蒂萎，就是最近插入的元素秆吵。要注意，這個(gè)排序跟在Map中的存儲(chǔ)順序沒有關(guān)系五慈，只是在雙向鏈表中的順序纳寂。我們還發(fā)現(xiàn)在LinkedHashMapEntry類內(nèi)部，出現(xiàn)了before和after兩個(gè)屬性泻拦，而根據(jù)在afterNodeAccess()方法中的分析毙芜，他們分別指向元素的上一個(gè)和下一個(gè)節(jié)點(diǎn)。那么争拐，由此得出爷肝，在LinkedHashMap中的鏈表是一個(gè)雙向鏈表。
刪除條目時(shí)陆错，調(diào)用了HashMap的remove()方法灯抛，LinkedHashMap重寫了其中調(diào)用的afterNodeRemoval(node)方法(在removeNode方法中調(diào)用)，我們現(xiàn)在來看一下：
void afterNodeRemoval(Node<K,V> e) {
//將e的值賦予p音瓷，將p的上個(gè)節(jié)點(diǎn)的值賦予b对嚼，p的下個(gè)節(jié)點(diǎn)的值賦予a
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//將p前、后節(jié)點(diǎn)置為空
p.before = p.after = null;
//如果p為鏈表頭部
if (b == null)
//將a設(shè)置為鏈表頭部
head = a;
else
//否則绳慎，將b的下個(gè)元素由變?yōu)閍
b.after = a;
//如果p為鏈表尾部
if (a == null)
//將b設(shè)為鏈表尾部
tail = b;
else
//否則纵竖，將b設(shè)置為a的上個(gè)元素
a.before = b;
}
可以看到，通過對(duì)指定元素e前后節(jié)點(diǎn)b杏愤、a的設(shè)置靡砌，使得其b、a的指向不再指向p珊楼，以將其刪除通殃。
接下來，我們看一下它的get()方法：
public V get(Object key) {
//初始化一個(gè)節(jié)點(diǎn)對(duì)象
Node<K,V> e;
//判斷key所對(duì)應(yīng)的節(jié)點(diǎn)是否為空厕宗，不為空則獲取key所對(duì)應(yīng)的節(jié)點(diǎn)值
if ((e = getNode(hash(key), key)) == null)
return null;
//判斷排序方式
if (accessOrder)
//如果是訪問順序画舌，則重排序
afterNodeAccess(e);
return e.value;
}
//重排序(或是調(diào)用了put()方法之后，為節(jié)點(diǎn)設(shè)置前已慢、后位置的元素)
void afterNodeAccess(Node<K,V> e) {
LinkedHashMapEntry<K,V> last;
//判斷排序方式是按訪問順序排序曲聂，且e節(jié)點(diǎn)不是雙向鏈表的尾部
if (accessOrder && (last = tail) != e) {
//將e節(jié)點(diǎn)賦值給p，將e的前節(jié)點(diǎn)賦值給b佑惠，將e的后節(jié)點(diǎn)賦值給a
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//將p的后一個(gè)節(jié)點(diǎn)置為空
p.after = null;
if (b == null)
//如果b為空朋腋，證明e為首節(jié)點(diǎn)齐疙，則將e的下個(gè)節(jié)點(diǎn)置為首節(jié)點(diǎn)
head = a;
else
//如果b不為空，則將a置為其下個(gè)節(jié)點(diǎn)旭咽，替代e的位置
b.after = a;
if (a != null)
//如果a不為空剂碴，則將a的上一個(gè)節(jié)點(diǎn)置為b，替代e的位置
a.before = b;
else
//如果a為空轻专，則將b的值賦值給last
last = b;
if (last == null)
//如果last為空(即tail為空，且b為空察蹲，說明只有p一個(gè)元素)请垛，則將p置為首節(jié)點(diǎn)
head = p;
else {
//如果last不為空，則將p的前節(jié)點(diǎn)置為last洽议，last的后節(jié)點(diǎn)置為p
p.before = last;
last.after = p;
}
/將p置為尾節(jié)點(diǎn)
tail = p;
++modCount;
}
}
可以發(fā)現(xiàn)宗收，我們把get方法訪問過的元素放到鏈表的尾部，而通過上面的分析亚兄，我們發(fā)現(xiàn)混稽，如果主動(dòng)刪除元素，則從鏈表的頭部開始审胚。這樣匈勋，就形成了一個(gè)簡(jiǎn)單的LRU。不過膳叨，由于其removeEldestEntry()方法直接返回了false洽洁，所以，如果我們要用它做LRU菲嘴，就需要自己寫一個(gè)類繼承LinkedHashMap饿自，并重寫removeEldestEntry()方法。比如龄坪，我們要求Map的長(zhǎng)度在100以內(nèi)：
private static final int MAX_ENTRIES = 100;
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
小結(jié)
1昭雌、LinkedHashMap繼承于HashMap，是一個(gè)基于HashMap和雙向鏈表實(shí)現(xiàn)的Map健田。
2烛卧、LinedHashMap是有順序的，分別為按照插入順序排序和按照訪問順序排序妓局，默認(rèn)為按照插入順序排序唱星。
3、LinkedHashMap是非同步的跟磨。
