java - 什么更快？ 1)向treeset添加元素VS 2)添加到Hashset然后对hashset元素进行排序

Question

我想知道哪个集合可以提供更好的性能。如果需要的结果是获得不重复排序的集合。

1. treeSet - O(nlogn)
2. hashSet - 添加 n 个元素的时间复杂度为 O(n)，然后使用 collection.sort() 排序的时间复杂度为 O(nlogn)

理论上两者给出的结果是相同的，但想知道如果传递的输入长度超过 100K，是否真的有任何区别。还有可能是什么原因呢？

Answer 1

Collections.sort() 在内部使用 TimSort，这可能比向 TreeSet 添加元素要快一些。但更重要的是，HashSet 和 Collections.sort() 的内存开销应该低于 TreeSet。