LinkedHashMap源碼分析
概述
LinkedHashMap是HashMap的子類(lèi)
它能夠?qū)崿F(xiàn)兩大功能：
1.按照插入順序訪問(wèn)
2.按照訪問(wèn)順序調(diào)整元素順序 （實(shí)現(xiàn)LRU）
首先看兩個(gè)使用的示例：
public class LinkedHashMapTest {
public static void main(String[] args) {
// 按照插入順序訪問(wèn)
Map<Integer, String> m = new LinkedHashMap<>();
m.put(1, "a");
m.put(2, "b");
m.put(3, "c");
m.put(4, "d");
m.put(5, "e");
m.put(6, "f");
// 訪問(wèn)元素不會(huì)調(diào)整該元素的順序
m.put(3, "cc");
Set<Map.Entry<Integer, String>> entries = m.entrySet();
for (Map.Entry<Integer, String> entry : entries) {
System.out.println(entry);
}
System.out.println();
// 按照訪問(wèn)順序調(diào)整順序
Map<Integer, String> m2 = new LinkedHashMap<>(16, 0.75f, true);
m2.put(1, "aa");
m2.put(2, "bb");
m2.put(3, "cc");
m2.put(4, "dd");
printMap(m2);
System.out.println(m2.get(3));
printMap(m2);
System.out.println(m2.get(2));
printMap(m2);
}
public static void printMap(Map<Integer, String> map) {
System.out.println(map);
}
}
輸出結(jié)果
1=a
2=b
3=cc
4=d
5=e
6=f
{1=aa, 2=bb, 3=cc, 4=dd}
cc
{1=aa, 2=bb, 4=dd, 3=cc}
bb
{1=aa, 4=dd, 3=cc, 2=bb}
可以看到 兩次實(shí)驗(yàn)使用了LinkedHashMap 構(gòu)造函數(shù)的不同參數(shù)，主要為accessOrder 參數(shù)。該參數(shù)為true表示訪問(wèn)時(shí)調(diào)整它的順序。
構(gòu)造一個(gè)LRU
public class LruCache<K, V> extends LinkedHashMap<K, V> {
private int maxSize;
public LruCache(int maxSize) {
super(16, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
public static void main(String[] args) {
LruCache<Integer, String> lru = new LruCache<>(5);
lru.put(1, "a");
lru.put(2, "b");
lru.put(3, "c");
lru.put(4, "d");
lru.put(5, "e");
System.out.println(lru);
lru.get(3);
System.out.println(lru);
lru.put(6, "f");
System.out.println(lru);
}
}
輸出結(jié)果為：
{1=a, 2=b, 3=c, 4=d, 5=e}
{1=a, 2=b, 4=d, 5=e, 3=c}
{2=b, 4=d, 5=e, 3=c, 6=f}
可以看到
1.訪問(wèn)元素后，該被訪問(wèn)的元素會(huì)被添加到鏈表的最后位置
2.重寫(xiě)removeEldestEntry方法后，按照策略刪除最少訪問(wèn)的元素，即頭部元素
而該鏈表為一個(gè)雙向鏈表，后面源碼分析部分會(huì)詳細(xì)說(shuō)明。
和HashMap的關(guān)系
（1）數(shù)據(jù)結(jié)構(gòu)
LinkedHashMap繼承自HashMap，有如下特殊數(shù)據(jù)結(jié)構(gòu)
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);
}
}
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;
Entry為L(zhǎng)inkedHashMap中的節(jié)點(diǎn)，內(nèi)部維護(hù)兩個(gè)指針，分別指向后一個(gè)和前一個(gè)元素，可以組成一個(gè)雙向鏈表。
另有兩個(gè)節(jié)點(diǎn)保存頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
一個(gè)bool類(lèi)型維護(hù)是否根據(jù)訪問(wèn)順序調(diào)整節(jié)點(diǎn)順序
（2）方法
在HashMap中使用了模板方法模式，有幾個(gè)鉤子方法，供子類(lèi)實(shí)現(xiàn)
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
值得一提的是LinkedHashMap的節(jié)點(diǎn)為Entry，而不是HashMap的HashMap.Node。LinkedHashMap節(jié)點(diǎn)的創(chuàng)建是在自己的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);
// 被訪問(wèn)的元素（這里為添加的元素）放到鏈表尾部
linkNodeLast(p);
return p;
}
覆蓋了HashMap中的newNode實(shí)現(xiàn)，HashMap中的newNode是在put方法中被調(diào)用。
而且LinkedHashMap中的newNode添加了linkNodeLast方法調(diào)整被訪問(wèn)節(jié)點(diǎn)的順序，將它放到鏈表尾部。
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 取出維護(hù)的 tail 指針，last指向的是現(xiàn)有的尾部元素
LinkedHashMap.Entry<K,V> last = tail;
// 指向新創(chuàng)建的元素
tail = p;
// 元素為空，head也指向該元素，鏈表中只有一個(gè)元素
if (last == null)
head = p;
// 尾元素不為null，新增元素維護(hù)雙向鏈表結(jié)構(gòu)
else {
// 新元素的before指向最后一個(gè)元素
p.before = last;
// 最后一個(gè)元素after指向新元素
last.after = p;
}
}
HashMap中的鉤子方法我們來(lái)分析下源碼
首先是按照訪問(wèn)有序時(shí)，將被訪問(wèn)元素放到鏈表尾端的方法afterNodeAccess
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 按照 訪問(wèn)有序規(guī)則并且 剛才訪問(wèn)的元素不是尾元素，需要調(diào)整結(jié)構(gòu)
if (accessOrder && (last = tail) != e) {
// p指向剛才訪問(wèn)的節(jié)點(diǎn)，b指向p的前驅(qū)，a指向p的后繼
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// p的后驅(qū)為null
p.after = null;
// p為雙向鏈表頭節(jié)點(diǎn)，則頭節(jié)點(diǎn)指向p的后繼a
if (b == null)
head = a;
// p不為頭節(jié)點(diǎn)，則p的前驅(qū)直接指向p的后繼
else
b.after = a;
// 下面為維護(hù)向前的指針
// 后繼不為null，后繼的前驅(qū)指向p的前驅(qū)
if (a != null)
a.before = b;
// 后繼為null，last指針指向前驅(qū)節(jié)點(diǎn)
else
last = b;
// last指針為null，頭節(jié)點(diǎn)為p，只有一個(gè)元素
if (last == null)
head = p;
// 不只有p這個(gè)元素，則將p的前向指針指向最后一個(gè)節(jié)點(diǎn)，last的后繼指向p
// 把p添加在雙向鏈表的尾部
else {
p.before = last;
last.after = p;
}
// 尾指針指向p
tail = p;
// 維護(hù)修改次數(shù)變量
++modCount;
}
}
接著是插入元素后，將最老的元素刪除，該方法的調(diào)用時(shí)機(jī)在hashMapput元素的最后，默認(rèn)的put方法會(huì)將evict置為true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// evict為true，頭節(jié)點(diǎn)不為null，重寫(xiě)的removeEldestEntry為true，則刪除頭部元素
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
接著調(diào)用HashMap的remove方法，可以看到其中afterNodeRemoval也是一個(gè)鉤子方法
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 鏈表不為null，hash值對(duì)應(yīng)的元素不為null，p為hash路由到的table中的元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 哈希值相同，key相同，沒(méi)有hash沖突，node為p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 產(chǎn)生了hash沖突，hash值不一樣
else if ((e = p.next) != null) {
// p是紅黑樹(shù)
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// 鏈表中查找
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 查找到元素，value不為null則刪除元素
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 從紅黑樹(shù)中刪除
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 從沒(méi)有沖突的節(jié)點(diǎn)中刪除
else if (node == p)
tab[index] = node.next;
// 從有沖突的鏈表中刪除
else
p.next = node.next;
// 維護(hù)操作次數(shù)
++modCount;
--size;
// 鉤子方法
afterNodeRemoval(node);
return node;
}
}
return null;
}
afterNodeRemoval方法在LinkedHashMap刪除節(jié)點(diǎn)后，會(huì)從LinedHashMap的雙向鏈表中去除該節(jié)點(diǎn)。
void afterNodeRemoval(Node<K,V> e) { // unlink
// 待刪除節(jié)點(diǎn)為p，前驅(qū)節(jié)點(diǎn)為b，后繼節(jié)點(diǎn)為a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 斷開(kāi)待刪除節(jié)點(diǎn)的前驅(qū)后繼
p.before = p.after = null;
// 待刪除為頭，則后繼修改為頭
if (b == null)
head = a;
// 待刪除不為頭，則前驅(qū)指向后繼
else
b.after = a;
// 待刪除為尾，則前驅(qū)修改為尾
if (a == null)
tail = b;
// 待刪除不為尾，則后繼的前驅(qū)指針指向前驅(qū)
else
a.before = b;
}
還有一個(gè)get方法也會(huì)訪問(wèn)元素，LinkedHashMap重寫(xiě)了該方法
public V get(Object key) {
Node<K,V> e;
// 先從HashMap的getNode中獲取元素，為null則返回
if ((e = getNode(hash(key), key)) == null)
return null;
// 按訪問(wèn)順序
if (accessOrder)
// 調(diào)用afterNodeAccess，將訪問(wèn)元素放到雙向鏈表尾部
afterNodeAccess(e);
return e.value;
}
containsValue也是LinkedHashMap重寫(xiě)的方法
通過(guò)雙向鏈表直接遍歷元素是否存在
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;
}
總結(jié)：
1.LinkedHashMap可以實(shí)現(xiàn)按插入順序訪問(wèn)
2.LinkedHashMap可以實(shí)現(xiàn)按照訪問(wèn)調(diào)整元素順序，實(shí)現(xiàn)LRU
3.模板方法模式的使用，鉤子方法的使用
