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

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

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

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

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

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

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

二叉查找樹又是什么呢？

image

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

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

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

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

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

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

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

1)每個節點都只能是紅色或者黑色

2)根節點是黑色

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

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

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

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

01、自然順序

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

TreeMap mapInt = new TreeMap<>();mapInt.put(3, "11");mapInt.put(2, "12");mapInt.put(1, "13");mapInt.put(5, "14");mapInt.put(4, "15");System.out.println(mapInt);

輸出結果如下所示：

{1=11, 2=12, 3=13, 4=14, 5=15}

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

public V put(K key, V value) { TreeMap.Entry t = root; int cmp; TreeMap.Entry 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);}

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

TreeMap 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 對象的時候指定排序規則。

TreeMap 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 提供了可以指定排序規則的構造方法：

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

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

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

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

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

03、排序的好處

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

Integer highestKey = mapInt.lastKey();Integer lowestKey = mapInt.firstKey();Set keysLessThan3 = mapInt.headMap(3).keySet();Set 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)。

來看一下輸出結果：

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

04、如何選擇 Map

在學習 TreeMap 之前，我們已經學習了 [HashMap] 和 [LinkedHashMap]，那如何從它們三個中間選擇呢？

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

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

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

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

來個表格吧，一目了然。

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

注：如果文章有任何問題，歡迎毫不留情地指正。
轉自：沉默王二原文 http://www.itwanger.com/java/2020/08/24/java-treemap.html

總結

以上是生活随笔為你收集整理的java表格树_Java程序员值得拥有的TreeMap指南的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。