Java中TreeMap的特點

如果您正在閱讀本文，您很可能熟悉地圖介面及其用途。如果沒有，那就到這裡。今天我們來談談TreeMap的實現特點，更具體地說，它與HashMap有何不同以及如何正確使用它。

TreeMap、HashMap 與 LinkedHashMap 的比較

Map介面最常用的實作是HashMap。它易於使用並保證快速存取數據，使其成為大多數任務的最佳選擇。大多數，但不是全部。有時需要以結構化形式儲存資料並能夠瀏覽資料。在這種情況下，Map介面的另一個實作可以解決這個問題- TreeMap。 TreeMap實作NavigableMap接口，該介面繼承自SortedMap，而 SortedMap 又繼承自Map介面。 透過實作NavigableMap和SortedMap接口，TreeMap獲得了HashMap沒有的附加功能，但這是以效能為代價的。還有一個LinkedHashMap類，它還允許您按特定順序儲存資料 - 按照它們添加的順序。為了幫助您了解這三個類別之間的差異，請查看此表： 正如您所看到的，這些類別有很多共同點，但也有一些差異。儘管類別的TreeMap功能最多，但它不能總是null作為鍵存儲。另外，對TreeMap元素的存取時間將是最長的。因此，如果不需要以排序形式儲存數據，最好使用HashMapor LinkedHashMap。

紅檀樹

您可能已經注意到，它在底層TreeMap使用了一種稱為紅黑樹的資料結構。正是這種結構中資料的儲存保證了資料儲存的順序。這棵樹是什麼？讓我們來弄清楚吧！想像一下您需要儲存數字-字串對。數字 16、20、52、55、61、65、71、76、81、85、90、93、101 將是按鍵。如果您將資料儲存在傳統清單中並且需要尋找鍵為 101 的元素，則需要迭代所有 13 個元素才能找到它。對於 13 個元素來說，這並不重要；當處理 100 萬個元素時，我們就會遇到大麻煩。為了解決此類問題，程式設計師使用稍微複雜的資料結構。因此，來認識紅黑樹吧！

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

所需元素的搜尋從樹的根開始，在我們的範例中為 61。接下來，與所需值進行比較。如果我們的值較小，我們就向左走，如果數值較大，我們就往右走。這種情況會發生，直到我們找到所需的值或命中具有值的元素null（樹的葉子）。紅色和黑色用於使樹木更容易導航和平衡。建造紅黑樹時必須始終遵循以下規則：

• 根部應該是黑色的。
• 樹的葉子應該是黑色的。
• 紅色節點必須有兩個黑色子節點。
• 黑色節點可以有任何子節點。
• 從節點到其葉子的路徑必須包含相同數量的黑色節點。
• 新增節點來代替葉子。

如果您一起查看規則 3、4 和 5，您可以理解著色節點如何加速樹中的導航：通過黑色節點的路徑總是比通過紅色節點的路徑短。因此，樹的總大小由黑色節點的數量決定，這個大小稱為「黑色高度」。紅黑樹是用不同的程式語言實現的。網路上有很多 Java 的實現，因此我們不會詳細討論它，但會繼續熟悉其功能TreeMap。

從 SortedMap 和 NavigableMap 介面衍生出來的方法

就像HashMap，TreeMap它實作了接口Map，這意味著它TreeMap具有該接口的所有方法HashMap。但除此之外，TreeMap它還實作了介面SortedMap和NavigableMap，並從中獲取了附加功能。 — 擴展並新增與排序資料集相關的方法的 SortedMap介面：Map

• firstKey()：傳回map第一個元素的key；
• lastKey()：返回最後一個元素的鍵；
• headMap(K end)：傳回一個包含目前元素的所有元素的映射，從開頭到帶有鍵 的元素end；
• tailMap(K start)：傳回一個map，包含目前的所有元素，從該元素開始start，到end結束；
• subMap(K start, K end)：傳回一個包含目前元素的所有元素的映射，從該元素開始start並以帶有鍵 的元素結束end。

NavigableMapSortedMap— 擴展並新增在地圖元素之間導航的方法的 介面：

• firstEntry()：傳回第一個鍵值對；
• lastEntry()：傳回最後一個鍵值對；
• pollFirstEntry()：返回並刪除第一對；
• pollLastEntry()：返回並刪除最後一對；
• ceilingKey(K obj)：傳回大於或等於key obj的最小key k。如果不存在該鍵，則傳回null；
• floorKey(K obj)：傳回小於或等於key obj的最大key k。如果不存在該鍵，則傳回null；
• lowerKey(K obj)：傳回小於鍵 obj 的最大鍵 k。如果不存在該鍵，則傳回null；
• higherKey(K obj)：傳回大於鍵 obj 的最小鍵 k。如果不存在該鍵，則傳回null；
• ceilingEntry(K obj)：與ceilingKey(K obj)方法類似，但傳回一個鍵值對（或null）；
• floorEntry(K obj)：與floorKey(K obj)方法類似，但傳回一個鍵值對（或null）；
• lowerEntry(K obj)：與lowerKey(K obj)方法類似，但傳回鍵值對（或null）；
• higherEntry(K obj)：與higherKey(K obj)方法類似，但傳回一個鍵值對（或null）；
• descendingKeySet()：傳回一個 NavigableSet，其中包含所有以相反順序排序的鍵；
• descendingMap()：傳回一個 NavigableMap，其中包含所有依相反順序排序的對；
• navigableKeySet()：傳回一個 NavigableSet 對象，其中包含依儲存順序排列的所有鍵；
• headMap(K upperBound, boolean incl)：傳回一個包含從開頭到 upperBound 元素的對的映射。incl 參數指定 upperBound 元素是否應包含在傳回的對應中；
• tailMap(K lowerBound, boolean incl)：功能與上一個方法類似，僅傳回從 lowerBound 到末尾的對；
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl)：與前面的方法一樣，傳回從 lowerBound 到 upperBound 的對，參數 lowIncl 和 highIncl 指定是否在新映射中包含邊界元素。

在實作本身中TreeMap，除了我們熟悉的建構函式之外，還增加了一個，它接受比較器的實例。此比較器將負責元素的儲存順序。

使用 TreeMap 的範例

如此豐富的附加方法似乎沒有必要，但事實證明它們往往比最初看起來更有用。讓我們和你一起看一下這個例子。想像一下，我們在一家大公司的行銷部門工作，我們有一個我們想要向其展示廣告的人員的資料庫。這有兩個細微差別：

• 我們需要追蹤每個人的印象數；
• 向未成年人展示廣告的演算法是不同的。

讓我們創建一個類別Person來儲存我們可以獲得的有關一個人的所有資訊：

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

我們在類別中實作邏輯Main：

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

Main在我們創建的 類別中TreeMap，其中key是特定人員，value是本月的廣告展示次數。在建構函數中，我們傳遞一個比較器，它將按年齡對人們進行排序。map用隨機值填充。現在我們需要在我們的迷你資料儲存中獲取第一個成人的引用。我們使用 Stream API 來完成此操作。之後，我們得到兩個獨立的地圖，我們將其傳遞給顯示廣告的方法。有很多很多方法可以解決這個問題。課程的方法庫TreeMap可讓您發明適合各種口味的解決方案。沒有必要全部記住它們，因為您始終可以使用開發環境中的文件或提示。就這樣！我希望你現在已經清楚了這門課TreeMap，並能在解決實際問題中找到準確的應用。