1 LinkedHashMap
1.1 底層結(jié)構(gòu)
LinkedHashMap可以認(rèn)為是HashMap(藍(lán)色部分)+LinkedList(黑色部分)瘦馍，即它既使用HashMap操作數(shù)據(jù)結(jié)構(gòu)，又使用LinkedList維護(hù)插入元素的先后順序应役。
LinkedHashMap的基本實(shí)現(xiàn)思想就是—-多態(tài)情组≡锟辏可以說(shuō)，理解多態(tài)院崇，再去理解LinkedHashMap原理會(huì)事半功倍肆氓；反之也是，對(duì)于LinkedHashMap原理的學(xué)習(xí)底瓣，也可以促進(jìn)和加深對(duì)于多態(tài)的理解谢揪。
說(shuō)明：LinkedHashMap會(huì)將元素串起來(lái)，形成一個(gè)雙鏈表結(jié)構(gòu)捐凭〔Ψ觯可以看到，其結(jié)構(gòu)在HashMap結(jié)構(gòu)上增加了鏈表結(jié)構(gòu)茁肠。數(shù)據(jù)結(jié)構(gòu)為（數(shù)組 + 單鏈表 + 紅黑樹(shù) + 雙鏈表）患民，圖中的標(biāo)號(hào)是結(jié)點(diǎn)插入的順序。
1.2 優(yōu)缺點(diǎn)
有序的官套，即能夠保存元素插入的順序
2 四個(gè)關(guān)注點(diǎn)
| 關(guān)注點(diǎn) | 結(jié)論 |
|---|---|
| LinkedHashMap是否允許鍵值對(duì)為空 | Key和Value都允許為空 |
| LinkedHashMap是否允許重復(fù)數(shù)據(jù) | Key重復(fù)會(huì)覆蓋酒奶，Value允許重復(fù) |
| LinkedHashMap是否有序 | 有序 |
| LinkedHashMap是否線程安全 | 非線程安全 |
3 LinkedHashMap源碼解析
其實(shí)，在分析了HashMap的源碼之后奶赔，我們來(lái)分析LinkedHashMap的源碼就會(huì)容易很多惋嚎，因?yàn)長(zhǎng)inkedHashMap是在HashMap基礎(chǔ)上進(jìn)行了擴(kuò)展，我們需要注意的就是兩者不同的地方站刑。
3.1 類的繼承關(guān)系
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
說(shuō)明：LinkedHashMap繼承了HashMap另伍，所以HashMap的一些方法或者屬性也會(huì)被繼承；同時(shí)也實(shí)現(xiàn)了Map結(jié)構(gòu)绞旅，關(guān)于HashMap類與Map接口摆尝，我們之前已經(jīng)分析過(guò)，不再累贅因悲。
3.2 類的屬性
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 版本序列號(hào)
private static final long serialVersionUID = 3801124242820219131L;
// 鏈表頭結(jié)點(diǎn)
transient LinkedHashMap.Entry<K,V> head;
// 鏈表尾結(jié)點(diǎn)
transient LinkedHashMap.Entry<K,V> tail;
// 訪問(wèn)順序
final boolean accessOrder;
}
說(shuō)明：由于繼承HashMap堕汞，所以HashMap中的非private方法和字段，都可以在LinkedHashMap直接中訪問(wèn)晃琳。
3.3 類的構(gòu)造函數(shù)
1. LinkedHashMap(int, float)型構(gòu)造函數(shù)
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
說(shuō)明：總是會(huì)在構(gòu)造函數(shù)的第一行調(diào)用父類構(gòu)造函數(shù)讯检，使用super關(guān)鍵字，accessOrder默認(rèn)為false卫旱，access為true表示之后訪問(wèn)順序按照元素的訪問(wèn)順序進(jìn)行人灼，即不按照之前的插入順序了，access為false表示按照插入順序訪問(wèn)顾翼。
2. LinkedHashMap(int)型構(gòu)造函數(shù)
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
3. LinkedHashMap()型構(gòu)造函數(shù)
public LinkedHashMap() {
super();
accessOrder = false;
}
4. LinkedHashMap(Map<? extends K, ? extends V>)型構(gòu)造函數(shù)
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
說(shuō)明：putMapEntries是調(diào)用到父類HashMap的函數(shù)
5. LinkedHashMap(int, float, boolean)型構(gòu)造函數(shù)
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
說(shuō)明：可以指定accessOrder的值投放，從而控制訪問(wèn)順序。
3.4 類的重要函數(shù)分析
1. newNode函數(shù)
// 當(dāng)桶中結(jié)點(diǎn)類型為HashMap.Node類型時(shí)适贸，調(diào)用此函數(shù)
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 生成Node結(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 將該結(jié)點(diǎn)插入雙鏈表末尾
linkNodeLast(p);
return p;
}
說(shuō)明：此函數(shù)在HashMap類中也有實(shí)現(xiàn)灸芳，LinkedHashMap重寫(xiě)了該函數(shù)涝桅，所以當(dāng)實(shí)際對(duì)象為L(zhǎng)inkedHashMap，桶中結(jié)點(diǎn)類型為Node時(shí)烙样，我們調(diào)用的是LinkedHashMap的newNode函數(shù)苹支，而非HashMap的函數(shù)，newNode函數(shù)會(huì)在調(diào)用put函數(shù)時(shí)被調(diào)用误阻≌郏可以看到，除了新建一個(gè)結(jié)點(diǎn)之外究反，還把這個(gè)結(jié)點(diǎn)鏈接到雙鏈表的末尾了寻定，這個(gè)操作維護(hù)了插入順序。
其中LinkedHashMap.Entry繼承自HashMap.Node精耐。
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);
}
}
說(shuō)明：在HashMap.Node基礎(chǔ)上增加了前后兩個(gè)指針域狼速，注意，HashMap.Node中的next域也存在卦停。
2. newTreeNode函數(shù)
// 當(dāng)桶中結(jié)點(diǎn)類型為HashMap.TreeNode時(shí)向胡，調(diào)用此函數(shù)
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
// 生成TreeNode結(jié)點(diǎn)
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
// 將該結(jié)點(diǎn)插入雙鏈表末尾
linkNodeLast(p);
return p;
}
說(shuō)明：當(dāng)桶中結(jié)點(diǎn)類型為T(mén)reeNode時(shí)候，插入結(jié)點(diǎn)時(shí)調(diào)用的此函數(shù)惊完，也會(huì)鏈接到末尾僵芹。
3. afterNodeAccess函數(shù)
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 若訪問(wèn)順序?yàn)閠rue，且訪問(wèn)的對(duì)象不是尾結(jié)點(diǎn)
if (accessOrder && (last = tail) != e) {
// 向下轉(zhuǎn)型小槐，記錄p的前后結(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// p的后結(jié)點(diǎn)為空
p.after = null;
// 如果p的前結(jié)點(diǎn)為空
if (b == null)
// a為頭結(jié)點(diǎn)
head = a;
else // p的前結(jié)點(diǎn)不為空
// b的后結(jié)點(diǎn)為a
b.after = a;
// p的后結(jié)點(diǎn)不為空
if (a != null)
// a的前結(jié)點(diǎn)為b
a.before = b;
else // p的后結(jié)點(diǎn)為空
// 后結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)
last = b;
// 若最后一個(gè)結(jié)點(diǎn)為空
if (last == null)
// 頭結(jié)點(diǎn)為p
head = p;
else { // p鏈入最后一個(gè)結(jié)點(diǎn)后面
p.before = last;
last.after = p;
}
// 尾結(jié)點(diǎn)為p
tail = p;
// 增加結(jié)構(gòu)性修改數(shù)量
++modCount;
}
}
說(shuō)明：此函數(shù)在很多函數(shù)（如put）中都會(huì)被回調(diào)拇派，LinkedHashMap重寫(xiě)了HashMap中的此函數(shù)。若訪問(wèn)順序?yàn)閠rue凿跳，且訪問(wèn)的對(duì)象不是尾結(jié)點(diǎn)件豌，則下面的圖展示了訪問(wèn)前和訪問(wèn)后的狀態(tài)，假設(shè)訪問(wèn)的結(jié)點(diǎn)為結(jié)點(diǎn)3
說(shuō)明：從圖中可以看到控嗜，結(jié)點(diǎn)3鏈接到了尾結(jié)點(diǎn)后面茧彤。
4. transferLinks函數(shù)
// 用dst替換src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
說(shuō)明：此函數(shù)用dst結(jié)點(diǎn)替換結(jié)點(diǎn)，示意圖如下
說(shuō)明：其中只考慮了before與after域疆栏，并沒(méi)有考慮next域曾掂，next會(huì)在調(diào)用tranferLinks函數(shù)中進(jìn)行設(shè)定。
5. containsValue函數(shù)
public boolean containsValue(Object value) {
// 使用雙鏈表結(jié)構(gòu)進(jìn)行遍歷查找
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;
}
說(shuō)明：containsValue函數(shù)根據(jù)雙鏈表結(jié)構(gòu)來(lái)查找是否包含value承边，是按照插入順序進(jìn)行查找的遭殉，與HashMap中的此函數(shù)查找方式不同石挂，HashMap是使用按照桶遍歷博助，沒(méi)有考慮插入順序。
