Java TreeMap指南

1.概述

在本文中,我們將從Java Collections Framework(JCF)探索Map接口的TreeMap實現。

TreeMap是一種地圖實現,可以根據其鍵的自然順序對條目進行排序,或者如果用戶在構建時提供了比較器,則最好使用比較器。

以前,我們已經介紹了HashMapLinkedHashMap的實現,並且我們將意識到,關於這些類如何工作的信息很多。

強烈建議您在閱讀本文章之前閱讀其中的文章。

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

在查看了HashMapLinkedHashMap的實現(以及現在的TreeMap)之後對這三個實現進行簡短的比較,以指導我們選者哪個很重要。

hash map是一種通用的map實現,可以提供快速的存儲和檢索操作。但是,它缺點是元素的混亂和無序排列。

這導致它在存在大量迭代的情況下表現不佳,因為基礎數組的整個容量會影響遍歷,而不僅僅是條目數。

linked hash map具有hash maps的良好屬性,並為條目添加了順序。在存在大量迭代的情況下,它的性能更好,因為無論容量如何,都僅考慮條目數。

通過完全控制鍵的排序方式,tree map將順序提高到一個新的層次。另一方面,與其他兩種選擇相比,它提供的綜合性能更差。

我們可以說一個linked hash map減少了哈希圖順序的混亂,而不會產生tree map的性能損失

7.結論

在本文中,我們探討了Java TreeMap類及其內部實現。由於它是一系列常見Map接口實現中的最後一個,因此我們也繼續簡要地討論了與其他兩個最適合的地方。

本文中使用的所有示例的完整源代碼都可以在GitHub項目中找到。