如果您正在閱讀本文,您很可能熟悉 Map 接口以及可以適當應用的地方。如果沒有,那就來這裡。今天我們將討論 Java TreeMap 實現的特點,更具體地說,它與 HashMap 有何不同以及如何正確使用它。
通過實現NavigableMap和SortedMap接口,TreeMap 獲得了 HashMap 所沒有的額外功能,但它在性能方面付出了代價。還有LinkedHashMapclass ,它還允許您以特定順序存儲數據(將數據添加到地圖的順序)。要了解這三個類之間的差異,請查看此表:
如您所見,這些類有很多共同點,但也有一些不同之處。雖然 TreeMap 類是最通用的,但它不能總是將null存儲為鍵。此外,訪問 TreeMap 的元素花費的時間最長。因此,如果您不需要按某種排序順序存儲數據,最好使用HashMap或LinkedHashMap。
搜索元素從樹的根開始,在我們的例子中是 61。然後我們將節點值與我們要查找的值進行比較。如果我們的價值較小,那麼我們就往左走;如果它更大,那麼我們就往右走。重複此過程,直到我們找到所需的值或遇到值為null的元素(樹的葉子)。紅色和黑色用於簡化樹的導航和平衡。構建紅黑樹時必須始終遵守以下規則:
目前為止就這樣了!我希望您現在已經清楚 TreeMap 類,並希望您在解決實際編碼任務時正確應用它。
比較 TreeMap、HashMap 和 LinkedHashMap
Map 接口最常用的實現是 HashMap。它易於使用並保證快速訪問數據,因此它是解決大多數問題的最佳選擇。大多數,但不是全部。有時您需要以結構化方式存儲數據並能夠在其中導航。在這種情況下,Map 接口的另一個實現 (TreeMap) 可以派上用場。TreeMap 實現了NavigableMap接口,它繼承了SortedMap,而 SortedMap 又繼承了 Map 接口。
哈希表 | 鍊錶 | 樹圖 | |
---|---|---|---|
數據排序 | 隨機的。不能保證訂單會隨著時間的推移而維持。 | 按照添加數據的順序 | 按升序或基於指定的比較器 |
時間複雜度 | O(1) | O(1) | O(日誌(n)) |
實現接口 | 地圖 | 地圖 | NavigableMap SortedMap 地圖 |
數據結構 | 水桶 | 水桶 | 紅黑樹 |
支持空鍵嗎? | 是的 | 是的 | 是的,如果您使用比較器,則允許 null |
線程安全? | 不 | 不 | 不 |
紅黑樹
您可能注意到,在幕後,TreeMap 使用一種稱為紅黑樹的數據結構。以這種結構存儲數據正是提供數據排序的原因。那麼這是什麼樹呢?讓我們弄清楚!想像一下,您需要存儲數字-字符串對。數字 16、20、52、55、61、65、71、76、81、85、90、93 和 101 將成為密鑰。如果你將數據存儲在一個傳統的列表中,你需要找到鍵為 101 的元素,那麼你將需要遍歷所有 13 個元素才能找到它。對於 13 個元素,這沒什麼大不了的,但是當處理一百萬個元素時,我們就會遇到大問題。為了解決這些問題,程序員使用稍微複雜一點的數據結構。這就是紅黑樹出場的地方!
- 根必須是黑色的。
- 樹的葉子必須是黑色的。
- 一個紅色節點必須有兩個黑色子節點。
- 黑色節點可以有任何顏色的子節點。
- 從節點到其葉子的路徑必須包含相同數量的黑色節點。
- 新節點被添加到葉子中。
來自 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為鍵的元素。
- 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 指示是否在新地圖中包含邊界元素。
樹圖的例子
大量的額外方法似乎是不必要的,但事實證明它們比您乍看之下要有用得多。讓我們一起探討以下示例。想像一下,我們在一家大公司的營銷部門工作,我們有一個數據庫,其中包含我們要向其展示廣告的人員。有兩個細節需要記住:- 我們需要跟踪每個人的印像數
- 向未成年人展示廣告的算法不同。
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 課程中的視頻課程
GO TO FULL VERSION