先看再點贊，給自己一點思考的時間，微信搜索【沉默王二】關注這個有顏值卻假裝靠才華茍且的程序員。
本文 GitHub github.com/itwanger 已收錄，里面還有我精心為你準備的一線大廠面試題。

吃飯間隙，迷上了《吐槽大會》，一集一集地刷啊，覺得這些嘉賓真的挺有勇氣的，敢于直面自己的慘淡槽點。于是，同學們看到了，我作為一個技術博主，也受到了“傳染”，不，受到了“熏陶”，本來這篇文章標題就想叫《TreeMap 指南》，是不是有點平淡無奇，沒有槽點？于是我就想，不妨蹭點吐槽大會的熱度吧，雖然吐槽大會現(xiàn)在也沒什么熱度了哈。

TreeMap，雖然也是個 Map，但存在感太低了。我做程序員這十多年里，HashMap 用了超過十年，TreeMap 只用了多字里那么一小會兒一小會兒，真的是，太慘了。

雖然 TreeMap 用得少，但還是有用處的。

之前 LinkedHashMap 那篇文章里提到過了，HashMap 是無序的，所有有了 LinkedHashMap，加上了雙向鏈表后，就可以保持元素的插入順序和訪問順序，那 TreeMap 呢？

TreeMap 由紅黑樹實現(xiàn)，可以保持元素的自然順序，或者實現(xiàn)了 Comparator 接口的自定義順序。

可能有些同學不知道紅黑樹，理解起來 TreeMap 就有點難度，那我先來普及一下：

紅黑樹（英語：Red–black tree）是一種自平衡的二叉查找樹（Binary Search Tree），結構復雜，但卻有著良好的性能，完成查找、插入和刪除的時間復雜度均為 log(n)。

二叉查找樹又是什么呢？

圖片來源于網(wǎng)絡，侵刪

上圖中這棵樹，就是一顆典型的二叉查找樹：

1）左子樹上所有節(jié)點的值均小于或等于它的根結點的值。

2）右子樹上所有節(jié)點的值均大于或等于它的根結點的值。

3）左、右子樹也分別為二叉排序樹。

理解二叉查找樹了吧？不過，二叉查找樹有一個不足，就是容易變成瘸子，就是一側多，一側少，就像下圖這樣：

圖片來源于網(wǎng)絡，侵刪

查找的效率就要從 log(n) 變成 o(n) 了，對吧？必須要平衡一下，對吧？于是就有了平衡二叉樹，左右兩個子樹的高度差的絕對值不超過 1，就像下圖這樣：

圖片來源于網(wǎng)絡，侵刪

紅黑樹，顧名思義，就是節(jié)點是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡：

1）每個節(jié)點都只能是紅色或者黑色

2）根節(jié)點是黑色

3）每個葉節(jié)點（NIL 節(jié)點，空節(jié)點）是黑色的。

4）如果一個節(jié)點是紅色的，則它兩個子節(jié)點都是黑色的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色節(jié)點。

5）從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

圖片來源于網(wǎng)絡，侵刪

那，關于紅黑樹，同學們就先了解到這，腦子里有個大概的印象，知道 TreeMap 是個什么玩意。

01、自然順序

默認情況下，TreeMap 是根據(jù) key 的自然順序排列的。比如說整數(shù)，就是升序，1、2、3、4、5。

TreeMap<Integer,String> mapInt = new TreeMap<>();
mapInt.put(3, "沉默王二");
mapInt.put(2, "沉默王二");
mapInt.put(1, "沉默王二");
mapInt.put(5, "沉默王二");
mapInt.put(4, "沉默王二");

System.out.println(mapInt);

輸出結果如下所示：

{1=沉默王二, 2=沉默王二, 3=沉默王二, 4=沉默王二, 5=沉默王二}

TreeMap 是怎么做到的呢？想一探究竟，就得上源碼了，來看 TreeMap 的 put() 方法（省去了一部分，版本為 JDK 14）：

public V put(K key, V value) {
    TreeMap.Entry<K,V> t = root;
    int cmp;
    TreeMap.Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
    }
    else {
        @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);
    }
    return null;
}

注意 cmp = k.compareTo(t.key) 這行代碼，就是用來進行 key 的比較的，由于此時 key 是 int，所以就會調用 Integer 類的 compareTo() 方法進行比較。

public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}

public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

那相應的，如果 key 是字符串的話，也就會調用 String 類的 compareTo() 方法進行比較。

