文章首發(fā)csdn博客地址：https://blog.csdn.net/u013277209?viewmode=contents
一：概要
HashMap是Java集合中的重要成員仍翰，也是Map族中我們最為常用的一種梦皮，但是HashMap是無序的，也就是說励翼，迭代HashMap所得到的元素順序并不是它們最初放置到HashMap的順序抡秆。
HashMap的這一缺點往往會造成諸多不便大溜，因為在有些場景中差油，我們確需要用到一個可以保持插入順序的Map泳炉。慶幸的是憾筏，JDK為我們解決了這個問題，它為HashMap提供了一個子類 —— LinkedHashMap花鹅。雖然LinkedHashMap增加了時間和空間上的開銷氧腰，但是它通過維護一個額外的雙向鏈表保證了迭代順序。
該迭代順序可以是插入順序刨肃，也可以是訪問順序古拴。因此，根據(jù)鏈表中元素的順序可以將LinkedHashMap分為：保持插入順序的LinkedHashMap和保持訪問順序的LinkedHashMap真友，其中LinkedHashMap的默認實現(xiàn)是按插入順序排序的黄痪。
其實LinkedHashMap就是 HashMap+雙向鏈表 來實現(xiàn)的，就是將所有Node節(jié)點鏈入一個雙向鏈表的HashMap盔然。在LinkedHashMapMap中桅打，所有put進來的Node都保存在哈希表中是嗜，但由于它又額外定義了一個以head為頭結(jié)點的雙向鏈表，因此對于每次put進來Node挺尾，除了將其保存到哈希表中對應(yīng)的位置上之外鹅搪，還會將其插入到雙向鏈表的尾部。
二潦嘶、源碼分析
類信息
LinkedHashMap繼承于HashMap涩嚣，并在此基礎(chǔ)上擴展了雙向鏈表。
public class LinkedHashMap<K,V> extends HashMap<K,V>
implements Map<K,V>
成員變量
與HashMap相比掂僵，LinkedHashMap增加了兩個屬性用于保證迭代順序航厚，分別是 雙向鏈表頭結(jié)點head尾結(jié)點tail 和 標志位accessOrder (值為true時，表示按照訪問順序迭代锰蓬；值為false時幔睬，表示按照插入順序迭代)。
//頭結(jié)點
transient LinkedHashMap.Entry<K,V> head;
//尾結(jié)點
transient LinkedHashMap.Entry<K,V> tail;
//true表示按照訪問順序迭代芹扭，false時表示按照插入順序
final boolean accessOrder;
元素類
LinkedHashMap采用的hash算法和HashMap相同麻顶，但是它重新定義了Entry。LinkedHashMap中的Entry增加了兩個指針 before 和 after舱卡，它們分別用于維護雙向鏈接列表辅肾。特別需要注意的是，next用于維護HashMap各個桶中Entry的連接順序轮锥，before矫钓、after用于維護Entry插入的先后順序的，源代碼如下：
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);
}
}
構(gòu)造函數(shù)
LinkedHashMap 一共提供了五個構(gòu)造函數(shù)舍杜，它們都是在HashMap的構(gòu)造函數(shù)的基礎(chǔ)上實現(xiàn)的新娜，除了默認空參數(shù)構(gòu)造方法，下面這個構(gòu)造函數(shù)包含了大部分其他構(gòu)造方法使用的參數(shù)既绩。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);// 調(diào)用HashMap對應(yīng)的構(gòu)造函數(shù)
this.accessOrder = accessOrder;//指定迭代順序方式
}
put方法
LinkedHashMap沒有對 put(key,vlaue) 方法進行任何直接的修改概龄，完全繼承了HashMap的 put(Key,Value) 方法，HashMap中put源碼如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//計算index饲握，并對null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//節(jié)點key存在私杜，直接覆蓋value
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);
//鏈表長度大于8轉(zhuǎn)換為紅黑樹進行處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已經(jīng)存在直接覆蓋value
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中，它對newNode方法進行了重寫救欧。下面我們對比地看一下LinkedHashMap 和HashMap的newNode方法的具體實現(xiàn)：
//LinkedHashMap
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
```java
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
可見在LinkedHashMap中向哈希表中插入新Node的同時歪今，還會通過linkNodeLast方法將其鏈入到雙向鏈表中，相比HashMap而言颜矿，LinkedHashMap在向哈希表添加一個鍵值對的同時，也會將其鏈入到它所維護的雙向鏈表中嫉晶，以便設(shè)定迭代順序骑疆。
get方法
相對于LinkedHashMap的存儲而言田篇，讀取就顯得比較簡單了。LinkedHashMap中重寫了HashMap中的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;
}
在LinkedHashMap的get方法中泊柬，通過HashMap中的getNode方法獲取Node對象。注意這里的afterNodeAccess方法诈火，如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話（當accessOrder為false時）兽赁，該方法什么也不做；如果鏈表中元素的排序規(guī)則是按照訪問的先后順序排序的話（當accessOrder為true時）冷守，則將e移到鏈表的末尾處刀崖。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 判斷迭代策略，并且當前節(jié)點不是尾節(jié)點
if (accessOrder && (last = tail) != e) {
// 記錄當前節(jié)點拍摇，并獲取前后節(jié)點
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 把當前節(jié)點的 after 節(jié)點置 null
p.after = null;
// 如果當前節(jié)點是頭節(jié)點亮钦，把后一個節(jié)點置為頭節(jié)點
if (b == null)
head = a;
// 把當前節(jié)點的前后節(jié)點相連
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
// 把當前節(jié)點置為尾節(jié)點并記錄
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
擴容機制
由于LinkedHashMap并沒有重寫HashMap的擴容，所以其擴容是和HashMap保持一致的充活，具體可以參見吃透Java集合系列九：HashMap
