TreeMap 还是 HashMap？

小开

平均而言，在 HashMap 中插入新元素要比在 TreeMap 中插入元素快得多。除非您需要对元素进行排序，否则我会使用 HashMap。

小开

TreeMap提供了保证的 O (log n)查找时间(和插入等) ，而 HashMap提供了 O (1)查找时间，如果散列代码适当分散键。

除非您需要对条目进行排序，否则我将坚持使用 HashMap。当然还有 ConcurrentHashMap。我不记得它们之间差异的细节，但 HashMap是一个完全合理的“默认”选项:)

为了完整起见，我应该指出，大约一个月前有一个关于 Stack Overflow 的讨论，是关于各种映射的内部结构的。请参阅对这个问题的评论，如果最好的，我将复制到这个答案，我很高兴这样做。

小开

不要忘记还有 LinkedHashMap，它在添加/包含/删除操作方面几乎和 HashMap一样快，但是也维护插入顺序。

小开

最佳答案

Hashtables (通常)执行在 O(n)<=T(n)<=O(1)复杂度范围内的搜索操作(查找) ，平均大小写复杂度为 O(1 + n/k); 然而，二进制搜索树(BST)执行在 O(n)<=T(n)<=O(log_2(n))复杂度范围内的搜索操作(查找) ，平均大小写复杂度为 O(log_2(n))。为了理解操作的优点、缺点、时间复杂性和代码复杂性，您应该知道每个(和每个)数据结构的实现。

例如，散列表中的条目数通常有固定数量的条目(其中一部分可能根本不会被填充)和冲突列表。另一方面，树通常每个节点有两个指针(引用) ，但是如果实现允许每个节点有两个以上的子节点，那么这个数字可能会更多，并且这允许树随着节点的添加而增长，但是可能不允许重复。(JavaTreeMap 的默认实现不允许重复)

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

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

所以，如果你有一个类似于缓存的东西(Ex。那么散列表可能是你最好的选择; 然而，如果你有一个更像字典的东西(例如。然后我会用一棵树。

然而，这只是在一般情况下(没有给出任何信息)。您必须理解在决定使用哪种数据结构时，这些过程是如何做出正确选择的。

当我需要一个集合的多映射(远程查找)或排序扁平化时，它就不能是一个散列表。

小开

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

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

TreeMaps 以排序的树结构存储数据。虽然这意味着他们永远不必分配更多的空间并复制到它，但是操作需要迭代已经存储的部分数据。有时改变大量的结构。

当您不需要排序时，这两个 Hashmap 通常会有更好的性能。