Java TreeMap与HashMap的比较

1.绪论

在这篇文章中，我们将比较两种Map的实现。TreeMap和HashMap。

这两种实现都构成了Java Collections框架的一个组成部分，并以键-值对的形式存储数据。

2.差异

2.1.实现

我们将首先讨论 HashMap ，它是一个基于哈希表的实现。它扩展了 AbstractMap 类并实现了 Map 接口。 HashMap 的工作原理是散列。

此 Map 实现通常用作分桶的 hash 表，但当分桶变得太大时，它们会转换为 TreeNodes 的节点，每个结构都与 java.util.TreeMap 中的结构类似。

你可以在专注于它的文章中找到更多关于HashMap的内部的信息。

另一方面，TreeMap扩展了AbstractMap类并实现了NavigableMap接口。TreeMap将地图元素存储在一个Red-Black中，它是一个自平衡二进制搜索树。

而且，你还可以在这里重点介绍的文章中找到更多关于TreeMap的内部结构的信息。

2.2.排序

HashMap对元素在Map中的排列方式不提供任何保证。

这意味着，我们在迭代HashMap的keys和values时，不能假设任何顺序：。

@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));
}

23. 空值

HashMap允许最多存储一个null key和许多null值。

让我们来看看一个例子。

@Test
public void whenInsertNullInHashMap_thenInsertsNull() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(null, null);
    
    assertNull(hashmap.get(null));
}

然而，TreeMap不允许有null key，但可能包含许多null值。

一个空的键是不允许的，因为compareTo()或compare()方法会抛出一个NullPointerException:。

@Test(expected = NullPointerException.class)
public void whenInsertNullInTreeMap_thenException() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(null, "NullPointerException");
}

如果我们使用一个带有用户定义的Comparator的TreeMap，那么如何处理null值就取决于compare()方法的实现了。

3.性能分析

性能是最关键的指标，可以帮助我们了解一个数据结构在使用情况下的适用性。

在这一节中，我们将对HashMap 和TreeMap.的性能进行全面分析。

3.1. HashMap

HashMap，是一个基于哈希的实现，在内部使用一个基于数组的数据结构，根据哈希函数来组织其元素。

HashMap 为大多数操作（如 add()、remove() 和 contains()）提供预期的恒定时间性能 O(1)。因此，它比 TreeMap 快得多。

在合理的假设下，在哈希表中搜索一个元素的平均时间是O(1)。但是，对哈希函数的不当实现可能会导致值在桶中的分布不佳，从而导致：

内存开销 – 许多桶仍然未被使用
性能下降 – 碰撞次数越多，性能就越低。

在Java 8之前，分离链式是处理碰撞的唯一首选方式。它通常使用链表来实现，即，如果有任何碰撞或两个不同的元素具有相同的哈希值，那么将这两个项目存储在同一个链表中。

因此，在HashMap中搜索一个元素，在最坏的情况下，可能需要和在链接列表中搜索一个元素一样长的时间，即O(n)时间。

然而，随着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 为大多数操作提供了O(log(n))的性能，如add()、remove()和contains()等。
Treemap可以节省内存（与HashMap相比），因为它只使用保存项目所需的内存量，而不像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.Fail-Fast的迭代器

如果Map在迭代器创建后的任何时候以任何方式被修改，Iterator会抛出ConcurrentModificationException 。

此外，我们可以使用迭代器的移除方法来改变迭代过程中的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具有更显著的位置性，如果我们想要访问那些根据自然排序相对接近的对象，我们可以考虑使用它。
HashMap 可以使用initialCapacity和loadFactor进行调整，这对TreeMap来说是不可能的。
如果我们想保留插入顺序，同时从恒定时间访问中受益，我们可以使用LinkedHashMap。

6.结语

在这篇文章中，我们展示了TreeMap和HashMap之间的差异和相似之处。

像往常一样，本文的代码实例可在GitHub上找到。