2023-08-25 09:00:07

树对树

我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。

在哪些情况下,我应该在树集上使用HashSet ?


当前回答

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

其他回答

如果您没有插入足够多的元素导致频繁重散列(或冲突,如果您的HashSet不能调整大小),那么HashSet当然可以为您提供常量时间访问的好处。但是对于有大量增长或收缩的集合,使用Treesets实际上可能会获得更好的性能,这取决于实现。

如果我没记错的话,平摊时间可以接近于一个功能性红黑树的O(1)。冈崎的书会有比我更好的解释。(或参阅他的出版物列表)

HashSet是O(1)来访问元素,所以这当然很重要。但是保持集合中对象的顺序是不可能的。

如果维护顺序(根据值而不是插入顺序)对您很重要,TreeSet是有用的。但是,正如您所注意到的,您正在以顺序换取访问元素的更慢时间:基本操作为O(log n)。

来自TreeSet的javadocs:

该实现为基本操作(添加、删除和包含)提供了log(n)的时间成本。

TreeSet的一个尚未被提及的优点是它有更大的“局部性”,这是以下说法的简写:(1)如果两个条目在顺序上是相邻的,TreeSet将它们放在数据结构中彼此相邻的地方,因此在内存中也是如此;并且(2)这种布局利用了局部性原则,该原则说类似的数据通常被一个应用程序以相似的频率访问。

这与HashSet相反,HashSet将条目分布在内存中,而不管它们的键是什么。

当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍,并且当数据确实是通过局部性访问时,TreeSet可能是更好的选择。

即使在11年后,也没有人想到提到一个非常重要的区别。

你认为如果HashSet等于TreeSet,那么反过来也成立吗?看看这段代码:

TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.add("a");
hashSet.add("A");
System.out.println(hashSet.equals(treeSet));
System.out.println(treeSet.equals(hashSet));

尝试猜测输出,然后徘徊在代码片段下面,看看真正的输出是什么。准备好了吗?给你:

假 真正的

没错,如果比较器与等号不一致,它们就不具有等价关系。原因是TreeSet使用比较器来确定等价性,而HashSet使用等号。在内部,它们使用HashMap和TreeMap,所以你应该预料到上述map也会有这种行为。

最初的回答

HashSet比TreeSet快得多(对于添加、删除和包含等大多数操作,HashSet是常量时间,而不是日志时间),但不像TreeSet那样提供排序保证。

HashSet

该类为基本操作(添加、删除、包含和大小)提供恒定的时间性能。 它不能保证元素的顺序随时间保持不变 迭代性能取决于初始容量和HashSet的负载因子。 接受默认的负载因子是相当安全的,但您可能希望指定的初始容量大约是您期望该集增长的两倍。

TreeSet

保证基本操作(添加、删除和包含)的时间成本为log(n) 确保set的元素将被排序(升序,自然或由你通过它的构造函数指定)(实现SortedSet) 不为迭代性能提供任何调优参数 提供了一些方便的方法来处理有序集,如first(), last(), headSet()和tailSet()等

重要的几点:

Both guarantee duplicate-free collection of elements It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal. None of these implementations are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however,it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.

因此,使用方法的选择完全取决于您的需要,但我认为,即使您需要一个有序的集合,那么您仍然应该使用HashSet来创建Set,然后将其转换为TreeSet。

例如:SortedSet<String> s = new TreeSet<String>(hashSet);