TreeMap或HashMap?

何时使用hashmaps或treemaps?

我知道我可以使用TreeMap遍历元素,当我需要他们进行sorting。 但是,只是呢? 当我只想查阅地图或者某些最佳的具体用途时,没有优化。

散列表(通常)执行O(n)<=T(n)<=O(1)复杂度范围内的search操作(查找O(n)<=T(n)<=O(1) ,平均复杂度为O(1 + n/k) 。 然而,二叉search树(BST)在O(n)<=T(n)<=O(log_2(n))的复杂度内执行search操作(查找O(n)<=T(n)<=O(log_2(n)) ,其平均复杂度为O(log_2(n)) 。 为了理解优点,缺点,操作的时间复杂性和代码的复杂性,每个(和每个)数据结构的实现应该被你所知道。

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

还有一些特殊情况需要考虑,例如,如果特定数据结构中的元素数量增加而没有界限或接近数据结构底层部分的限制呢? 那么执行一些重新平衡或清理操作的分期付款操作呢?

例如,在散列表中,当表中元素的数量变得足够大时,可能发生任意数量的冲突。 另一方面,树插入(或删除)后通常需要重新平衡程序。

所以,如果你有像caching这样的东西(例如有界的元素的数量,或者大小是已知的),那么哈希表可能是你最好的select。 然而,如果你有一些更像字典的东西(例如,填充一次,抬头多次),那么我会使用一棵树。

然而,这只是在一般情况下(没有提供任何信息)。 您必须了解如何在决定使用哪种数据结构时做出正确select的过程。

当我需要一个集合的多重映射(范围查找)或sorting展平时,它不能是一个哈希表。

TreeMap提供保证的O(log n)查找时间(和插入等),而HashMap提供O(1)查找时间,如果散列码恰好分散键。

除非你需要sorting的条目,我会坚持使用HashMap 。 当然还有ConcurrentHashMap 。 我不记得所有这些差异的细节,但HashMap是一个完全合理的“默认”选项:)

为了完整起见,我应该指出,大约一个月前,有关Stack Overflow的讨论关于各种地图的内部。 看到这个问题的意见,如果bestsss为我这样做,我将复制到这个答案。

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

HashMaps使用数组和散列函数来存储元素。 当您尝试插入或删除数组中的项目时,哈希函数会将该键转换为该对象应存储在其上的索引(忽略冲突)。 虽然hashmaps通常非常快,因为它们不需要迭代大量的数据,当它们被填充时,它们会减速,因为它们需要将所有的键/值复制到一个新的数组中。

TreeMaps将数据存储在sorting的树结构中。 虽然这意味着他们永远不需要分配更多的空间并拷贝到它,但是操作需要已经存储的部分数据被迭代。 有时会改变大量的结构。

当你不需要sorting的时候,两个HashMap中通常会有更好的性能。

不要忘记还有一个LinkedHashMap ,它与用于添加/包含/删除操作的HashMap几乎一样快,但是也保持了插入顺序。

在HashMap中插入新元素平均来说比将元素插入TreeMap要快得多。 除非你需要你的元素sorting,我会去与HashMap。