阿里這段時間忙著制定下半年的OKR，其實在制定OKR的時候就能看出團隊里誰是領導的嫡系，誰是團隊的邊角料。嫡系的OKR都是從領導的核心項目分出來的，而其他人的OKR不會體現在領導的OKR里面，只配給嫡系做打下手的工作。pMo28資訊網——每日最新資訊28at.com

“員工的績效，在制定OKR的時候，已經確定了”。pMo28資訊網——每日最新資訊28at.com

職場失意，摸魚得意。我還是安心的更新《解讀Java源碼專欄》，在這個系列中，我將手把手帶著大家剖析Java核心組件的源碼，內容包含集合、線程、線程池、并發、隊列等，深入了解其背后的設計思想和實現細節，輕松應對工作面試。 這是解讀Java源碼系列的第六篇，將跟大家一起學習Java中比較特殊的數據結構 - TreeMap。pMo28資訊網——每日最新資訊28at.com

引言

上篇文章講到LinkedHashMap可以保證元素的插入順序或者訪問順序，而TreeMap也能保證元素順序，不過按照鍵的順序進行排序。插入到TreeMap中的鍵值對，會自動按照鍵的順序進行排序。pMo28資訊網——每日最新資訊28at.com

簡介

HashMap底層結構是基于數組實現的，而TreeMap底層結構是基于紅黑樹實現的。TreeMap利用紅黑樹的特性實現對鍵的排序。 額外介紹一下紅黑樹的特性：pMo28資訊網——每日最新資訊28at.com

1. 節點是紅色或者黑色
2. 根節點是黑色
3. 所有葉子節點是黑色
4. 每個紅色結點的兩個子結點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點）
5. 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。

紅黑樹是基于平衡二叉樹的改進，而平衡二叉樹是為了解決二叉搜索樹在特殊情況下，退化成鏈表，查找、插入效率退化成 O(n)，規定左右子樹高度差不超過1，但是插入、刪除節點的時候，所做的平衡操作比較復雜。 而紅黑樹的特性，保證了平衡操作實現相對簡單，樹的高度僅比平衡二叉樹高了一倍，查找、插入、刪除的時間復雜度是 O(log n)。pMo28資訊網——每日最新資訊28at.com

圖片pMo28資訊網——每日最新資訊28at.com

使用示例

利用TreeMap可以自動對鍵進行排序的特性，比較適用一些需要排序的場景，比如排行榜、商品列表等。pMo28資訊網——每日最新資訊28at.com

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}

實現一個簡單的熱詞排行榜功能：pMo28資訊網——每日最新資訊28at.com

/** * @author 一燈架構 * @apiNote 熱詞 **/public class HotWord {    /**     * 熱詞內容     */    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 一燈架構 * @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存儲排行榜數據，key是熱詞對象，value是熱詞標題    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();    }}

輸出結果：pMo28資訊網——每日最新資訊28at.com

熱詞排行榜:#1 HotWord(word=淘寶崩了, count=95)#2 HotWord(word=閑魚崩了, count=90)#3 HotWord(word=閑魚崩了, count=85)#4 HotWord(word=釘釘崩了, count=80)

類屬性

看一下TreeMap的類屬性，包含哪些字段？pMo28資訊網——每日最新資訊28at.com

public class TreeMap<K, V>        extends AbstractMap<K, V>        implements NavigableMap<K, V>, Cloneable, java.io.Serializable {    /**     * 排序方式     */    private final Comparator<? super K> comparator;    /**     * 紅黑樹根節點     */    private transient Entry<K, V> root;    /**     * 紅黑樹節點數     */    private transient int size = 0;    /**     * 紅黑樹的紅黑節點表示     */    private static final boolean RED = false;    private static final boolean BLACK = true;    /**     * 紅黑樹節點對象     */    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;        /**         * 構造方法         */        Entry(K key, V value, Entry<K, V> parent) {            this.key = key;            this.value = value;            this.parent = parent;        }    }}

TreeMap類屬性比較簡單，包含排序方式comparator、紅黑樹根節點root、節點個數size等。自定義了一個紅黑樹節點類Entry，內部屬性包括鍵值對、左右子樹、父節點、紅黑標記值等。pMo28資訊網——每日最新資訊28at.com

初始化

TreeMap常用的初始化方式有下面三個：pMo28資訊網——每日最新資訊28at.com

1. 無參初始化，使用默認的排序方式。
2. 指定排序方式的初始化
3. 將普通Map轉換為TreeMap，使用默認的排序方式。

/** * 無參初始化 */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轉換為TreeMap */Map<Integer, Integer> map3 = new TreeMap<>(new HashMap<>());

再看一下對應的源碼實現：pMo28資訊網——每日最新資訊28at.com

/** * 無參初始化 */public TreeMap() {    comparator = null;}/** * 指定排序方式初始化 */public TreeMap(Comparator<? super K> comparator) {    this.comparator = comparator;}/** * 將普通Map轉換為TreeMap */public TreeMap(Map<? extends K, ? extends V> m) {    comparator = null;    putAll(m);}

