Java：Hashset Vs TreeSet - 何时应该使用其中之一？

Question

我已经阅读了许多关于这个问题的博客，但仍然不能清楚地理解何时使用HashSet或TreeSet。

拿一个例子来说：

1. 我有可比较的对象。我把它们放在HashSet中。现在当我想要根据compareTo逻辑对集合进行排序时，我可以调用Collections.sort(object)。

2. 然而，TreeSet默认始终使用compareTo或compare(obj1, obj2)。因此，TreeSet的性能会受到影响，但输出与第一种情况（Collections.sort）相同。

我的理解正确吗？

- sabtharishi

---

这有帮助吗？（链接指向一个关于HashSet和TreeSet区别的问题讨论） - Maroun

Answer 1

HashSet 采用哈希表实现，元素不排序。add、remove和contains方法的时间复杂度为常数 O(1)。

TreeSet 采用树结构（红黑树），集合中的元素有序排列，但是add、remove和contains方法的时间复杂度为 O(log (n))。它提供了许多处理有序集合的方法，如first()、last()、headSet()、tailSet()等。

1) HashSet 和 TreeSet 的第一大区别在于性能。如果元素不需要排序，则HashSet比TreeSet更快，应该选择HashSet。

2) HashSet 和 TreeSet 的第二个区别是HashSet允许空对象，但TreeSet不允许空对象并且抛出NullPointerException。为什么？因为TreeSet使用compareTo()方法来比较键，而compareTo()会抛出java.lang.NullPointerException。

3) HashSet 和 TreeSet 的另一个重要区别是，HashSet的底层实现是HashMap，而TreeSet的底层实现是Java中的NavigableMap。

4) HashSet 和 TreeSet 的另一个值得记住的区别是，HashSet使用equals()方法来比较集合中的两个对象并检测重复项，而TreeSet使用compareTo()方法来实现相同的功能。如果equals()和compareTo()不一致，即对于两个相等的对象equals应该返回true，而compareTo()应该返回零，则它将破坏Set接口的契约，并允许Set实现（如TreeSet）中出现重复项。

5) HashSet和TreeSet最重要的区别在于排序。Java中，HashSet不保证任何顺序，而TreeSet根据Comparable或Comparator方法定义的顺序维护对象的排序顺序。

6) TreeSet不允许插入异构对象。如果尝试添加异构对象，它将在Runtime时抛出classCastException异常，而HashSet允许异构对象。

- Ankur Singhal

---

Treeset是同质的，这意味着只允许相同类型的数据，而Hashset是异质的。 - Parmar Kamlesh

"如果不需要对元素进行排序，HashSet比TreeSet更快，应该是首选。这是部分正确的说法。" - mightyWOZ

TreeSet 是由 NavigableMap 支持的，而不是 TreeMap。 - VIJ

@ViyaanJhiingade 已经更正，感谢您指出。 - Ankur Singhal