Java中的TreeMap底層源碼分析
一. 基本原理和優(yōu)缺點
TreeMap與Hashmap、LinkedHashMap不同，他的底層不再是數(shù)組，而是一顆紅黑樹。
在插入、刪除或者替換元素時，TreeMap能按照事先約定的順序來對key進行排序和迭代查詢。
支持二叉搜索，因此做查詢操作時，時間復雜度是O(logn)，雖然比起純粹使用數(shù)組要慢O(1)，但是比普通的鏈表要快O(n)。
插入數(shù)據(jù)類似鏈表，只調整幾個指針就實現(xiàn)插入操作。
TreeMap的缺點在于，為了使用紅黑樹，每次新增、刪除、修改一個節(jié)點后，都需要重新調整整顆樹，達到紅黑樹的要求，這個調整的過程可能涉及到變色，也可能涉及到左旋、右旋，所以耗時啊！
二. 源碼分析
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é)點對應的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;
最后，使用紅黑樹相關的算法，利用變色啊、旋轉啊等手段，使添加了節(jié)點的二叉搜索樹重新成為紅黑樹。
fixAfterInsertion(e);
2.2 紅黑樹節(jié)點的結構
K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK;
到此這篇關于Java中的TreeMap底層源碼分析的文章就介紹到這了,更多相關TreeMap源碼分析內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
mybatis Mapper的xml文件中resultType值的使用說明
這篇文章主要介紹了mybatis Mapper的xml文件中resultType值的使用說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
在本篇文章里小編給大家整理的是關于java中堆內存與棧內存的知識點總結，有需要的朋友們可以跟著學習下。2019-12-12
這篇文章主要介紹了Java實現(xiàn)JDK動態(tài)代理的原理詳解，Java常用的動態(tài)代理模式有JDK動態(tài)代理，也有cglib動態(tài)代理，本文重點講解JDK的動態(tài)代理，需要的小伙伴可以參考一下的相關資料2022-07-07
SpringBoot+Shiro+LayUI權限管理系統(tǒng)項目源碼
本項目旨在打造一個基于RBAC架構模式的通用的、并不復雜但易用的權限管理系統(tǒng)，通過SpringBoot+Shiro+LayUI權限管理系統(tǒng)項目可以更好的幫助我們掌握springboot知識點，感興趣的朋友一起看看吧2021-04-04
基于springboot攔截器HandlerInterceptor的注入問題
這篇文章主要介紹了springboot攔截器HandlerInterceptor的注入問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
通過重寫Schedu lingConfigurer方法實現(xiàn)對定時任務的操作，單次執(zhí)行、停止、啟動三個主要的基本功能，動態(tài)的從數(shù)據(jù)庫中獲取配置的定時任務cron信息，通過反射的方式靈活定位到具體的類與方法中2023-02-02
這是一個使用了java+SSM開發(fā)的網上水果商城批發(fā)平臺，是一個實戰(zhàn)小練習，具有水果商城批發(fā)該有的所有功能，感興趣的朋友快來看看吧2022-06-06
這篇文章主要介紹了Java利用序列化實現(xiàn)對象深度clone的方法,實例分析了java序列化及對象克隆的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細介紹了利用HttpClient實現(xiàn)文件上傳，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
下面小編就為大家?guī)硪黄猯og4j.properties 配置(實例講解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08