我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
当前回答
大多数人使用HashSet的原因是操作(平均)是O(1)而不是O(log n)。如果集合包含标准项,你就不会像以前那样“乱搞哈希函数”。如果集合包含自定义类,则必须实现hashCode才能使用HashSet(尽管Effective Java演示了如何使用),但如果使用TreeSet,则必须使其具有可比性或提供比较器。如果类没有特定的顺序,这可能是一个问题。
我有时会使用TreeSet(或者实际上是TreeMap)用于非常小的集合/映射(< 10项),尽管我没有检查这样做是否有任何真正的好处。对于大型机组,差异可能相当大。
现在,如果您需要排序,那么TreeSet是合适的,尽管即使如此,如果更新频繁,对排序结果的需求并不频繁,有时将内容复制到列表或数组中并对它们排序会更快。
其他回答
如果您没有插入足够多的元素导致频繁重散列(或冲突,如果您的HashSet不能调整大小),那么HashSet当然可以为您提供常量时间访问的好处。但是对于有大量增长或收缩的集合,使用Treesets实际上可能会获得更好的性能,这取决于实现。
如果我没记错的话,平摊时间可以接近于一个功能性红黑树的O(1)。冈崎的书会有比我更好的解释。(或参阅他的出版物列表)
1.HashSet允许空对象。
2.树集不允许空对象。如果你试图添加空值,它将抛出一个NullPointerException。
3.HashSet比TreeSet快得多。
e.g.
TreeSet<String> ts = new TreeSet<String>();
ts.add(null); // throws NullPointerException
HashSet<String> hs = new HashSet<String>();
hs.add(null); // runs fine
TreeSet是两个排序集合之一(另一个是 TreeMap)。它使用红黑树结构(但你知道),并保证 元素会按照自然的顺序,按升序排列。可选地, 您可以使用构造函数构造TreeSet,该构造函数允许您为集合提供您的 自己制定顺序规则(而不是依赖于定义的顺序) 通过使用Comparable或Comparator)
LinkedHashSet是HashSet的有序版本 在所有元素之间维护一个双链接列表。使用这个类而不是HashSet 当你关心迭代顺序时。迭代HashSet时 顺序是不可预测的,而LinkedHashSet允许您迭代元素 按照它们被插入的顺序
HashSet是O(1)来访问元素,所以这当然很重要。但是保持集合中对象的顺序是不可能的。
如果维护顺序(根据值而不是插入顺序)对您很重要,TreeSet是有用的。但是,正如您所注意到的,您正在以顺序换取访问元素的更慢时间:基本操作为O(log n)。
来自TreeSet的javadocs:
该实现为基本操作(添加、删除和包含)提供了log(n)的时间成本。
TreeSet的一个尚未被提及的优点是它有更大的“局部性”,这是以下说法的简写:(1)如果两个条目在顺序上是相邻的,TreeSet将它们放在数据结构中彼此相邻的地方,因此在内存中也是如此;并且(2)这种布局利用了局部性原则,该原则说类似的数据通常被一个应用程序以相似的频率访问。
这与HashSet相反,HashSet将条目分布在内存中,而不管它们的键是什么。
当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍,并且当数据确实是通过局部性访问时,TreeSet可能是更好的选择。