Java TreeMap指南
1.概述
在本文中，我們將從Java Collections Framework（JCF）探索Map接口的TreeMap實現。
TreeMap是一種地圖實現，可以根據其鍵的自然順序對條目進行排序，或者如果用戶在構建時提供了比較器，則最好使用比較器。
以前，我們已經介紹了HashMap和LinkedHashMap的實現，並且我們將意識到，關於這些類如何工作的信息很多。
強烈建議您在閱讀本文章之前閱讀其中的文章。
2. TreeMap中的默認排序
默認情況下， TreeMap根據其所有條目的自然順序對其進行排序。對於整數，這意味著升序，對於字符串，則意味著字母序。
讓我們看看測試中的自然順序：
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString());
}注意，我們以非有序的方式放置整數鍵，但是在檢索鍵集時，我們確認它們確實以升序維護。這是整數的自然排序。
同樣，當我們使用字符串時，它們將按照其自然順序（即按字母順序）排序：
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
TreeMap<String, String> map = new TreeMap<>();
map.put("c", "val");
map.put("b", "val");
map.put("a", "val");
map.put("e", "val");
map.put("d", "val");
assertEquals("[a, b, c, d, e]", map.keySet().toString());
}TreeMap與哈希map和linked hash map不同，它不使用哈希原理，因為它不使用數組來存儲其條目。
3. TreeMap中的自定義排序
如果我們對TreeMap的自然排序不滿意，則還可以在構建樹圖時通過比較器定義自己的排序規則。
在下面的示例中，我們希望整數鍵以降序排列：
@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
TreeMap<Integer, String> map =
new TreeMap<>(Comparator.reverseOrder());
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString());
}hash map不能保證鍵的存儲順序，特別是不能保證該鍵隨時間的推移保持不變，但是tree map保證鍵將始終根據指定的順序進行排序。
4. TreeMap排序的重要性
現在我們知道TreeMap將所有條目存儲在已排序的順序中。由於TreeMaps的這一屬性，我們可以執行類似的查詢；找到“最大”，找到“最小”，找到所有小於或大於某個值的鍵，等等。
下面的代碼僅涵蓋了這些情況的一小部分：
@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
Integer highestKey = map.lastKey();
Integer lowestKey = map.firstKey();
Set<Integer> keysLessThan3 = map.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = map.tailMap(3).keySet();
assertEquals(new Integer(5), highestKey);
assertEquals(new Integer(1), lowestKey);
assertEquals("[1, 2]", keysLessThan3.toString());
assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString());
}5. TreeMap的內部實現
TreeMap實現NavigableMap接口，並將其內部工作基於紅黑樹的原理：
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable紅黑樹的原理超出了本文的範圍，但是，要理解它們如何適合TreeMap，需要記住一些關鍵的事情。
首先，紅黑樹是由節點組成的數據結構。想像一棵倒立的芒果樹，其根在天空中，樹枝向下生長。根目錄將包含添加到樹中的第一個元素。
規則是，從根開始，任何節點左分支中的任何元素總是小於節點本身中的元素。右邊的那些總是更大。大於或小於的定義由元素的自然順序或在構建時定義的比較器確定，如我們先前所見。
此規則確保樹形圖的條目將始終按可預測的順序排序。
其次，紅黑樹是一種自平衡二叉搜索樹。此屬性及以上內容保證搜索，獲取，放置和刪除之類的基本操作花費對數時間O（log n） 。
保持自我平衡是這裡的關鍵。當我們不斷插入和刪除條目時，可以想像樹在一側長得更長，而在另一側更短。
這意味著操作將在較短的分支上花費更短的時間，而在距離根最遠的分支上花費更長的時間，這是我們不希望發生的事情。
因此，在設計紅黑樹時要注意這一點。對於每次插入和刪除，樹在任何邊緣上的最大高度都保持為O（log n），即樹不斷地自我平衡。
就像hash map和linked hash map一樣，tree map也不是線程同步，因此在多線程環境中使用tree map的規則與其他兩個Map實現中的規則相似。
6.選擇正確的Map
在查看了HashMap和LinkedHashMap的實現（以及現在的TreeMap）之後，對這三個實現進行簡短的比較，以指導我們選者哪個很重要。
hash map是一種通用的map實現，可以提供快速的存儲和檢索操作。但是，它缺點是元素的混亂和無序排列。
這導致它在存在大量迭代的情況下表現不佳，因為基礎數組的整個容量會影響遍歷，而不僅僅是條目數。
linked hash map具有hash maps的良好屬性，並為條目添加了順序。在存在大量迭代的情況下，它的性能更好，因為無論容量如何，都僅考慮條目數。
通過完全控制鍵的排序方式，tree map將順序提高到一個新的層次。另一方面，與其他兩種選擇相比，它提供的綜合性能更差。
我們可以說一個linked hash map減少了哈希圖順序的混亂，而不會產生tree map的性能損失。
7.結論
在本文中，我們探討了Java TreeMap類及其內部實現。由於它是一系列常見Map接口實現中的最後一個，因此我們也繼續簡要地討論了與其他兩個最適合的地方。
本文中使用的所有示例的完整源代碼都可以在GitHub項目中找到。