logo标签列表

TreeMap还是HashMap？

javadata-structures
76

何时使用哈希映射或树映射？

我知道当我需要对元素进行排序时，可以使用TreeMap进行迭代。但是只有这些吗？在我只想查询映射或者一些特定的最优用途时，是否存在优化？

3
TreeMap 是一种可导航的排序映射表，与其他地图有很大的区别。它有一些有趣的特性，例如基于当前键查找下一个/上一个值/键，但需要键的 [自然] 顺序，而 HashMap 则基于哈希，所以直接比较并不合适。如果没有定义自然排序（类似于 java.util.URL），则无法实际使用 TreeMap。此外，对象比较通常比 hashcode/equals 更慢。 - bestsss
非常感谢，这些互补的好答案。现在我更清楚何时使用它们了。也感谢提供链接。 - JeanK
你可以查看以下链接：enter link description here - fxl545826
5个回答
53

TreeMap 提供了保证 O(log n) 的查找时间（以及插入等操作），而 HashMap 则在哈希码适当地分散键的情况下提供 O(1) 的查找时间。

除非您需要对条目进行排序，否则我建议使用 HashMap。当然也可以使用 ConcurrentHashMap。我记不清它们之间的差异细节，但 HashMap 是一个完全合理的“默认”选项 :)

为了完整起见，我应该指出 Stack Overflow 上有一个关于各种映射内部的讨论。请参见此问题的评论，如果 bestsss 愿意，我将把它们复制到此答案中。

2
我想这更适用于“TreeSet vs HashSet”，但假设我经常进行集合交集操作。在这种情况下，即使您不明确使用它们的排序方式，拥有元素排序通常也是一种净胜利。 - phooji
那很有道理，是的，假设交叉代码被适当地优化。就像你所说的那样，这对于地图来说不太可能相关。 - Jon Skeet
@Jon，我想我就是那个人（指出Java中HashMap的弱点）。 - bestsss
@bestsss：可能是这样。你还记得讨论在哪里吗？如果我们能找到它，你介意我直接将其发布到此回答中吗？ - Jon Skeet
@bestsss：找到了：https://dev59.com/F2445IYBdhLWcg3wg6xn - 相同的问题仍然适用 :) - Jon Skeet
@Jon，我会把LinkedHashMap作为默认的Map。它拥有更好和可预测的迭代（就像LinkedList），不会随着Java版本或HashMap实现而改变。 - bestsss
49
哈希表（通常）执行搜索操作（查找），其复杂度在 O(n)<=T(n)<=O(1) 范围内，平均情况下的复杂度为 O(1 + n/k)；然而，二叉搜索树（BST）执行搜索操作（查找），其复杂度在 O(n)<=T(n)<=O(log_2(n)) 范围内，平均情况下的复杂度为 O(log_2(n))。了解每种（和每一个）数据结构的实现对于理解操作的优点、缺点、时间复杂度和代码复杂度非常重要。
例如，哈希表中的条目数量通常有一些固定的条目数（其中的某些部分可能根本没有填充），并带有冲突列表。另一方面，树通常每个节点有两个指针（引用），但如果实现允许每个节点有多于两个子节点，则可以更多，这使得树随着添加节点而增长，但可能不允许重复。（Java TreeMap 的默认实现不允许重复）
还需要考虑特殊情况，例如，如果特定数据结构中的元素数量无限增加或接近数据结构的底层部分的限制怎么办？什么是执行某些重新平衡或清理操作的摊销操作？
例如，在哈希表中，当表中的元素数量变得足够大时，任意数量的冲突可能会发生。另一方面，在插入（或删除）后，树通常需要进行一些重新平衡过程。
因此，如果您有类似缓存的东西（例如，元素数量有界限或大小已知），那么哈希表可能是最好的选择；然而，如果您有类似字典的东西（例如，填充一次并多次查找），那么我会使用树。
然而，这只是一般情况下（没有给出信息）。您必须了解发生的过程以及如何进行正确的选择，以决定使用哪种数据结构。
当我需要多重映射（范围查找）或集合的排序展开时，它不能是哈希表。
15
我不同意你用树来表示一个只需要一次填充但需要多次引用的结构的例子。在这种情况下，你可以创建一个合适大小的哈希表，它具有O(1)的查找性能，而基于树的结构则是O(log n)。此外，你永远不会使用哈希表的线性操作。 - Chris Kerekes
@ChrisKerekes，你可以创建一个完美适合的哈希表，不会发生冲突，这样就可以达到O(m)并且得到承诺的O(1)。但是你需要为你的数据生成好的哈希函数（并不总是可以花费一些额外的空条目来更改哈希函数的行为）。否则，通用哈希表更适合快速缓存，我认为。 - ony
2
这个 O(n)<=T(n)<=O(1) 是正确的吗？ - f.ardelian
2
@f.ardelian，我也不理解。@alvonellos承诺这些都是技术细节。对于哈希表，可能应该是O(1) ≤ T(n) ≤ O(n)，对于平衡树，应该是T(n) = O(log n)（据我所记，常数可以从O符号中剥离）。 - ony
这是一个基于集合大小的性能测试，其中包含一些数字：http://www.artima.com/weblogs/viewpost.jsp?thread=122295 - Simone Avogadro
11

这两者之间最大的区别在于实现时使用的底层结构。

HashMap使用数组和哈希函数存储元素。当您尝试在数组中插入或删除项目时，哈希函数将键转换为数组上的索引位置，对象被存储/应该存储在那里（忽略冲突）。虽然HashMap通常非常快，因为它们不需要迭代大量数据，但在填充时会变慢，因为它们需要将所有键/值复制到一个新数组中。

TreeMap使用排序树结构存储数据。虽然这意味着它们永远不需要分配更多空间并将数据复制到其中，但操作需要对已存储的部分数据进行迭代。有时要改变大量的结构。

在这两个中，如果您不需要排序，则HashMap通常具有更好的性能。

4

将新元素插入HashMap通常比将元素插入TreeMap要快得多。除非您需要对元素进行排序，否则建议使用HashMap。

4

不要忘记还有LinkedHashMap，它几乎和HashMap一样快，可以进行添加/包含/删除操作，但还保持插入顺序。

2
“contains” 的速度非常快，但是迭代 LinkedHashMap 的速度更快（相当多）。 - bestsss
嗯，也许我应该更经常地使用它！ - z7sg Ѫ
get（） 函数的速度非常快，除非使用 accessOrder=true 来创建它，这时只需进行几个（6个）赋值和一个间接操作（接近于零）。LinkedHashMap 是我在 java.util 中最喜欢的结构。 - bestsss
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接