public int compareTo(String anotherString) {
    byte v1[] = value;
    byte v2[] = anotherString.value;
    byte coder = coder();
    if (coder == anotherString.coder()) {
        return coder == LATIN1 ? StringLatin1.compareTo(v1, v2)
                : StringUTF16.compareTo(v1, v2);
    }
    return coder == LATIN1 ? StringLatin1.compareToUTF16(v1, v2)
            : StringUTF16.compareToLatin1(v1, v2);
}

由于內(nèi)部是由字符串的字節(jié)數(shù)組的字符進行比較的，是不是聽起來很繞？對，就是很繞，所以使用中文字符串作為 key 的話，看不出來效果。

TreeMap<String,String> mapString = new TreeMap<>();
mapString.put("c", "沉默王二");
mapString.put("b", "沉默王二");
mapString.put("a", "沉默王二");
mapString.put("e", "沉默王二");
mapString.put("d", "沉默王二");

System.out.println(mapString);

輸出結果如下所示：

{a=沉默王二, b=沉默王二, c=沉默王二, d=沉默王二, e=沉默王二}

字母的升序，對吧？

02、自定義排序

如果自然順序不滿足，那就可以在聲明 TreeMap 對象的時候指定排序規(guī)則。

TreeMap<Integer,String> mapIntReverse = new TreeMap<>(Comparator.reverseOrder());
mapIntReverse.put(3, "沉默王二");
mapIntReverse.put(2, "沉默王二");
mapIntReverse.put(1, "沉默王二");
mapIntReverse.put(5, "沉默王二");
mapIntReverse.put(4, "沉默王二");

System.out.println(mapIntReverse);

TreeMap 提供了可以指定排序規(guī)則的構造方法：

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

Comparator.reverseOrder() 返回的是 ReverseComparator 對象，就是用來反轉順序的，非常方便。

所以，輸出結果如下所示：

{5=沉默王二, 4=沉默王二, 3=沉默王二, 2=沉默王二, 1=沉默王二}

HashMap 是無序的，插入的順序隨著元素的增加會不停地變動。但 TreeMap 能夠至始至終按照指定的順序排列，這對于需要自定義排序的場景，實在是太有用了！

03、排序的好處

既然 TreeMap 的元素是經(jīng)過排序的，那找出最大的那個，最小的那個，或者找出所有大于或者小于某個值的鍵來說，就方便多了。

Integer highestKey = mapInt.lastKey();
Integer lowestKey = mapInt.firstKey();
Set<Integer> keysLessThan3 = mapInt.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = mapInt.tailMap(3).keySet();

System.out.println(highestKey);
System.out.println(lowestKey);

System.out.println(keysLessThan3);
System.out.println(keysGreaterThanEqTo3);

TreeMap 考慮得很周全，恰好就提供了 lastKey()、firstKey() 這樣獲取最后一個 key 和第一個 key 的方法。

headMap() 獲取的是到指定 key 之前的 key；tailMap() 獲取的是指定 key 之后的 key（包括指定 key）。

來看一下輸出結果：

5
1
[1, 2]
[3, 4, 5]

04、如何選擇 Map

在學習 TreeMap 之前，我們已經(jīng)學習了 HashMap 和 LinkedHashMap ，那如何從它們?nèi)齻€中間選擇呢？

HashMap、LinkedHashMap、TreeMap 都實現(xiàn)了 Map 接口，并提供了幾乎相同的功能（增刪改查）。它們之間最大的區(qū)別就在于元素的順序：

HashMap 完全不保證元素的順序，添加了新的元素，之前的順序可能完全逆轉。

LinkedHashMap 默認會保持元素的插入順序。

TreeMap 默認會保持 key 的自然順序（根據(jù) compareTo() 方法）。

來個表格吧，一目了然。

謝謝大家，下期見，同學們。

我是沉默王二，一枚有顏值卻假裝靠才華茍且的程序員。關注即可提升學習效率，別忘了三連啊，點贊、收藏、留言，我不挑，奧利給??。

注：如果文章有任何問題，歡迎毫不留情地指正。

如果你覺得文章對你有些幫助，歡迎微信搜索「沉默王二」第一時間閱讀，回復關鍵字「小白」可以免費獲取我肝了 4 萬+字的 《Java 小白從入門到放肆》2.0 版；本文 GitHub github.com/itwanger 已收錄，歡迎 star。