Java 中的樹圖

如果您正在閱讀本文，您很可能熟悉 Map 接口以及可以適當應用的地方。如果沒有，那就來這裡。今天我們將討論 Java TreeMap 實現的特點，更具體地說，它與 HashMap 有何不同以及如何正確使用它。

比較 TreeMap、HashMap 和 LinkedHashMap

Map 接口最常用的實現是 HashMap。它易於使用並保證快速訪問數據，因此它是解決大多數問題的最佳選擇。大多數，但不是全部。有時您需要以結構化方式存儲數據並能夠在其中導航。在這種情況下，Map 接口的另一個實現 (TreeMap) 可以派上用場。TreeMap 實現了NavigableMap接口，它繼承了SortedMap，而 SortedMap 又繼承了 Map 接口。 通過實現NavigableMap和SortedMap接口，TreeMap 獲得了 HashMap 所沒有的額外功能，但它在性能方面付出了代價。還有LinkedHashMapclass ，它還允許您以特定順序存儲數據（將數據添加到地圖的順序）。要了解這三個類之間的差異，請查看此表： 如您所見，這些類有很多共同點，但也有一些不同之處。雖然 TreeMap 類是最通用的，但它不能總是將null存儲為鍵。此外，訪問 TreeMap 的元素花費的時間最長。因此，如果您不需要按某種排序順序存儲數據，最好使用HashMap或LinkedHashMap。

紅黑樹

您可能注意到，在幕後，TreeMap 使用一種稱為紅黑樹的數據結構。以這種結構存儲數據正是提供數據排序的原因。那麼這是什麼樹呢？讓我們弄清楚！想像一下，您需要存儲數字-字符串對。數字 16、20、52、55、61、65、71、76、81、85、90、93 和 101 將成為密鑰。如果你將數據存儲在一個傳統的列表中，你需要找到鍵為 101 的元素，那麼你將需要遍歷所有 13 個元素才能找到它。對於 13 個元素，這沒什麼大不了的，但是當處理一百萬個元素時，我們就會遇到大問題。為了解決這些問題，程序員使用稍微複雜一點的數據結構。這就是紅黑樹出場的地方！搜索元素從樹的根開始，在我們的例子中是 61。然後我們將節點值與我們要查找的值進行比較。如果我們的價值較小，那麼我們就往左走；如果它更大，那麼我們就往右走。重複此過程，直到我們找到所需的值或遇到值為null的元素（樹的葉子）。紅色和黑色用於簡化樹的導航和平衡。構建紅黑樹時必須始終遵守以下規則：

• 根必須是黑色的。
• 樹的葉子必須是黑色的。
• 一個紅色節點必須有兩個黑色子節點。
• 黑色節點可以有任何顏色的子節點。
• 從節點到其葉子的路徑必須包含相同數量的黑色節點。
• 新節點被添加到葉子中。

如果將規則 3、4 和 5 一起考慮，您就會理解節點顏色如何讓我們更快地導航樹：通過黑色節點的路徑總是比通過紅色節點的路徑短。因此，樹的總大小由黑色節點的數量決定，稱為“黑色高度”。紅黑樹數據結構在各種編程語言中都有實現。Java的實現網上有很多，這裡就不多說了。相反，讓我們繼續了解 TreeMap 的功能。

來自 SortedMap 和 NavigableMap 接口的方法

和HashMap一樣，TreeMap實現了Map接口，也就是說TreeMap擁有HashMap存在的所有方法。但是 TreeMap 還實現了SortedMap和NavigableMap接口，因此從中獲得了額外的功能。SortedMap是一個擴展Map並添加與排序數據集相關的方法的接口：

• firstKey()：返回地圖中第一個元素的鍵
• lastKey()：返回最後一個元素的鍵
• headMap(K end) : 返回一個包含當前地圖所有元素的地圖，從開始到鍵為end的元素
• tailMap(K start)：返回一個包含當前地圖所有元素的地圖，從開始元素到結束
• subMap(K start, K end)：返回一個包含當前地圖所有元素的地圖，從開始元素到以end為鍵的元素。

NavigableMap是一個擴展 SortedMap 的接口，並添加了在地圖元素之間導航的方法：

• firstEntry()：返回第一個鍵值對
• lastEntry()：返回最後一個鍵值對
• pollFirstEntry()：返回並刪除第一對
• pollLastEntry()：返回並刪除最後一對
• ceilingKey(K obj)：返回大於或等於鍵obj的最小鍵k。如果沒有這樣的鍵，則返回 null
• floorKey(K obj)：返回小於或等於鍵obj的最大鍵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參數表示返回的map中是否包含upperBound元素
• tailMap(K lowerBound, boolean incl) : 功能類似於之前的方法，只返回從 lowerBound 到末尾的對
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl)：與前面的方法一樣，返回從 lowerBound 到 upperBound 的對；參數 lowIncl 和 highIncl 指示是否在新地圖中包含邊界元素。

除了通常的構造函數之外，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;
   }
}

我們在主類 中實現邏輯：

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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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是這個月的廣告展示次數。我們向構造函數傳遞一個按年齡對人進行排序的比較器。我們用任意值填充地圖。現在我們想在我們的小數據存儲庫中獲取對第一個成年人的引用。我們使用 Stream API 來做到這一點。然後我們得到兩個單獨的地圖，我們將其傳遞給顯示廣告的方法。我們可以通過多種方式完成這項任務。TreeMap 類的方法庫使我們能夠為各種需要創建自定義解決方案。您不需要全部記住它們，因為您始終可以使用 IDE 中的文檔或提示。 為了鞏固您所學的知識，我們建議您觀看我們的 Java 課程中的視頻課程 目前為止就這樣了！我希望您現在已經清楚 TreeMap 類，並希望您在解決實際編碼任務時正確應用它。