Java中的TreeMap底層源碼分析
一. 基本原理和優(yōu)缺點
TreeMap與Hashmap、LinkedHashMap不同，他的底層不再是數(shù)組，而是一顆紅黑樹。
在插入、刪除或者替換元素時，TreeMap能按照事先約定的順序來對key進行排序和迭代查詢。
支持二叉搜索，因此做查詢操作時，時間復雜度是O(logn)，雖然比起純粹使用數(shù)組要慢O(1)，但是比普通的鏈表要快O(n)。
插入數(shù)據(jù)類似鏈表，只調(diào)整幾個指針就實現(xiàn)插入操作。
TreeMap的缺點在于，為了使用紅黑樹，每次新增、刪除、修改一個節(jié)點后，都需要重新調(diào)整整顆樹，達到紅黑樹的要求，這個調(diào)整的過程可能涉及到變色，也可能涉及到左旋、右旋，所以耗時啊！
二. 源碼分析
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默認使用key的升序排序，如果遍歷上方的map，能獲取到1->2->3->4排列順序的key-value對。
我們也可以自定義比較key的方法，具體的做法如下:
Map<Integer, String> map = new TreeMap<Integer, String>(new Comparator<Integer> () {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}) {};此時，再次遍歷map，能獲取到4->3->2->1排列順序的key-value對。
我們可以把TreeMap put( )方法的源碼分解成幾個部分。
首先，判斷當前TreeMap有沒有節(jié)點，如果連一個節(jié)點都沒有，那好辦，就拿著本次待新增的k-v，做成一個節(jié)點，此時紅黑樹只有一個節(jié)點。
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é)點對應(yīng)的key進行比較，這里就可以自定義比較方式了。
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()方法進行比較。
然后，把較小的節(jié)點掛到根節(jié)點的左邊，把較大的節(jié)點掛到根節(jié)點的右邊。這不就是二叉搜索樹的概念么。
if (cmp < 0) parent.left = e; else parent.right = e;
最后，使用紅黑樹相關(guān)的算法，利用變色啊、旋轉(zhuǎn)啊等手段，使添加了節(jié)點的二叉搜索樹重新成為紅黑樹。
fixAfterInsertion(e);
2.2 紅黑樹節(jié)點的結(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于Java獲取月份的三種方法,文中分別介紹了使用java.util.Date、java.util.Calendar和java.time包中的LocalDate類,推薦使用java.time包中的LocalDate,因為它提供了更為簡潔和強大的功能,需要的朋友可以參考下2024-12-12
Springboot中的Validation參數(shù)校驗詳解
這篇文章主要介紹了Springboot中的Validation參數(shù)校驗詳解,Springboot參數(shù)校驗是一種常用的驗證機制,在傳遞參數(shù)時進行校驗,以確保參數(shù)的有效性和正確性,該機制可以幫助開發(fā)者在代碼實現(xiàn)前就避免一些常見的錯誤,需要的朋友可以參考下2023-10-10
詳解在Spring-Boot中實現(xiàn)通用Auth認證的幾種方式
這篇文章主要介紹了詳解在Spring-Boot中實現(xiàn)通用Auth認證的幾種方式，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-07-07
下面小編就為大家?guī)硪黄猭afka生產(chǎn)實踐(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
Spring AOP面向切面編程實現(xiàn)原理方法詳解
這篇文章主要介紹了Spring AOP面向切面編程實現(xiàn)原理方法詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08
Spring Boot整合Mybatis并完成CRUD操作的實現(xiàn)示例
這篇文章主要介紹了Spring Boot整合Mybatis并完成CRUD操作的實現(xiàn)示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-12-12
這篇文章主要介紹了HashMap底層實現(xiàn)原理詳解,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-08-08
詳解SpringMVC的url-pattern配置及原理剖析
這篇文章主要介紹了SpringMVC的url-pattern配置及原理剖析，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-06-06
這篇文章主要介紹了MyBatis實現(xiàn)物理分頁的實例,MyBatis使用RowBounds實現(xiàn)的分頁是邏輯分頁，有興趣的可以了解一下。2017-01-01
java sftp下載文件報錯Caused by:com.jcraft.jsch.JSchExcep
文章講述了作者在日常工作中遇到的JSch連接問題,經(jīng)過分析發(fā)現(xiàn)是由于連接泄露導致的,作者提出了解決方案,并給出了使用建議：1.在finally代碼塊中關(guān)閉連接；2.在真正使用階段再創(chuàng)建連接,避免創(chuàng)建后不使用又忘記關(guān)閉連接2024-11-11