java - TreeSet 的优缺点是什么

Question

只是想知道 TreeSet 的优缺点是什么，如果有人可以告诉我吗？谢谢！

Answer 1

集合类之一。它使您可以按键或按顺序访问集合中的元素。它的开销比 ArrayList 或 HashMap 多得多。不需要顺序访问的时候使用HashSet，只需要按键查找即可。使用 ArrayList 并使用数组。如果您只想按顺序排列元素，请排序。TreeSet 始终保持元素有序。使用 ArrayList，您只需在需要时进行排序。使用 TreeSet，键必须嵌入到您存储在集合中的对象中。通常你可能有 TreeSet of Strings。你所能做的就是判断给定的字符串是否在集合中。它不会像 Treemap 那样为您找到关联的对象。使用 TreeMap，键和它们关联的对象是分开的。

TreeSet 和它的兄弟 TreeMap 奇怪地与表示树无关。在内部，他们使用树组织为您提供按字母顺序排序的集合/地图，但您无法控制父母和孩子之间的链接。

TreeSet 内部使用红黑树。无需对数据进行预排序即可获得平衡良好的树。另一方面，如果数据是排序的（升序或降序），它不会像其他类型的树那样受到伤害。

如果您不提供 Comparator 来定义所需的顺序，TreeSet 需要在项目类上实现 Comparable 来定义自然顺序。

Answer 2

缺点：TreeSet 的一个缺陷是它以一种意想不到的方式实现了 Set 接口。如果 TreeSet 包含对象 a，则如果 a.compareTo(b) 返回 0，则将对象 b 视为集合的一部分，即使 a.equals(b) 为假，因此如果 compareTo 和 equals 没有以一致的方式实现，你的旅程很糟糕。

当一个方法返回一个 Set 并且您不知道实现是 TreeSet 还是例如 HashSet 时，这尤其是一个问题。

这里要吸取的教训是，始终避免不一致地实现 compareTo 和 equals。如果您需要以与 equals 不一致的方式对对象进行排序，请使用 Comparator。

Answer 3

TreeSet：
优点：排序，基于红/黑树算法，为操作提供 O(log(N)) 复杂度。
缺点：值必须是Comparable或者您需要在构造函数中提供Comparator。此外，HashSet 实现提供了更好的性能，因为它提供了~O(1) 的复杂性。

Answer 4

TreeSet 对内存进行分段并具有额外的内存开销。您可以查看来源并计算额外内存的数量和它创建的额外对象的数量。当然，这取决于存储对象的性质，你也可以怀疑我对内存有偏执狂:) 但最好不要到处乱花钱——你有 GC，你有缓存未命中，所有这些事情都很慢。

通常您可以使用 PriorityQueue 代替 TreeSet。在您的典型用例中，最好对字符串数组进行排序。

Answer 5

我猜这个数据结构将使用二叉树来维护数据，以便可以进行升序检索。在这种情况下，如果它试图保持树的平衡，那么删除操作会有点昂贵。