Java TreeMap與HashMap

1.簡介

在本文中，我們將比較兩個Map實現： TreeMap和HashMap 。

這兩種實現都是Java Collections Framework的組成部分，並將數據存儲為鍵值對。

2.差異

2.1. 實現

我們將首先討論HashMap ，它是基於哈希表的實現。它擴展了AbstractMap類並實現了Map接口。 HashMap遵循哈希原理。

這個Map實現通常用作存儲桶的**哈希表，但是當存儲桶太大時，它們會轉換為TreeNodes的節點，每個節點的*結構與java.util.TreeMap中的結構類似。*

您可以在重點文章中找到有關HashMap內部的更多信息。

另一方面， TreeMap擴展了AbstractMap類並實現了NavigableMap接口。 TreeMap將地圖元素存儲在Red-Black樹中，該樹是Self-Balancing Binary Search Tree 。

而且，您還可以在此處重點關注的文章中找到有關TreeMap內部的更多信息。

2.2. 排序

HashMap不對Map中元素的排列方式提供任何保證。

這意味著，在遍歷HashMap的**鍵和值時，我們不能假設任何順序：

@Test

 public void whenInsertObjectsHashMap_thenRandomOrder() {

 Map<Integer, String> hashmap = new HashMap<>();

 hashmap.put(3, "TreeMap");

 hashmap.put(2, "vs");

 hashmap.put(1, "HashMap");



 assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3));

 }

但是， TreeMap中的項目是根據其自然順序排序的。

如果無法根據自然順序對TreeMap對象進行排序，則可以使用Comparator或Comparable來定義元素在Map中的排列順序：

@Test

 public void whenInsertObjectsTreeMap_thenNaturalOrder() {

 Map<Integer, String> treemap = new TreeMap<>();

 treemap.put(3, "TreeMap");

 treemap.put(2, "vs");

 treemap.put(1, "HashMap");



 assertThat(treemap.keySet(), contains(1, 2, 3));

 }

2.3。空值

HashMap允許最多存儲一個空鍵和許多空值。

讓我們來看一個例子：

@Test

 public void whenInsertNullInHashMap_thenInsertsNull() {

 Map<Integer, String> hashmap = new HashMap<>();

 hashmap.put(null, null);



 assertNull(hashmap.get(null));

 }

但是， TreeMap不允許使用null**鍵，但可能包含許多null值。

不允許使用null鍵，因為compareTo（）或compare（）方法會引發NullPointerException：

@Test(expected = NullPointerException.class)

 public void whenInsertNullInTreeMap_thenException() {

 Map<Integer, String> treemap = new TreeMap<>();

 treemap.put(null, "NullPointerException");

 }

如果我們將TreeMap與用戶定義的Comparator一起使用，則它取決於compare （）方法的實現，如何處理空值。

3.性能分析

性能是最關鍵的指標，可以幫助我們了解給定用例的數據結構的適用性。

在本節中，我們將對HashMap和TreeMap的性能進行全面的分析。

3.1。HashMap

HashMap是基於哈希表的實現，在內部使用基於數組的數據結構根據哈希函數組織其元素。

HashMap為大多數操作（如add（） ， remove（）和contains（））提供預期的恆定時間性能O（1 ）。因此，它比TreeMap快得多。

在合理的假設下，在哈希表中搜索元素的平均時間為O（1）。但是，哈希函數的不正確實現可能會導致值在存儲桶中分佈不均，從而導致：

• 內存開銷–許多存儲桶未使用
• 性能下降–碰撞次數越多，性能越低

在Java 8之前，單獨鏈接是處理衝突的唯一首選方法。通常使用鏈接列表來實現，即，如果發生任何衝突或兩個不同的元素具有相同的哈希值，則將兩個項目都存儲在同一鏈接列表中。

因此，在最壞的情況下，只要在鏈接列表中搜索元素（即O（n）時間），就可以在HashMap中搜索元素。

但是，隨著JEP 180的出現， HashMap中**元素的排列方式的實現有了細微的變化**。

根據規範，當存儲桶過大並包含足夠的節點時，它們會轉換為TreeNodes模式，每種模式的結構都與TreeMap中的模式類似。

因此，在高哈希衝突的情況下，最壞情況下的性能將從O（n）提高到O（log n）。

