TreeMap 还是 HashMap? [英] TreeMap or HashMap?

问题描述

何时使用哈希图或树图?

When to use hashmaps or treemaps?

我知道当我需要对元素进行排序时，我可以使用 TreeMap 对它们进行迭代.但仅此而已吗?只是想参考地图的时候没有优化，或者一些优化的具体用途?

I know that I can use TreeMap to iterate over the elements when I need them to be sorted. But is just that? There is no optimization when I just want to consult the maps, or some optimal specific uses?

推荐答案

Hashtables(通常)在O(n)<=T(n)<=的复杂度范围内执行搜索操作(查找)O(1)，平均情况复杂度O(1 + n/k)；然而，二叉搜索树(BST)执行的搜索操作(查找)在O(n)<=T(n)<=O(log_2(n))的复杂度范围内，平均情况复杂度为O(log_2(n)).每个(和每个)数据结构的实现都应该(由你)知道，以了解优点、缺点、操作的时间复杂度和代码复杂度.

Hashtables (usually) perform search operations (look up) bounded within the complexity of O(n)<=T(n)<=O(1), with an average case complexity of O(1 + n/k); however, binary search trees, (BST's), perform search operations (lookup) bounded within the complexity of O(n)<=T(n)<=O(log_2(n)), with an average case complexity of O(log_2(n)). The implementation for each (and every) data structure should be known (by you), to understand the advantages, drawbacks, time complexity of operations, and code complexity.

例如，哈希表中的条目数通常有一些固定数量的条目(其中某些部分可能根本没有填充)与冲突列表.另一方面，树通常每个节点有两个指针(引用)，但是如果实现允许每个节点有两个以上的子节点，这可能会更多，这允许树随着节点的添加而增长，但可能不允许重复.(Java TreeMap 的默认实现不允许重复)

For example, the number of entries in a hashtable often have some fixed number of entries (some part of which may not be filled at all) with lists of collisions. Trees, on the other hand, usually have two pointers (references) per node, but this can be more if the implementation allows more than two child nodes per node, and this allows the tree to grow as nodes are added, but may not allow duplicates. (The default implementation of a Java TreeMap does not allow for duplicates)

还有一些特殊情况需要考虑，例如，如果特定数据结构中的元素数量无限制地增加或接近数据结构底层部分的限制怎么办?执行一些重新平衡或清理操作的摊销操作怎么样?

There are special cases to consider as well, for example, what if the number of elements in a particular data structure increases without bound or approaches the limit of an underlying part of the data structure? What about amortized operations that perform some rebalancing or cleanup operation?

例如，在哈希表中，当表中的元素数量变得足够大时，可能会发生任意数量的冲突.另一方面，树通常需要在插入(或删除)后进行重新平衡过程.

For example, in a hashtable, when the number of elements in the table become sufficiently large, and arbitrary number of collisions can occur. On the other hand, trees usually require come re-balancing procedure after an insertion (or deletion).

因此，如果您有诸如缓存之类的东西(例如，有界元素的数量或大小是已知的)，那么哈希表可能是您最好的选择；但是，如果您有更像字典的东西(例如填充一次并查找多次)，那么我会使用一棵树.

So, if you have something like a cache (Ex. the number of elements in bounded, or size is known) then a hashtable is probably your best bet; however, if you have something more like a dictionary (Ex. populated once and looked up many times) then I'd use a tree.

然而，这只是在一般情况下(未提供任何信息).您必须了解发生的过程，以便在决定使用哪种数据结构时做出正确的选择.

This is only in the general case, however, (no information was given). You have to understand process that happen how they happen to make the right choice in deciding which data structure to use.

当我需要一个多映射(范围查找)或一个集合的排序扁平化时，它就不能是一个哈希表.

When I need a multi-map (ranged lookup) or sorted flattening of a collection, then it can't be a hashtable.

这篇关于TreeMap 还是 HashMap?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！