阿里面試官：你說一下Java的TreeMap底層實現(xiàn)原理？
阿里這段時間忙著制定下半年的OKR，其實在制定OKR的時候就能看出團隊里誰是領(lǐng)導(dǎo)的嫡系，誰是團隊的邊角料。嫡系的OKR都是從領(lǐng)導(dǎo)的核心項目分出來的，而其他人的OKR不會體現(xiàn)在領(lǐng)導(dǎo)的OKR里面，只配給嫡系做打下手的工作。
“員工的績效，在制定OKR的時候，已經(jīng)確定了”。
職場失意，摸魚得意。我還是安心的更新《解讀Java源碼專欄》，在這個系列中，我將手把手帶著大家剖析Java核心組件的源碼，內(nèi)容包含集合、線程、線程池、并發(fā)、隊列等，深入了解其背后的設(shè)計思想和實現(xiàn)細(xì)節(jié)，輕松應(yīng)對工作面試。 這是解讀Java源碼系列的第六篇，將跟大家一起學(xué)習(xí)Java中比較特殊的數(shù)據(jù)結(jié)構(gòu) - TreeMap。
引言
上篇文章講到LinkedHashMap可以保證元素的插入順序或者訪問順序，而TreeMap也能保證元素順序，不過按照鍵的順序進行排序。插入到TreeMap中的鍵值對，會自動按照鍵的順序進行排序。
簡介
HashMap底層結(jié)構(gòu)是基于數(shù)組實現(xiàn)的，而TreeMap底層結(jié)構(gòu)是基于紅黑樹實現(xiàn)的。TreeMap利用紅黑樹的特性實現(xiàn)對鍵的排序。 額外介紹一下紅黑樹的特性：
- 節(jié)點是紅色或者黑色
- 根節(jié)點是黑色
- 所有葉子節(jié)點是黑色
- 每個紅色結(jié)點的兩個子結(jié)點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結(jié)點）
- 從任一結(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點。
紅黑樹是基于平衡二叉樹的改進，而平衡二叉樹是為了解決二叉搜索樹在特殊情況下，退化成鏈表，查找、插入效率退化成 O(n)，規(guī)定左右子樹高度差不超過1，但是插入、刪除節(jié)點的時候，所做的平衡操作比較復(fù)雜。 而紅黑樹的特性，保證了平衡操作實現(xiàn)相對簡單，樹的高度僅比平衡二叉樹高了一倍，查找、插入、刪除的時間復(fù)雜度是 O(log n)。
圖片
使用示例
利用TreeMap可以自動對鍵進行排序的特性，比較適用一些需要排序的場景，比如排行榜、商品列表等。
Map<Integer, String> map = new TreeMap<>();
map.put(1, "One");
map.put(3, "Three");
map.put(2, "Two");
System.out.println(map); // 輸出：{1=One, 2=Two, 3=Three}實現(xiàn)一個簡單的熱詞排行榜功能：
/**
* @author 一燈架構(gòu)
* @apiNote 熱詞
**/
public class HotWord {
/**
* 熱詞內(nèi)容
*/
String word;
/**
* 熱度
*/
Integer count;
public HotWord(String word, Integer count) {
this.word = word;
this.count = count;
}
}import java.util.Comparator;
import java.util.TreeMap;
/**
* @author 一燈架構(gòu)
* @apiNote 熱詞排行榜
**/
public class Leaderboard {
/**
* 自定義排序方式，按照熱度降序排列
*/
private static final Comparator<HotWord> HOT_WORD_COMPARATOR = new Comparator<HotWord>() {
@Override
public int compare(HotWord o1, HotWord o2) {
return Integer.compare(o2.count, o1.count); // 降序排列
}
};
// 使用TreeMap存儲排行榜數(shù)據(jù)，key是熱詞對象，value是熱詞標(biāo)題
private TreeMap<HotWord, String> rankMap = new TreeMap<>(HOT_WORD_COMPARATOR);
// 添加成績
public void addHotWord(String name, int score) {
rankMap.put(new HotWord(name, score), name);
}
/**
* 打印排行榜
*/
public void printLeaderboard() {
System.out.println("熱詞排行榜:");
int rank = 1;
for (HotWord hotWord : rankMap.keySet()) {
System.out.println("#" + rank + " " + hotWord);
rank++;
}
}
public static void main(String[] args) {
Leaderboard leaderboard = new Leaderboard();
leaderboard.addHotWord("閑魚崩了", 90);
leaderboard.addHotWord("淘寶崩了", 95);
leaderboard.addHotWord("閑魚崩了", 85);
leaderboard.addHotWord("釘釘崩了", 80);
leaderboard.printLeaderboard();
}
}輸出結(jié)果：
熱詞排行榜:
#1 HotWord(word=淘寶崩了, count=95)
#2 HotWord(word=閑魚崩了, count=90)
#3 HotWord(word=閑魚崩了, count=85)
#4 HotWord(word=釘釘崩了, count=80)類屬性
看一下TreeMap的類屬性，包含哪些字段？
public class TreeMap<K, V>
extends AbstractMap<K, V>
implements NavigableMap<K, V>, Cloneable, java.io.Serializable {
/**
* 排序方式
*/
private final Comparator<? super K> comparator;
/**
* 紅黑樹根節(jié)點
*/
private transient Entry<K, V> root;
/**
* 紅黑樹節(jié)點數(shù)
*/
private transient int size = 0;
/**
* 紅黑樹的紅黑節(jié)點表示
*/
private static final boolean RED = false;
private static final boolean BLACK = true;
/**
* 紅黑樹節(jié)點對象
*/
static final class Entry<K, V> implements Map.Entry<K, V> {
K key;
V value;
Entry<K, V> left;
Entry<K, V> right;
Entry<K, V> parent;
boolean color = BLACK;
/**
* 構(gòu)造方法
*/
Entry(K key, V value, Entry<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}TreeMap類屬性比較簡單，包含排序方式comparator、紅黑樹根節(jié)點root、節(jié)點個數(shù)size等。自定義了一個紅黑樹節(jié)點類Entry，內(nèi)部屬性包括鍵值對、左右子樹、父節(jié)點、紅黑標(biāo)記值等。
初始化
TreeMap常用的初始化方式有下面三個：
- 無參初始化，使用默認(rèn)的排序方式。
- 指定排序方式的初始化
- 將普通Map轉(zhuǎn)換為TreeMap，使用默認(rèn)的排序方式。
/**
* 無參初始化
*/
Map<Integer, Integer> map1 = new TreeMap<>();
/**
* 指定排序方式初始化
*/
Map<Integer, Integer> map2 = new TreeMap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
/**
* 將普通Map轉(zhuǎn)換為TreeMap
*/
Map<Integer, Integer> map3 = new TreeMap<>(new HashMap<>());再看一下對應(yīng)的源碼實現(xiàn)：
/**
* 無參初始化
*/
public TreeMap() {
comparator = null;
}
/**
* 指定排序方式初始化
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 將普通Map轉(zhuǎn)換為TreeMap
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}方法列表
由于TreeMap存儲是按照鍵的順序排列的，所以還可以進行范圍查詢，下面舉一些示例。
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;
/**
* @author 一燈架構(gòu)
* @apiNote TreeMap方法測試
*/
public class TreeMapTest {
public static void main(String[] args) {
// 1. 創(chuàng)建一個熱詞排行榜（按熱度倒序），key是熱度，value是熱詞內(nèi)容
TreeMap<Integer, String> rankMap = new TreeMap<>(Collections.reverseOrder());
rankMap.put(80, "阿里云崩了");
rankMap.put(100, "淘寶崩了");
rankMap.put(90, "釘釘崩了");
rankMap.put(60, "閑魚崩了");
rankMap.put(70, "支付寶崩了");
System.out.println("熱詞排行榜：");
for (Map.Entry<Integer, String> entry : rankMap.entrySet()) {
System.out.println("#" + entry.getKey() + " " + entry.getValue());
}
System.out.println("-----------");
// 2. 獲取排行榜的第一個元素
Map.Entry<Integer, String> firstEntry = rankMap.firstEntry();
System.out.println("firstEntry: " + firstEntry);
// 3. 獲取排行榜的最后一個元素
Map.Entry<Integer, String> lastEntry = rankMap.lastEntry();
System.out.println("lastEntry: " + lastEntry);
// 4. 獲取排行榜的大于指定鍵的最小元素（由于是倒序排列，所以結(jié)果是反的）
Map.Entry<Integer, String> higherEntry = rankMap.higherEntry(70);
System.out.println("higherEntry: " + higherEntry);
// 5. 獲取排行榜的小于指定鍵的最大元素
Map.Entry<Integer, String> lowerEntry = rankMap.lowerEntry(70);
System.out.println("lowerEntry: " + lowerEntry);
// 6. 獲取排行榜的大于等于指定鍵的最小元素
Map.Entry<Integer, String> ceilingEntry = rankMap.ceilingEntry(70);
System.out.println("ceilingEntry: " + ceilingEntry);
// 7. 獲取排行榜的小于等于指定鍵的最大元素
Map.Entry<Integer, String> floorEntry = rankMap.floorEntry(70);
System.out.println("floorEntry: " + floorEntry);
}
}輸出結(jié)果：
熱詞排行榜：
#100 淘寶崩了
#90 釘釘崩了
#80 阿里云崩了
#70 支付寶崩了
#60 閑魚崩了
-----------
firstEntry: 100=淘寶崩了
lastEntry: 60=閑魚崩了
higherEntry: 60=閑魚崩了
lowerEntry: 80=阿里云崩了
ceilingEntry: 70=支付寶崩了
floorEntry: 70=支付寶崩了其他方法的還包括：
作用 | 方法簽名 |
獲取第一個鍵 | K firstKey() |
獲取最后一個鍵 | K lastKey() |
獲取大于指定鍵的最小鍵 | K higherKey(K key) |
獲取小于指定鍵的最大鍵 | K lowerKey(K key) |
獲取大于等于指定鍵的最小鍵 | K ceilingKey(K key) |
獲取小于等于指定鍵的最大鍵 | K floorKey(K key) |
獲取第一個鍵值對 | Map.Entry<K,V> firstEntry() |
獲取最后一個鍵值對 | Map.Entry<K,V> lastEntry() |
獲取并刪除第一個鍵值對 | Map.Entry<K,V> pollFirstEntry() |
獲取并刪除最后一個鍵值對 | Map.Entry<K,V> pollLastEntry() |
獲取大于指定鍵的最小鍵值對 | Map.Entry<K,V> higherEntry(K key) |
獲取小于指定鍵的最大鍵值對 | Map.Entry<K,V> lowerEntry(K key) |
獲取大于等于指定鍵的最小鍵值對 | Map.Entry<K,V> ceilingEntry(K key) |
獲取小于等于指定鍵的最大鍵值對 | Map.Entry<K,V> floorEntry(K key) |
獲取子map，左閉右開 | SortedMap<K,V> subMap(K fromKey, K toKey) |
獲取前幾個子map，不包含指定鍵 | SortedMap<K,V> headMap(K toKey) |
獲取前幾個子map | NavigableMap<K,V> headMap(K toKey, boolean inclusive) |
獲取后幾個子map，不包含指定鍵 | SortedMap<K,V> tailMap(K fromKey) |
獲取后幾個子map | NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) |
獲取其中一段子map | NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) |
put源碼
再看一下TreeMap的put源碼：
/**
* put源碼入口
*/
public V put(K key, V value) {
Entry<K,V> t = root;
// 1. 如果根節(jié)點為空，則創(chuàng)建根節(jié)點
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 2. 判斷是否傳入了排序方式，如果沒有則使用默認(rèn)
Comparator<? super K> cpr = comparator;
if (cpr != null) {
// 3. 如果傳入了排序方式，使用do-while循環(huán)，找到目標(biāo)值所在位置，并賦值
do {
parent = t;
cmp = cpr.compare(key, t.key);
// 4. 利用紅黑樹節(jié)點左小右大的特性，進行查找
if (cmp < 0) {
t = t.left;
} else if (cmp > 0) {
t = t.right;
} else {
return t.setValue(value);
}
} while (t != null);
} else {
// 5. TreeMap不允許key為null
if (key == null) {
throw new NullPointerException();
}
// 6. 如果沒有傳入排序方式，則使用Comparable進行比較
Comparable<? super K> k = (Comparable<? super K>) key;
// 7. 跟上面一致，使用do-while循環(huán)，利用紅黑樹節(jié)點左小右大的特性，查找目標(biāo)值所在位置，并賦值
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);
}
// 8. 如果沒有找到，則創(chuàng)建新節(jié)點
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0) {
parent.left = e;
} else {
parent.right = e;
}
// 9. 插入新節(jié)點后，需要調(diào)整紅黑樹節(jié)點位置，保持紅黑樹的特性
fixAfterInsertion(e);
size++;
modCount++;
return null;
}put源碼邏輯比較簡單：
- 判斷紅黑樹根節(jié)點是否為空，如果為空，則創(chuàng)建根節(jié)點。
- 判斷是否傳入了排序方式，如果沒有則使用默認(rèn)，否則使用自定義排序。
- 循環(huán)遍歷紅黑樹，利用紅黑樹節(jié)點左小右大的特性，進行查找。
- 如果找到，就覆蓋。如果沒找到，就插入新節(jié)點。
- 插入新節(jié)點后，調(diào)整紅黑樹節(jié)點位置，保持紅黑樹的特性。
get源碼
再看一下get源碼：
/**
* get源碼入口
*/
public V get(Object key) {
// 調(diào)用查找節(jié)點的方法
Entry<K, V> p = getEntry(key);
return (p == null ? null : p.value);
}
/**
* 查找節(jié)點方法
*/
final Entry<K, V> getEntry(Object key) {
// 1. 判斷如果傳入了排序方式，則使用排序方式查找節(jié)點
if (comparator != null) {
return getEntryUsingComparator(key);
}
if (key == null) {
throw new NullPointerException();
}
// 2. 否則使用默認(rèn)方式查找
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K, V> p = root;
// 3. 利用紅黑樹節(jié)點左小右大的特性，循環(huán)查找
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;
}
}
return null;
}
/**
* 使用傳入的排序方式，查找節(jié)點方法
*/
final Entry<K, V> getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K, V> p = root;
// 3. 跟上面類似，利用紅黑樹節(jié)點左小右大的特性，循環(huán)查找
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0) {
p = p.left;
} else if (cmp > 0) {
p = p.right;
} else {
return p;
}
}
}
return null;
}get方法源碼與put方法邏輯類似，都是利用紅黑樹的特性遍歷紅黑樹。
總結(jié)
TreeMap是一種有序Map集合，具有以下特性：
- 保證以鍵的順序進行排列
- 具有一些以鍵的順序進行范圍查詢的方法，比如firstEntry()、lastEntry()、higherEntry(K key)、 lowerEntry(K key) 等。
- 可以自定義排序方式，初始化的時候，可以指定是正序、倒序或者自定義排序。
- 不允許key為null，因為null值無法比較大小。
- 底層基于紅黑樹實現(xiàn)，查找、插入、刪除的時間復(fù)雜度是O(log n)，而HashMap的時間復(fù)雜度是O(1)。
