TreeMap或HashMap？
这个问题在这里已经有了答案：
散列表（通常）执行O(n)<=T(n)<=O(1)复杂度范围内的搜索操作（查找O(n)<=T(n)<=O(1) ，平均复杂度为O(1 + n/k) 。 然而，二叉搜索树（BST）在O(n)<=T(n)<=O(log_2(n))的复杂度范围内执行搜索操作（查找O(n)<=T(n)<=O(log_2(n)) ，平均复杂度为O(log_2(n)) 。 为了理解优点，缺点，操作的时间复杂性和代码复杂性，应该知道每个（和每个）数据结构的实现。
例如，哈希表中的条目数量通常有一些固定数量的条目（其中一部分可能根本没有被填充）和冲突列表。 另一方面，树通常每个节点有两个指针（引用），但是如果实现允许每个节点有两个以上的子节点，则这可以更多，并且这允许树随着节点的添加而增长，但可能不允许重复。 （Java TreeMap的默认实现不允许重复）
还有一些特殊情况需要考虑，例如，如果特定数据结构中的元素数量没有限制地增加或接近数据结构的底层部分的限制会怎样？ 执行一些重新平衡或清理操作的分期付款操作如何？
例如，在散列表中，当表中元素的数量变得足够大时，可能发生任意数量的冲突。 另一方面，树插入（或删除）后通常需要重新平衡程序。
所以，如果你有像缓存这样的东西（例如有界的元素数量，或者大小已知），那么哈希表可能是你最好的选择; 然而，如果你有更像字典的东西（例如，填充一次并抬头多次），那么我会使用一棵树。
然而，这只是在一般情况下（没有提供任何信息）。 您必须了解如何在决定使用哪种数据结构时做出正确选择的过程。
当我需要一个多重映射（范围查找）或排序集合的扁平化时，它不能成为一个哈希表。
TreeMap提供有保证的O（log n）查找时间（和插入等），而如果散列码恰好分散键，则HashMap提供O（1）查找时间。
除非你需要对条目进行排序，否则我会坚持使用HashMap 。 当然还有ConcurrentHashMap 。 我不记得所有这些差异的细节，但HashMap是一个完全合理的“默认”选项:)
为了完整起见，我应该指出，大约一个月前关于堆栈溢出的讨论关于各种地图的内部。 查看这个问题中的评论，如果bestsss对我这么做感到高兴，我会将其复制到这个答案中。
两者之间最大的区别在于实现中使用的基础结构。
HashMaps使用数组和散列函数来存储元素。 当您尝试插入或删除数组中的项目时，哈希函数会将该键转换为该对象应存储在其上的索引（忽略冲突）。 虽然hashmaps通常非常快，因为它们不需要迭代大量数据，但当它们被填充时，它们会减慢速度，因为它们需要将所有键/值复制到新数组中。
TreeMaps将数据存储在排序的树结构中。 虽然这意味着他们永远不必分配更多空间并复制到它，但操作需要已经存储的部分数据进行迭代。 有时会改变大量的结构。
在不需要排序的情况下，两个哈希表中的哈希表通常会有更好的性能。
链接地址: http://www.djcxy.com/p/92169.html上一篇: TreeMap or HashMap?
下一篇: What is the difference between a HashMap and a TreeMap?