Java TreeMap與HashMap

1.簡介

在本文中,我們將比較兩個Map實現: TreeMapHashMap

這兩種實現都是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對象進行排序,則可以使用ComparatorComparable來定義元素在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.性能分析

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

在本節中,我們將對HashMapTreeMap的性能進行全面的分析

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。獨特元素

TreeMapHashMap都不支持重複鍵。如果添加,它將覆蓋前一個元素(無錯誤或異常):

@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具有更大的局部性,如果我們要根據對象的自然順序訪問彼此相對較近的對象,則可以考慮使用它
  • 可以使用initialCapacityloadFactor調整HashMap ,這對於TreeMap是不可能的
  • 如果我們想保留插入順序,同時受益於恆定的訪問時間,則可以使用LinkedHashMap

六,結論

在本文中,我們展示了TreeMapHashMap之間的異同。

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