方法列表

由于TreeMap存儲是按照鍵的順序排列的，所以還可以進行范圍查詢，下面舉一些示例。pMo28資訊網——每日最新資訊28at.com

import java.util.Collections;import java.util.Map;import java.util.TreeMap;/** * @author 一燈架構 * @apiNote TreeMap方法測試 */public class TreeMapTest {    public static void main(String[] args) {        // 1. 創建一個熱詞排行榜（按熱度倒序），key是熱度，value是熱詞內容        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. 獲取排行榜的大于指定鍵的最小元素（由于是倒序排列，所以結果是反的）        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);    }}

輸出結果：pMo28資訊網——每日最新資訊28at.com

熱詞排行榜：#100 淘寶崩了#90 釘釘崩了#80 阿里云崩了#70 支付寶崩了#60 閑魚崩了-----------firstEntry: 100=淘寶崩了lastEntry: 60=閑魚崩了higherEntry: 60=閑魚崩了lowerEntry: 80=阿里云崩了ceilingEntry: 70=支付寶崩了floorEntry: 70=支付寶崩了

其他方法的還包括：pMo28資訊網——每日最新資訊28at.com

put源碼

再看一下TreeMap的put源碼：pMo28資訊網——每日最新資訊28at.com

/** * put源碼入口 */public V put(K key, V value) {    Entry<K,V> t = root;    // 1. 如果根節點為空，則創建根節點    if (t == null) {        compare(key, key);        root = new Entry<>(key, value, null);        size = 1;        modCount++;        return null;    }    int cmp;    Entry<K,V> parent;    // 2. 判斷是否傳入了排序方式，如果沒有則使用默認    Comparator<? super K> cpr = comparator;    if (cpr != null) {        // 3. 如果傳入了排序方式，使用do-while循環，找到目標值所在位置，并賦值        do {            parent = t;            cmp = cpr.compare(key, t.key);            // 4. 利用紅黑樹節點左小右大的特性，進行查找            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循環，利用紅黑樹節點左小右大的特性，查找目標值所在位置，并賦值        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. 如果沒有找到，則創建新節點    Entry<K,V> e = new Entry<>(key, value, parent);    if (cmp < 0) {        parent.left = e;    } else {        parent.right = e;    }    // 9. 插入新節點后，需要調整紅黑樹節點位置，保持紅黑樹的特性    fixAfterInsertion(e);    size++;    modCount++;    return null;}

put源碼邏輯比較簡單：pMo28資訊網——每日最新資訊28at.com

1. 判斷紅黑樹根節點是否為空，如果為空，則創建根節點。
2. 判斷是否傳入了排序方式，如果沒有則使用默認，否則使用自定義排序。
3. 循環遍歷紅黑樹，利用紅黑樹節點左小右大的特性，進行查找。
4. 如果找到，就覆蓋。如果沒找到，就插入新節點。
5. 插入新節點后，調整紅黑樹節點位置，保持紅黑樹的特性。

get源碼

再看一下get源碼：pMo28資訊網——每日最新資訊28at.com

/** * get源碼入口 */public V get(Object key) {    // 調用查找節點的方法    Entry<K, V> p = getEntry(key);    return (p == null ? null : p.value);}/** * 查找節點方法 */final Entry<K, V> getEntry(Object key) {    // 1. 判斷如果傳入了排序方式，則使用排序方式查找節點    if (comparator != null) {        return getEntryUsingComparator(key);    }    if (key == null) {        throw new NullPointerException();    }    // 2. 否則使用默認方式查找    Comparable<? super K> k = (Comparable<? super K>) key;    Entry<K, V> p = root;    // 3. 利用紅黑樹節點左小右大的特性，循環查找    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;}/** * 使用傳入的排序方式，查找節點方法 */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. 跟上面類似，利用紅黑樹節點左小右大的特性，循環查找        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方法邏輯類似，都是利用紅黑樹的特性遍歷紅黑樹。pMo28資訊網——每日最新資訊28at.com

總結

TreeMap是一種有序Map集合，具有以下特性：pMo28資訊網——每日最新資訊28at.com

1. 保證以鍵的順序進行排列
2. 具有一些以鍵的順序進行范圍查詢的方法，比如firstEntry()、lastEntry()、higherEntry(K key)、 lowerEntry(K key) 等。
3. 可以自定義排序方式，初始化的時候，可以指定是正序、倒序或者自定義排序。
4. 不允許key為null，因為null值無法比較大小。
5. 底層基于紅黑樹實現，查找、插入、刪除的時間復雜度是O(log n)，而HashMap的時間復雜度是O(1)。

pMo28資訊網——每日最新資訊28at.com

本文鏈接：http://www.tebozhan.com/showinfo-26-35325-0.html阿里面試官：你說一下Java的TreeMap底層實現原理？

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 你不知道的Websocket協議，這次給你講明白！

下一篇： 嵌入式軟件設計原則隨想