TreeMap或HashMap？ [英] TreeMap or HashMap?

问题描述

何时使用hashmaps或treemaps？

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's）执行在 O（n）<= T（n）<= O（log_2（n））的复杂度内界限的搜索操作（查找） code>，平均病例复杂度为 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屋！