java - 包含在 TreeSet 上与另一个 Set

Question

TreeSet 上的 contains 方法(因为它已经默认排序)比说 HashSet 快吗？

我问的原因是，如果列表已排序，Collections.binarySearch 会非常快，所以我认为 TreeSet 的 contains 方法可能是相同的。

Answer 1

来自 TreeSet 的 javadoc :

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

来自 HashSet 的 javadoc :

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

所以答案是否定的。

查看实现(JDK 1.7 oracle)，treeset.contains (resp.hashtree) 依赖于 treemap.containsKey (resp.hashmap) 方法。 containsKey 在 HashMap 中的一个哈希桶(可能只包含一项)上循环，而它在整个 map 上循环，使用 compareTo 方法在 TreeMap 中从一个节点移动到另一个节点。如果您的项目是最大的或最小的，这可能会花费更多的时间。

最后，我用一棵包含 1m 整数的树进行了快速测试(是的，我知道，不是很可靠)并寻找 2 个最大的树之一，这迫使树集浏览整个集合。 HashSet 快了 50 倍。