包含TreeSet与另一个Set

Question

是否打开contains方法TreeSet(因为它已经默认排序)比说快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倍.