一文帶你深入了解Java?TreeMap
概述
TreeMap是Map家族中的一員，也是用來存放key-value鍵值對的。平時在工作中使用的可能并不多，它最大的特點是遍歷時是有順序的，根據(jù)key的排序規(guī)則來，那么它具體是如何使用，又是怎么實現(xiàn)的呢？本文基于jdk8做一個講解。
TreeMap介紹
TreeMap是一個基于key有序的key value散列表。
- map根據(jù)其鍵的自然順序排序，或者根據(jù)map創(chuàng)建時提供的Comparator排序
- 不是線程安全的
- key 不可以存入null
- 底層是基于紅黑樹實現(xiàn)的
以上是TreeMap的類結構圖：
- 實現(xiàn)了NavigableMap接口，NavigableMap又實現(xiàn)了Map接口，提供了導航相關的方法。
- 繼承了AbstractMap，該方法實現(xiàn)Map操作的骨干邏輯。
- 實現(xiàn)了Cloneable接口，標記該類支持clone方法復制
- 實現(xiàn)了Serializable接口，標記該類支持序列化
構造方法
TreeMap()
說明：使用鍵的自然排序構造一個新的空樹映射。
TreeMap(Comparator<? super K> comparator)
說明：構造一個新的空樹映射，根據(jù)給定的比較器排序。
TreeMap(Map<? extends K,? extends V> m)
說明：構造一個新的樹映射，包含與給定映射相同的映射，按照鍵的自然順序排序。
TreeMap(SortedMap<K,? extends V> m)
說明：構造一個新的樹映射，包含相同的映射，并使用與指定排序映射相同的順序。
關鍵方法
這邊主要講解下NavigableMap和SortedMap提供的一些方法，Map相關的方法大家應該都很熟悉了。
SortedMap接口：
Comparator<? super K> comparator()
返回用于排序此映射中的鍵的比較器，如果此映射使用其鍵的自然排序，則返回null。
Set<Map.Entry<K,V>> entrySet()
返回此映射中包含的映射的Set視圖。
K firstKey()
返回當前映射中的第一個(最低)鍵。
K lastKey()
返回當前映射中的最后(最高)鍵。
NavigableMap接口：
Map.Entry<K,V> ceilingEntry(K key)
返回與大于或等于給定鍵的最小鍵相關聯(lián)的鍵值映射，如果沒有這樣的鍵則返回null。
K ceilingKey(K key)
返回大于或等于給定鍵的最小鍵，如果沒有這樣的鍵，則返回null。
NavigableMap<K,V> descendingMap()
返回此映射中包含的映射的倒序視圖。
Map.Entry<K,V> firstEntry()
返回與該映射中最小的鍵關聯(lián)的鍵值映射，如果映射為空，則返回null。
Map.Entry<K,V> floorEntry(K key)
返回與小于或等于給定鍵的最大鍵相關聯(lián)的鍵值映射，如果沒有這樣的鍵則返回null。
SortedMap<K,V> headMap(K toKey)
返回該映射中鍵嚴格小于toKey的部分的視圖。
Map.Entry<K,V> higherEntry(K key)
返回與嚴格大于給定鍵的最小鍵關聯(lián)的鍵值映射，如果沒有這樣的鍵，則返回null。
Map.Entry<K,V> lastEntry()
返回與此映射中最大鍵關聯(lián)的鍵值映射，如果映射為空，則返回null。
Map.Entry<K,V> lowerEntry(K key)
返回與嚴格小于給定鍵的最大鍵關聯(lián)的鍵值映射，如果沒有這樣的鍵，則返回null。
Map.Entry<K,V> pollFirstEntry()
刪除并返回與該映射中最小的鍵關聯(lián)的鍵值映射，如果映射為空，則返回null。
Map.Entry<K,V> pollLastEntry()
刪除并返回與此映射中最大鍵關聯(lián)的鍵值映射，如果映射為空，則返回null。
SortedMap<K,V> subMap(K fromKey, K toKey)
返回該映射中鍵范圍從fromKey(包含)到toKey(獨占)的部分的視圖。
SortedMap<K,V> tailMap(K fromKey)
返回該映射中鍵大于或等于fromKey的部分的視圖。
使用案例
驗證順序性
@Test
public void test1() {
Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(16, "a");
treeMap.put(1, "b");
treeMap.put(4, "c");
treeMap.put(3, "d");
treeMap.put(8, "e");
// 遍歷
System.out.println("默認排序：");
treeMap.forEach((key, value) -> {
System.out.println("key: " + key + ", value: " + value);
});
// 構造方法傳入比較器
Map<Integer, String> tree2Map = new TreeMap<>((o1, o2) -> o2 - o1);
tree2Map.put(16, "a");
tree2Map.put(1, "b");
tree2Map.put(4, "c");
tree2Map.put(3, "d");
tree2Map.put(8, "e");
// 遍歷
System.out.println("倒序排序：");
tree2Map.forEach((key, value) -> {
System.out.println("key: " + key + ", value: " + value);
});
}運行結果：
驗證不能存儲null
@Test
public void test2() {
Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(null, "a");
}運行結果：
驗證NavigableMap相關方法
@Test
public void test3() {
NavigableMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(16, "a");
treeMap.put(1, "b");
treeMap.put(4, "c");
treeMap.put(3, "d");
treeMap.put(8, "e");
// 獲取大于等于5的key
Integer ceilingKey = treeMap.ceilingKey(5);
System.out.println("ceilingKey 5 is " + ceilingKey);
// 獲取最大的key
Integer lastKey = treeMap.lastKey();
System.out.println("lastKey is " + lastKey);
}運行結果：
核心機制
實現(xiàn)原理
大家有想過TreeMap的底層是怎么實現(xiàn)的嗎，是如何維護key的順序呢？答案就是基于紅黑樹實現(xiàn)的。
那什么是紅黑樹呢？我們在這里簡單的認識一下，了解一下紅黑樹的特點：紅黑樹是一顆自平衡的排序二叉樹。我們就先從二叉樹開始說起。
二叉樹
二叉樹很容易理解，就是一棵樹分倆叉。
上面這顆就是一顆最普通的二叉樹。但是你會發(fā)現(xiàn)看起來不那么美觀，因為你以H為根節(jié)點，發(fā)現(xiàn)左右兩邊高低不平衡，高度相差達到了2。于是出現(xiàn)了平衡二叉樹，使得左右兩邊高低差不多。
平衡二叉樹
這下子應該能看到，不管是從任何一個字母為根節(jié)點，左右兩邊的深度差不了2，最多是1。這就是平衡二叉樹。不過好景不長，有一天，突然要把字母變成數(shù)字，還要保持這種特性怎么辦呢？于是又出現(xiàn)了平衡二叉排序樹。
平衡二叉排序樹
不管是從長相（平衡），還是從規(guī)律（排序）感覺這棵樹超級完美。但是有一個問題，那就是在增加刪除節(jié)點的時候，你要時刻去讓這棵樹保持平衡，需要做太多的工作了，旋轉的次數(shù)超級多，于是乎出現(xiàn)了紅黑樹。
紅黑樹
這就是傳說中的紅黑樹，和平衡二叉排序樹的區(qū)別就是每個節(jié)點涂上了顏色，他有下列五條性質(zhì)：
- 每個節(jié)點都只能是紅色或者黑色
- 根節(jié)點是黑色
- 每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。
- 如果一個結點是紅的，則它兩個子節(jié)點都是黑的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色結點。
- 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
這些性質(zhì)有什么優(yōu)點呢？就是插入效率超級高。因為在插入一個元素的時候，最多只需三次旋轉，O(1)的復雜度，但是有一點需要說明他的查詢效率略微遜色于平衡二叉樹，因為他比平衡二叉樹會稍微不平衡最多一層，也就是說紅黑樹的查詢性能只比相同內(nèi)容的avl樹最多多一次比較。如何去旋轉呢？如下圖所示。
首先是左旋：
然后是右旋：
紅黑樹更詳細的內(nèi)容可以參考文章：Java紅黑樹的數(shù)據(jù)結構與算法解析
源碼解析
成員變量
//這是一個比較器，方便插入查找元素等操作 private final Comparator<? super K> comparator; //紅黑樹的根節(jié)點：每個節(jié)點是一個Entry private transient Entry<K,V> root; //集合元素數(shù)量 private transient int size = 0; //集合修改的記錄 private transient int modCount = 0;
- comparator是一個排序器，作為key的排序規(guī)則
- root是紅黑樹的根節(jié)點，說明的確底層用的紅黑樹作為數(shù)據(jù)結構。
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
//左子樹
Entry<K,V> left;
//右子樹
Entry<K,V> right;
//父節(jié)點
Entry<K,V> parent;
//每個節(jié)點的顏色：紅黑樹屬性。
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
查找get方法
TreeMap基于紅黑樹實現(xiàn)，而紅黑樹是一種自平衡二叉查找樹，所以 TreeMap 的查找操作流程和二叉查找樹一致。二叉樹的查找流程是這樣的，先將目標值和根節(jié)點的值進行比較，如果目標值小于根節(jié)點的值，則再和根節(jié)點的左孩子進行比較。如果目標值大于根節(jié)點的值，則繼續(xù)和根節(jié)點的右孩子比較。在查找過程中，如果目標值和二叉樹中的某個節(jié)點值相等，則返回 true，否則返回 false。TreeMap 查找和此類似，只不過在 TreeMap 中，節(jié)點（Entry）存儲的是鍵值對<k,v>。在查找過程中，比較的是鍵的大小，返回的是值，如果沒找到，則返回null。TreeMap 中的查找方法是get。
public V get(Object key) {
//調(diào)用 getEntry方法查找
Entry<K,V> p = getEntry(key);
return (p==null ? null : p. value);
}
final Entry<K,V> getEntry(Object key) {
/ 如果比較器為空，只是用key作為比較器查詢
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 取得root節(jié)點
Entry<K,V> p = root;
//核心來了：從root節(jié)點開始查找，根據(jù)比較器判斷是在左子樹還是右子樹
while (p != null) {
int cmp = k.compareTo(p.key );
if (cmp < 0)
p = p. left;
else if (cmp > 0)
p = p. right;
else
return p;
}插入put方法
我們來看下關鍵的插入方法，在插入時候是如何維護key的。
public V put(K key, V value) {
Entry<K,V> t = root;
// 1.如果根節(jié)點為 null，將新節(jié)點設為根節(jié)點
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
//如果root不為null，說明已存在元素
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果比較器不為null 則使用比較器
if (cpr != null) {
//找到元素的插入位置
do {
parent = t;
cmp = cpr.compare(key, t.key);
//當前key小于節(jié)點key 向左子樹查找
if (cmp < 0)
t = t.left;
//當前key大于節(jié)點key 向右子樹查找
else if (cmp > 0)
t = t.right;
else
//相等的情況下 直接更新節(jié)點值
return t.setValue(value);
} while (t != null);
}
//如果比較器為null 則使用默認比較器
else {
//如果key為null 則拋出異常
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);
}
Entry<K,V> e = new Entry<>(key, value, parent);
//根據(jù)比較結果決定插入到左子樹還是右子樹
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//保持紅黑樹性質(zhì)，進行紅黑樹的旋轉等操作
fixAfterInsertion(e);
size++;
modCount++;
return null;
}比較關鍵的就是fixAfterInsertion方法， 看懂這個方法需要你對紅黑樹的機制比較了解。
private void fixAfterInsertion(Entry<K,V> x) {
// 將新插入節(jié)點的顏色設置為紅色
x. color = RED;
// while循環(huán)，保證新插入節(jié)點x不是根節(jié)點或者新插入節(jié)點x的父節(jié)點不是紅色（這兩種情況不需要調(diào)整）
while (x != null && x != root && x. parent.color == RED) {
// 如果新插入節(jié)點x的父節(jié)點是祖父節(jié)點的左孩子
if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
// 取得新插入節(jié)點x的叔叔節(jié)點
Entry<K,V> y = rightOf(parentOf (parentOf(x)));
// 如果新插入x的父節(jié)點是紅色
if (colorOf(y) == RED) {
// 將x的父節(jié)點設置為黑色
setColor(parentOf (x), BLACK);
// 將x的叔叔節(jié)點設置為黑色
setColor(y, BLACK);
// 將x的祖父節(jié)點設置為紅色
setColor(parentOf (parentOf(x)), RED);
// 將x指向祖父節(jié)點，如果x的祖父節(jié)點的父節(jié)點是紅色，按照上面的步奏繼續(xù)循環(huán)
x = parentOf(parentOf (x));
} else {
// 如果新插入x的叔叔節(jié)點是黑色或缺少，且x的父節(jié)點是祖父節(jié)點的右孩子
if (x == rightOf( parentOf(x))) {
// 左旋父節(jié)點
x = parentOf(x);
rotateLeft(x);
}
// 如果新插入x的叔叔節(jié)點是黑色或缺少，且x的父節(jié)點是祖父節(jié)點的左孩子
// 將x的父節(jié)點設置為黑色
setColor(parentOf (x), BLACK);
// 將x的祖父節(jié)點設置為紅色
setColor(parentOf (parentOf(x)), RED);
// 右旋x的祖父節(jié)點
rotateRight( parentOf(parentOf (x)));
}
} else { // 如果新插入節(jié)點x的父節(jié)點是祖父節(jié)點的右孩子和上面的相似
Entry<K,V> y = leftOf(parentOf (parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf (x), BLACK);
setColor(y, BLACK);
setColor(parentOf (parentOf(x)), RED);
x = parentOf(parentOf (x));
} else {
if (x == leftOf( parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf (x), BLACK);
setColor(parentOf (parentOf(x)), RED);
rotateLeft( parentOf(parentOf (x)));
}
}
}
// 最后將根節(jié)點設置為黑色
root.color = BLACK;
}刪除remove方法
刪除remove是最復雜的方法。
public V remove(Object key) {
// 根據(jù)key查找到對應的節(jié)點對象
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
// 記錄key對應的value，供返回使用
V oldValue = p. value;
// 刪除節(jié)點
deleteEntry(p);
return oldValue;
}private void deleteEntry(Entry<K,V> p) {
modCount++;
//元素個數(shù)減一
size--;
// 如果被刪除的節(jié)點p的左孩子和右孩子都不為空，則查找其替代節(jié)
if (p.left != null && p. right != null) {
// 查找p的替代節(jié)點
Entry<K,V> s = successor (p);
p. key = s.key ;
p. value = s.value ;
p = s;
}
Entry<K,V> replacement = (p. left != null ? p.left : p. right);
if (replacement != null) {
// 將p的父節(jié)點拷貝給替代節(jié)點
replacement. parent = p.parent ;
// 如果替代節(jié)點p的父節(jié)點為空，也就是p為跟節(jié)點，則將replacement設置為根節(jié)點
if (p.parent == null)
root = replacement;
// 如果替代節(jié)點p是其父節(jié)點的左孩子，則將replacement設置為其父節(jié)點的左孩子
else if (p == p.parent. left)
p. parent.left = replacement;
// 如果替代節(jié)點p是其父節(jié)點的左孩子，則將replacement設置為其父節(jié)點的右孩子
else
p. parent.right = replacement;
// 將替代節(jié)點p的left、right、parent的指針都指向空
p. left = p.right = p.parent = null;
// 如果替代節(jié)點p的顏色是黑色，則需要調(diào)整紅黑樹以保持其平衡
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
// 如果要替代節(jié)點p沒有父節(jié)點，代表p為根節(jié)點，直接刪除即可
root = null;
} else {
// 如果p的顏色是黑色，則調(diào)整紅黑樹
if (p.color == BLACK)
fixAfterDeletion(p);
// 下面刪除替代節(jié)點p
if (p.parent != null) {
// 解除p的父節(jié)點對p的引用
if (p == p.parent .left)
p. parent.left = null;
else if (p == p.parent. right)
p. parent.right = null;
// 解除p對p父節(jié)點的引用
p. parent = null;
}
}
}最終還是落到了對紅黑樹節(jié)點的刪除上，需要維持紅黑樹的特性，做一系列的工作。
到此這篇關于一文帶你深入了解Java TreeMap的文章就介紹到這了,更多相關Java TreeMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Java線程休眠之sleep方法詳解,Thread?類中有一個靜態(tài)方法的sleep方法,當該線程調(diào)用sleep方法后,就會暫時讓CPU的調(diào)度權,但是監(jiān)視器資源比如鎖并不會釋放出去,需要的朋友可以參考下2024-01-01
IntelliJ IDEA下自動生成Hibernate映射文件以及實體類
這篇文章主要介紹了IntelliJ IDEA下自動生成Hibernate映射文件以及實體類，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-11-11
這篇文章主要介紹了如何使用IDEA從SVN服務端檢出項目問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
springIOC的使用流程及spring中使用類型轉換器的方式
Spring IOC是Spring框架的核心原理之一，它是一種軟件設計模式，用于管理應用程序中的對象依賴關系，這篇文章主要介紹了springIOC的使用流程以及spring中如何使用類型轉換器,需要的朋友可以參考下2023-06-06
JAVA序列化Serializable及Externalizable區(qū)別詳解
這篇文章主要介紹了JAVA序列化Serializable及Externalizable區(qū)別詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-07-07
Spring Boot自定義favicon實現(xiàn)方法實例解析
這篇文章主要介紹了Spring Boot自定義favicon實現(xiàn)方法實例解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08
這篇文章主要介紹了一次 Java 內(nèi)存泄漏的排查過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-07-07
SpringBoot中的@CacheEvict 注解的實現(xiàn)
本文主要介紹了SpringBoot中的@CacheEvict注解的實現(xiàn),@CacheEvict 注解用于清空緩存,文中通過示例代碼介紹的非常詳細,需要的朋友們下面隨著小編來一起學習學習吧2024-03-03
設置Myeclipse中的代碼格式化、注釋模板及保存時自動格式化
這篇文章主要介紹了設置Myeclipse中的代碼格式化、注釋模板及保存時自動格式化方法,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了sprinboot項目啟動一半到圖形化界面卡住了的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-10-10