一. 基本原理和優(yōu)缺點(diǎn)

LinkedHashMap能記錄你插入元素的順序，在遍歷時(shí)，能按照插入的順序給你遍歷出來(lái)。

LinkedHashMap是HashMap的子類，所以基本的操作與hashmap類似。不過(guò)呢，在插入、刪除、替換key-value對(duì)的時(shí)候，LinkedHashMap會(huì)維護(hù)一個(gè)鏈表結(jié)構(gòu)，專門(mén)用來(lái)記錄key-value對(duì)的順序。當(dāng)我們遍歷LinkedHashMap時(shí)，就能按照順序把key-value來(lái)遍歷出來(lái)。

所以啊，別看LinkedHashMap的名字中帶有Linked，其實(shí)它的底層仍然是數(shù)組實(shí)現(xiàn)的。

當(dāng)刪除元素時(shí)，它會(huì)在雙向鏈表的尾部刪除節(jié)點(diǎn)，當(dāng)查詢?cè)貢r(shí)，實(shí)際上是在迭代雙向鏈表，從頭節(jié)點(diǎn)開(kāi)始迭代。用于維護(hù)雙向鏈表的順序。

這里面有一個(gè)非常核心的參數(shù): accessOrder。

二. 源碼分析

2.1 put(K key, V value) 初次插入

絕大部分代碼邏輯與hashmap完全一樣，只不過(guò)，LinkedHashMap自己重寫(xiě)了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);
	linkNodeLast(p);
	return p;
}

將節(jié)點(diǎn)封裝成了LinkedHashMap.Entry對(duì)象，然后使用linkNodeLast()掛載節(jié)點(diǎn)。

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;
	}
}

這里可以看到，LinkedHashMap內(nèi)部維護(hù)了兩個(gè)指針head和tail，分別指向順序鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)。

每當(dāng)我們向LinkedHashMap內(nèi)新增一個(gè)key-value，就會(huì)在順序鏈表的末尾掛載一個(gè)順序節(jié)點(diǎn)。這個(gè)掛載的過(guò)程其實(shí)就是對(duì)雙向鏈表新增一個(gè)節(jié)點(diǎn)。

2.2 put(K key, V value) 覆蓋已經(jīng)存在的key

如果LinkedHashMap中已經(jīng)插入了key1-value1，此時(shí)我們插入key1-value2，會(huì)產(chǎn)生什么后果呢？

答案是，key1在LinkedHashMap內(nèi)的插入順序保持不變，但是value被覆蓋。

關(guān)于覆蓋的操作，由于我們熟悉HashMap的源碼，所以立刻可以鎖定到hashmap的putVal()內(nèi)如下代碼塊:

if (e != null) { // existing mapping for key
	V oldValue = e.value;
	if (!onlyIfAbsent || oldValue == null)
		e.value = value;
	afterNodeAccess(e);
	return oldValue;
}

如果在插入之前，能找到這個(gè)key對(duì)應(yīng)的節(jié)點(diǎn)，那么就用新的value覆蓋這個(gè)節(jié)點(diǎn)內(nèi)的舊value，接著執(zhí)行afterNodeAccess(e)。

注意，LinkedHashMap重寫(xiě)了afterNodeAccess(e)。

void afterNodeAccess(Node<K,V> e) { // move node to last
	LinkedHashMap.Entry<K,V> last;
	if (accessOrder && (last = tail) != e) {
		LinkedHashMap.Entry<K,V> p =
			(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
		p.after = null;
		if (b == null)
			head = a;
		else
			b.after = a;
		if (a != null)
			a.before = b;
		else
			last = b;
		if (last == null)
			head = p;
		else {
			p.before = last;
			last.after = p;
		}
		tail = p;
		++modCount;
	}
}

LinkedHashMap有一個(gè)非常重要的參數(shù)，accessOrder ，它可以通過(guò)入?yún)?，?jīng)過(guò)構(gòu)造函數(shù)傳入LinkedHashMap。accessOrder默認(rèn)等于false，這就意味著，你覆蓋或者查詢這個(gè)key，都不會(huì)改變key在鏈表里的順序。當(dāng)它等于true時(shí)，就截然相反了，每當(dāng)你覆蓋或者查詢這個(gè)key，LinkedHashMap就會(huì)把這個(gè)key挪動(dòng)到順序鏈表的末尾。

2.3 remove

大部分的邏輯仍然走的是hashmap的removeNode()，只不過(guò)LinkedHashMap重寫(xiě)了afterNodeRemoval( )。

void afterNodeRemoval(Node<K,V> e) { // unlink
	LinkedHashMap.Entry<K,V> p =
		(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
	p.before = p.after = null;
	if (b == null)
		head = a;
	else
		b.after = a;
	if (a == null)
		tail = b;
	else
		a.before = b;
}

到此這篇關(guān)于Java中的LinkedHashMap源碼分析的文章就介紹到這了,更多相關(guān)LinkedHashMap源碼內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論