下面說明了執行此轉換的代碼：

if(binCount >= TREEIFY_THRESHOLD - 1) {

 treeifyBin(tab, hash);

 }

TREEIFY_THRESHOLD的值為8，這實際上表示使用樹而不是存儲區的鍊錶的閾值計數。

顯而易見的是：

• HashMap需要的方式比保存其數據所需的方式更多
• HashMap的完整空間不應超過70％-75％。如果靠近，它將調整大小並重新整理條目
• 重新哈希處理需要n次操作，這很昂貴，其中我們的恆定時間插入變為O（n）階
• 這是哈希算法，可確定在HashMap中插入對象的順序

在創建HashMap對象時，可以通過設置自定義初始容量和負載因子來調整HashMap的性能。

但是，如果出現以下情況，我們應該選擇一個HashMap ：

• 我們知道我們的收藏中要維護多少件物品
• 我們不想以自然順序提取項目

在上述情況下， HashMap是我們的最佳選擇，因為它提供了恆定的時間插入，搜索和刪除。

3.2。TreeMap

TreeMap將其數據存儲在分層樹中，並能夠借助自定義Comparator對元素進行排序。

其性能摘要：

• TreeMap為大多數操作（如add（） ， remove（）和contains（））提供O（log（n））性能。
• Treemap可以節省內存（與HashMap相比），因為Treemap僅使用保存其項目所需的內存量，這與使用連續內存區域的HashMap不同
• 為了保持預期的性能，一棵樹應該保持其平衡，這需要大量的工作，因此使實現複雜化

每當以下情況，我們都應該使用TreeMap ：

• 內存限制必須考慮
• 我們不知道必須在內存中存儲多少個項目
• 我們想以自然順序提取對象
• 如果項目將被一致地添加和刪除
• 我們願意接受O（log n）搜索時間

4.相似之處

4.1。獨特元素

TreeMap和HashMap都不支持重複鍵。如果添加，它將覆蓋前一個元素（無錯誤或異常）：

@Test

 public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() {

 Map<Integer, String> treeMap = new HashMap<>();

 treeMap.put(1, "Baeldung");

 treeMap.put(1, "Baeldung");



 assertTrue(treeMap.size() == 1);



 Map<Integer, String> treeMap2 = new TreeMap<>();

 treeMap2.put(1, "Baeldung");

 treeMap2.put(1, "Baeldung");



 assertTrue(treeMap2.size() == 1);

 }

4.2。並發訪問

兩種Map實施都不同步，我們需要自己管理並發訪問。

每當多個線程同時訪問它們並且至少一個線程對其進行修改時，都必須在外部同步這兩個線程。

我們必須顯式使用Collections.synchronizedMap（mapName）來獲取所提供地圖的同步視圖。

4.3。失敗快速迭代器

如果在創建迭代器後以任何方式以及在任何時間修改了Map，則迭代器將引發ConcurrentModificationException 。

另外，我們可以使用迭代器的remove方法在迭代過程中更改Map 。

讓我們來看一個例子：

@Test

 public void whenModifyMapDuringIteration_thenThrowExecption() {

 Map<Integer, String> hashmap = new HashMap<>();

 hashmap.put(1, "One");

 hashmap.put(2, "Two");



 Executable executable = () -> hashmap

 .forEach((key,value) -> hashmap.remove(1));



 assertThrows(ConcurrentModificationException.class, executable);

 }

5.使用哪種實現？

總的來說，這兩種實現都有各自的優缺點，但是，這是關於了解潛在的期望和要求，這些期望和要求必須支配我們對此的選擇。

總結：

• 如果要保持條目排序，則應使用TreeMap
• 如果我們將性能優先於內存消耗，則應使用HashMap
• 由於TreeMap具有更大的局部性，如果我們要根據對象的自然順序訪問彼此相對較近的對象，則可以考慮使用它
• 可以使用initialCapacity和loadFactor調整HashMap ，這對於TreeMap是不可能的
• 如果我們想保留插入順序，同時受益於恆定的訪問時間，則可以使用LinkedHashMap

六，結論

在本文中，我們展示了TreeMap和HashMap之間的異同。

與往常一樣，可以在GitHub上獲得本文的代碼示例。