快捷導(dǎo)航

Java中的TreeMap底層源碼分析

更新時(shí)間：2023年12月15日 08:30:48 作者：愛喝咖啡的程序員

這篇文章主要介紹了Java中的TreeMap底層源碼分析,TreeMap與Hashmap、LinkedHashMap不同,他的底層不再是數(shù)組,而是一顆紅黑樹,在插入、刪除或者替換元素時(shí),TreeMap能按照事先約定的順序來對(duì)key進(jìn)行排序和迭代查詢,需要的朋友可以參考下

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

TreeMap與Hashmap、LinkedHashMap不同，他的底層不再是數(shù)組，而是一顆紅黑樹。

在插入、刪除或者替換元素時(shí)，TreeMap能按照事先約定的順序來對(duì)key進(jìn)行排序和迭代查詢。

支持二叉搜索，因此做查詢操作時(shí)，時(shí)間復(fù)雜度是O(logn)，雖然比起純粹使用數(shù)組要慢O(1)，但是比普通的鏈表要快O(n)。

插入數(shù)據(jù)類似鏈表，只調(diào)整幾個(gè)指針就實(shí)現(xiàn)插入操作。

TreeMap的缺點(diǎn)在于，為了使用紅黑樹，每次新增、刪除、修改一個(gè)節(jié)點(diǎn)后，都需要重新調(diào)整整顆樹，達(dá)到紅黑樹的要求，這個(gè)調(diào)整的過程可能涉及到變色，也可能涉及到左旋、右旋，所以耗時(shí)??！

二. 源碼分析

2.1 put(K key, V value)

TreeMap<Integer, String> map = new TreeMap<>();
map.put(2, "張三");
map.put(1, "李四");
map.put(3, "王五");
map.put(4, "趙六");

Treemap默認(rèn)使用key的升序排序，如果遍歷上方的map，能獲取到1->2->3->4排列順序的key-value對(duì)。

我們也可以自定義比較key的方法，具體的做法如下:

Map<Integer, String> map = new TreeMap<Integer, String>(new Comparator<Integer> () {
	@Override
	public int compare(Integer o1, Integer o2) {
		return o2 - o1;
	}
}) {};

此時(shí)，再次遍歷map，能獲取到4->3->2->1排列順序的key-value對(duì)。

我們可以把TreeMap put( )方法的源碼分解成幾個(gè)部分。

首先，判斷當(dāng)前TreeMap有沒有節(jié)點(diǎn)，如果連一個(gè)節(jié)點(diǎn)都沒有，那好辦，就拿著本次待新增的k-v，做成一個(gè)節(jié)點(diǎn)，此時(shí)紅黑樹只有一個(gè)節(jié)點(diǎn)。

Entry<K,V> t = root;
if (t == null) {
	compare(key, key); // type (and possibly null) check
	root = new Entry<>(key, value, null);
	size = 1;
	modCount++;
	return null;
}

接著，將待插入的key與根節(jié)點(diǎn)對(duì)應(yīng)的key進(jìn)行比較，這里就可以自定義比較方式了。

Comparator<? super K> cpr = comparator;
if (cpr != null) {
	do {
		parent = t;
		cmp = cpr.compare(key, t.key);
		if (cmp < 0)
			t = t.left;
		else if (cmp > 0)
			t = t.right;
		else
			return t.setValue(value);
	} while (t != null);
}
else {
	if (key == null)
		throw new NullPointerException();
	@SuppressWarnings("unchecked")
		Comparable<? super K> k = (Comparable<? super K>) key;
	do {
		parent = t;
		cmp = k.compareTo(t.key);
		if (cmp < 0)
			t = t.left;
		else if (cmp > 0)
			t = t.right;
		else
			return t.setValue(value);
	} while (t != null);
}

上圖中這么大一坨代碼，無非就是列舉了兩種情況，如果沒有顯示的給出Comparator，則使用key的compareTo()方法比較大小。如果給出了顯示的Comparator，則使用自定義的compare()方法進(jìn)行比較。

然后，把較小的節(jié)點(diǎn)掛到根節(jié)點(diǎn)的左邊，把較大的節(jié)點(diǎn)掛到根節(jié)點(diǎn)的右邊。這不就是二叉搜索樹的概念么。

if (cmp < 0)
	parent.left = e;
else
	parent.right = e;

最后，使用紅黑樹相關(guān)的算法，利用變色啊、旋轉(zhuǎn)啊等手段，使添加了節(jié)點(diǎn)的二叉搜索樹重新成為紅黑樹。

fixAfterInsertion(e);

2.2 紅黑樹節(jié)點(diǎn)的結(jié)構(gòu)

K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;

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

您可能感興趣的文章:

Java
TreeMap

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java中的TreeMap底層源碼分析

目錄

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

二. 源碼分析

2.1 put(K key, V value)

2.2 紅黑樹節(jié)點(diǎn)的結(jié)構(gòu)

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具