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

Question

上的 contains 方法TreeSet（因为它已经按默认排序）比 say 快HashSet吗？

我问的原因是，Collections.binarySearch如果对 List 进行排序，那会非常快，所以我认为 TreeSet 的 contains 方法可能是相同的。

Answer 1

从TreeSet的 javadoc ：

此实现为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本。

从HashSet的javadoc ：

此类为基本操作（添加、删除、包含和大小）提供恒定的时间性能，假设哈希函数将元素正确地分散在桶中。

所以答案是否定的。

查看实现（JDK 1.7 oracle），treeset.contains（resp.hashtree）依赖于treemap.containsKey（resp.hashmap）方法。containsKey 循环遍历 hashmap 中的一个哈希桶（可能只包含一项），而它循环遍历整个映射，在树形图中从一个节点移动到另一个节点，使用 compareTo 方法。如果您的项目是最大的或最小的，这可能需要更多的时间。

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