TreeMap或HashMap？
TreeMap或HashMap？
这个问题已经有了答案:
何时使用哈希映射或树映射？
我知道我可以使用TreeMap在需要排序时迭代元素。但是仅仅是这样吗？在我只想咨询地图或某些最佳特定用途时，没有优化吗？
哈希表（通常）在时间复杂度的范围内进行搜索操作（查找）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的默认实现不允许重复）
还有要考虑的特殊情况，例如，如果特定数据结构中的元素数量无限增加或趋近于数据结构的下层，该怎么办？什么情况下需要进行摊销操作来执行一些重新平衡或清理操作？
例如，在哈希表中，当表中元素的数量变得足够多时，可能会发生任意数量的冲突。另一方面，树通常需要在插入（或删除）后进行某些重新平衡程序。
因此，如果您有像缓存这样的东西（例如元素数量有限或大小已知），那么哈希表可能是您的最佳选择；然而，如果您有像词典这样的东西（例如一次填充并多次查找），那么我会使用树。
然而这只是在一般情况下（没有给出任何信息）。了解发生的过程如何发生，以便在决定使用哪种数据结构时做出正确的选择。
当我需要一个多映射（范围查找）或集合的排序化展开时，它就不能是哈希表。
TreeMap提供了保证O(log n)的查找时间（以及插入等），而HashMap如果哈希码适当地分散键，则提供O(1)的查找时间。
除非您需要对条目进行排序，否则我会坚持使用HashMap。或者当然还有ConcurrentHashMap。我记不清它们之间的差异细节，但HashMap是一个完全合理的“默认”选项 🙂
为了完整起见，我应该指出，大约一个月前在Stack Overflow上有一次关于各种映射内部的讨论。请参见此问题的评论，如果bestsss允许我这样做，我将把它们复制到这个答案中。