LinkedHashMap
LinkedHashMap繼承自HashMap實現(xiàn)了Map接口便斥∨梗基本實現(xiàn)同HashMap一樣育韩，不同之處在于LinkedHashMap保證了迭代的有序性宵晚。其內(nèi)部維護了一個雙向鏈表，解決了 HashMap不能隨時保持遍歷順序和插入順序一致的問題菠劝。
除此之外赊舶，LinkedHashMap對訪問順序也提供了相關(guān)支持。在一些場景下赶诊，該特性很有用笼平，比如緩存。
在實現(xiàn)上舔痪，LinkedHashMap很多方法直接繼承自HashMap寓调，僅為維護雙向鏈表覆寫了部分方法。所以锄码，要看懂 LinkedHashMap 的源碼夺英，需要先看懂 HashMap 的源碼晌涕。
默認情況下，LinkedHashMap的迭代順序是按照插入節(jié)點的順序秋麸。也可以通過改變accessOrder參數(shù)的值渐排，使得其遍歷順序按照訪問順序輸出。
這里我們只討論LinkedHashMap和HashMap的不同之處灸蟆，LinkedHashMap的其他操作和特性具體請參考HashMap的實現(xiàn)
我們先來看下兩者的區(qū)別：
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Test04 {
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("ahdjkf", "1");
map.put("ifjdj", "2");
map.put("giafdja", "3");
map.put("agad", "4");
map.put("ahdjkge", "5");
map.put("iegnj", "6");
System.out.println("LinkedHashMap的迭代順序(accessOrder=false)：");
Iterator iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
Map<String, String> map1 = new LinkedHashMap<String, String>(16,0.75f,true);
map1.put("ahdjkf", "1");
map1.put("ifjdj", "2");
map1.put("giafdja", "3");
map1.put("agad", "4");
map1.put("ahdjkge", "5");
map1.put("iegnj", "6");
map1.get("ahdjkf");
map1.get("ifjdj");
System.out.println("LinkedHashMap的迭代順序(accessOrder=true)：");
Iterator iterator1 = map1.entrySet().iterator();
while (iterator1.hasNext()) {
Map.Entry entry = (Map.Entry) iterator1.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
Map<String, String> map2 = new HashMap<>();
map2.put("ahdjkf", "1");
map2.put("ifjdj", "2");
map2.put("giafdja", "3");
map2.put("agad", "4");
map2.put("ahdjkge", "5");
map2.put("iegnj", "6");
System.out.println("HashMap的迭代順序：");
Iterator iterator2 = map2.entrySet().iterator();
while (iterator2.hasNext()) {
Map.Entry aMap = (Map.Entry) iterator2.next();
System.out.println(aMap.getKey() + "=" + aMap.getValue());
}
}
}
Output：
LinkedHashMap的迭代順序(accessOrder=false)：
ahdjkf=1
ifjdj=2
giafdja=3
agad=4
ahdjkge=5
iegnj=6
LinkedHashMap的迭代順序(accessOrder=true)：
giafdja=3
agad=4
ahdjkge=5
iegnj=6
ahdjkf=1
ifjdj=2
HashMap的迭代順序：
iegnj=6
giafdja=3
ifjdj=2
agad=4
ahdjkf=1
ahdjkge=5
可以看到 LinkedHashMap在每次插入數(shù)據(jù)驯耻，訪問、修改數(shù)據(jù)時都會調(diào)整鏈表的節(jié)點順序炒考。以決定迭代時輸出的順序可缚。
下面我們來看LinkedHashMap具體是怎么實現(xiàn)的：
LinkedHashMap繼承了HashMap，內(nèi)部靜態(tài)類Entry繼承了HashMap的Entry斋枢，但是LinkedHashMap.Entry多了兩個字段：before和after帘靡，before表示在本節(jié)點之前添加到LinkedHashMap的那個節(jié)點，after表示在本節(jié)點之后添加到LinkedHashMap的那個節(jié)點瓤帚，這里的之前和之后指時間上的先后順序描姚。
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);
}
}
同時類里有兩個成員變量head和tail,分別指向內(nèi)部雙向鏈表的表頭、表尾戈次。
//雙向鏈表的頭結(jié)點
transient LinkedHashMap.Entry<K,V> head;
//雙向鏈表的尾節(jié)點
transient LinkedHashMap.Entry<K,V> tail;
我們通過兩張圖來看下LinkedHashMap的存儲結(jié)構(gòu)
圖片來自：coolblog
將LinkedHashMap的accessOrder字段設(shè)置為true后轩勘，每次訪問哈希表中的節(jié)點都將該節(jié)點移到鏈表的末尾，表示該節(jié)點是最新訪問的節(jié)點怯邪。即循環(huán)雙向鏈表的頭部存放的是最久訪問的節(jié)點或最先插入的節(jié)點绊寻，尾部為最近訪問的或最近插入的節(jié)點。
由于增加了一個accessOrder屬性悬秉，LinkedHashMap相對HashMap來說增加了一個構(gòu)造方法用來控制迭代順序澄步。
final boolean accessOrder;
public LinkedHashMap() {
super();
accessOrder = false;
}
//指定初始化時的容量，
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//指定初始化時的容量和泌，和擴容的加載因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//指定初始化時的容量村缸，和擴容的加載因子，以及迭代輸出節(jié)點的順序
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//利用另一個Map 來構(gòu)建
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
//該方法上文分析過允跑，批量插入一個map中的所有數(shù)據(jù)到 本集合中王凑。
putMapEntries(m, false);
}
添加元素
LinkedHashMap在添加元素的時候，依舊使用的是HashMap中的put方法聋丝。不同的是LinkedHashMap重寫了newNode()方法在每次構(gòu)建新節(jié)點時，通過linkNodeLast(p);將新節(jié)點鏈接在內(nèi)部雙向鏈表的尾部工碾。
//將新增的節(jié)點弱睦，連接在鏈表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
//如果集合之前是空的
if (last == null)
head = p;
else {//將新節(jié)點連接在鏈表的尾部
p.before = last;
last.after = p;
}
}
刪除元素
LinkedHashMap并沒有重寫HashMap的remove()方法，但是他重寫了afterNodeRemoval()方法渊额，這個方法的作用是在刪除一個節(jié)點時况木，同步將該節(jié)點從雙向鏈表中刪除垒拢。該方法將會在remove中被回調(diào)。
//在刪除節(jié)點e時火惊，同步將e從雙向鏈表上刪除
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//將待刪除節(jié)點 p 的前置后置節(jié)點都置空
p.before = p.after = null;
//如果前置節(jié)點是null求类，則說明現(xiàn)在的頭結(jié)點應(yīng)該是后置節(jié)點a
if (b == null)
head = a;
else//否則將前置節(jié)點b的后置節(jié)點指向a
b.after = a;
//同理如果后置節(jié)點時null ，則尾節(jié)點應(yīng)是b
if (a == null)
tail = b;
else//否則更新后置節(jié)點a的前置節(jié)點為b
a.before = b;
}
刪除過程總的來說可以分為三步：
- 根據(jù) hash 定位到桶位置
- 遍歷鏈表或調(diào)用紅黑樹相關(guān)的刪除方法
- 回調(diào)afterNodeRemoval屹耐，從 LinkedHashMap 維護的雙鏈表中移除要刪除的節(jié)點
更新元素
// 清除節(jié)點時要將頭尾節(jié)點一起清除
public void clear() {
super.clear();
head = tail = null;
}
查找元素
LinkedHashMap重寫了get()和getOrDefault()方法
默認情況下尸疆，LinkedHashMap是按插入順序維護鏈表。不過如果我們在初始化 LinkedHashMap時惶岭，指定 accessOrder參數(shù)為 true寿弱，即可讓它按訪問順序維護鏈表。訪問順序的原理是按灶，當(dāng)我們調(diào)用get/getOrDefault/replace等方法時症革，會將這些方法訪問的節(jié)點移動到鏈表的尾部。
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder) // 回調(diào)afterNodeAccess(Node<K,V> e)
afterNodeAccess(e); // 將節(jié)點e移至雙向鏈表的尾部（保證迭代順序）
return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e); // 作用同上
return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;//原尾節(jié)點
//如果accessOrder 是true 鸯旁，且原尾節(jié)點不等于e
if (accessOrder && (last = tail) != e) {
//節(jié)點e強轉(zhuǎn)成雙向鏈表節(jié)點p
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p現(xiàn)在是尾節(jié)點噪矛， 后置節(jié)點一定是null
p.after = null;
//如果p的前置節(jié)點是null，則p以前是頭結(jié)點铺罢，所以更新現(xiàn)在的頭結(jié)點是p的后置節(jié)點a
if (b == null)
head = a;
else//否則更新p的前直接點b的后置節(jié)點為 a
b.after = a;
//如果p的后置節(jié)點不是null艇挨，則更新后置節(jié)點a的前置節(jié)點為b
if (a != null)
a.before = b;
else//如果原本p的后置節(jié)點是null，則p就是尾節(jié)點畏铆。 此時 更新last的引用為 p的前置節(jié)點b
last = b;
if (last == null) //原本尾節(jié)點是null 則雷袋，鏈表中就一個節(jié)點
head = p;
else {//否則 更新 當(dāng)前節(jié)點p的前置節(jié)點為 原尾節(jié)點last， last的后置節(jié)點是p
p.before = last;
last.after = p;
}
//尾節(jié)點的引用賦值成p
tail = p;
//修改modCount辞居。
++modCount;
}
}
// 因為LinkedHashMap中維護了一個雙向鏈表所以相對于HashMap中的雙重循環(huán)遍歷這個方法要優(yōu)化很多
LinkedHashMap
public boolean containsValue(Object value) {
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;
}
HashMap
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
其他方法
LinkedHashMap還有一個比較神奇的存在楷怒。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 根據(jù)條件判斷是否移除最近最少被訪問的節(jié)點
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 移除最近最少被訪問條件之一，通過覆蓋此方法可實現(xiàn)不同策略的緩存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
上面的方法一般不會被執(zhí)行瓦灶，但是當(dāng)我們基于 LinkedHashMap 實現(xiàn)緩存時鸠删，通過覆寫removeEldestEntry方法可以實現(xiàn)自定義策略的 LRU 緩存。比如我們可以根據(jù)節(jié)點數(shù)量判斷是否移除最近最少被訪問的節(jié)點贼陶，或者根據(jù)節(jié)點的存活時間判斷是否移除該節(jié)點等刃泡。
迭代器
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
//返回LinkedEntrySet
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class LinkedHashIterator {
//下一個節(jié)點
LinkedHashMap.Entry<K,V> next;
//當(dāng)前節(jié)點
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
//初始化時，next 為 LinkedHashMap內(nèi)部維護的雙向鏈表的扁頭
next = head;
//記錄當(dāng)前modCount碉怔，以滿足fail-fast
expectedModCount = modCount;
//當(dāng)前節(jié)點為null
current = null;
}
//判斷是否還有next
public final boolean hasNext() {
//就是判斷next是否為null烘贴，默認next是head 表頭
return next != null;
}
//nextNode() 就是迭代器里的next()方法 。
//該方法的實現(xiàn)可以看出撮胧，迭代LinkedHashMap桨踪，就是從內(nèi)部維護的雙鏈表的表頭開始循環(huán)輸出。
final LinkedHashMap.Entry<K,V> nextNode() {
//記錄要返回的e芹啥。
LinkedHashMap.Entry<K,V> e = next;
//判斷fail-fast
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//如果要返回的節(jié)點是null锻离，異常
if (e == null)
throw new NoSuchElementException();
//更新當(dāng)前節(jié)點為e
current = e;
//更新下一個節(jié)點是e的后置節(jié)點
next = e.after;
//返回e
return e;
}
//刪除方法 最終還是調(diào)用了HashMap的removeNode方法
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
該方法的實現(xiàn)可以看出铺峭，迭代LinkedHashMap，就是從內(nèi)部維護的雙鏈表的表頭開始循環(huán)輸出汽纠。而雙鏈表節(jié)點的順序在LinkedHashMap的增卫键、刪、改虱朵、查時都會更新莉炉。以滿足按照插入順序輸出，還是訪問順序輸出卧秘。
總結(jié)
總結(jié)：
在日常開發(fā)中LinkedHashMap 的使用頻率沒有HashMap高呢袱，但它也個重要的實現(xiàn)。
在 Java 集合框架中翅敌，HashMap羞福、LinkedHashMap 和 TreeMap 三個映射類基于不同的數(shù)據(jù)結(jié)構(gòu)，并實現(xiàn)了不同的功能蚯涮。
HashMap 底層基于拉鏈?zhǔn)降纳⒘薪Y(jié)構(gòu)治专，并在 JDK 1.8 中引入紅黑樹優(yōu)化過長鏈表的問題≡舛ィ基于這樣結(jié)構(gòu)张峰，HashMap 可提供高效的增刪改查操作。
LinkedHashMap 在其之上棒旗，通過維護一條雙向鏈表喘批，實現(xiàn)了散列數(shù)據(jù)結(jié)構(gòu)的有序遍歷。
TreeMap 底層基于紅黑樹實現(xiàn)铣揉，利用紅黑樹的性質(zhì)饶深，實現(xiàn)了鍵值對排序功能。具體實現(xiàn)我們下次分析逛拱。
