Hashset和Treeset的区别

Question

Hashset和Treeset的区别

518

我一直喜欢树，它们漂亮的O(n*log(n))以及整齐有序的特点。然而，我认识的每个软件工程师都曾经直截了当地问我为什么要使用TreeSet。从计算机科学背景来看，我认为你使用哪个并不是很重要，并且我也不想在哈希函数和桶（对于Java）方面进行操作。

在哪些情况下应该使用HashSet而不是TreeSet？

- heymatthew

14个回答

41

< p >一个 < code > TreeSet 的优势是它具有更大的"局部性"，也就是说(1)如果两个条目在排序中相邻，< code > TreeSet 将它们放置在数据结构中靠近彼此，因此在内存中也靠近；(2)此位置利用了"局部性原理"，该原理指出类似的数据通常由应用程序相似的频率访问。 < p >这与 < code > HashSet 不同，后者将条目分散到内存中，无论其键是什么。

< p >当从硬盘读取的延迟成本比从缓存或 RAM 读取的成本高数千倍时，并且当确实存在局部性数据访问时，< code > TreeSet 可能是更好的选择。

- Carl Andersen

3

你能否证明，如果两个条目在顺序中彼此相邻，那么 TreeSet 会将它们放置在数据结构中的相邻位置（因此也在内存中相邻）？ - David Soroko

8

对于Java而言这并不相关。集合中的元素本来就是对象并且指向其他地方，因此你并没有节省太多东西。 - Andrew Gallasch

2

除了其他评论普遍指出Java缺乏局部性之外，OpenJDK的TreeSet/TreeMap实现并没有进行局部性优化。虽然可以使用4阶B树来表示红黑树，从而提高局部性和缓存性能，但这不是实现的方式。相反，每个节点都存储指向其自身键、值、父节点以及左右子节点的指针，这在TreeMap.Entry的JDK 8源代码中很明显。 - kbolino

28

基于@shevchyk在地图上的可爱视觉答案，这是我的看法：

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashSet       ║      TreeSet      ║     LinkedHashSet   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Add/remove   ║        O(1)         ║     O(log(n))     ║        O(1)         ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableSet    ║                     ║
║  Interfaces  ║         Set         ║       Set         ║         Set         ║
║              ║                     ║    SortedSet      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║    not allowed    ║                     ║
║  Null values ║       allowed       ║ 1st element only  ║      allowed        ║
║              ║                     ║     in Java 7     ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═══════════════════════════════════════════════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

- kiedysktos

27

HashSet的时间复杂度为O(1)，因此它很重要。但是无法保持集合中对象的顺序。

TreeSet对于需要维护顺序(按值而非插入顺序)的情况非常有用。但是，正如您所指出的，这样做会以访问元素的速度变慢为代价：基本操作的时间复杂度为O(log n)。

从TreeSet的Javadocs中可知：

此实现提供了基本操作(add, remove 和 contains)的对数时间复杂度(O(log n))。

- duffymo

23

1.HashSet允许空对象。

2.TreeSet不允许空对象。如果您尝试添加空值，它将抛出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

- SuReN

3

如果在TreeSet中添加null作为第一个对象，则ts.add(null)将正常工作。但是，在此之后添加的任何对象都会在比较器的compareTo方法中导致NullPointerException。 - Shoaib Chikate

2

无论如何，您真的不应该将“null”添加到您的集合中。 - fluffy

TreeSet<String> badassTreeSet = new TreeSet<String>(new Comparator<String>() { public int compare(String string1, String string2) { if (string1 == null) { return (string2 == null) ? 0 : -1; } else if (string2 == null) { return 1; } else { return string1.compareTo(string2); } } }); badassTreeSet.add("tree"); badassTreeSet.add("asdf"); badassTreeSet.add(null); badassTreeSet.add(null); badassTreeSet.add("set"); badassTreeSet.add("tree"); System.out.println(badassTreeSet);

- Dávid Horváth

@ShoaibChikate，你的陈述在我的Java版本（Oracle Corporation 11.0.4+10-LTS）中不准确。第一个插入的元素总是与其自身进行比较，因此如果第一个元素为null，则会抛出NullPointerException。 - M. Justin

这并不是严格正确的。如果使用允许空值的比较器创建了 TreeSet，则可以添加 null 值。根据 TreeSet.add(E e) 的说明："如果指定的元素为 null 并且此 set 使用自然排序，或者其比较器不允许 null 元素，则抛出 NullPointerException 异常"。以下代码成功将 null 添加到 TreeSet 中：new TreeSet<>(Comparator.nullsLast(Comparator.naturalOrder())).add(null);。 - M. Justin

13

大多数人使用HashSet的原因是其操作（平均而言）为O(1)，而不是O(log n)。如果集合包含标准项，则无需“围绕哈希函数”进行操作，因为这已经为您完成了。如果集合包含自定义类，则必须实现hashCode才能使用HashSet（虽然《Effective Java》展示了如何实现），但如果您使用TreeSet，则必须使其Comparable或提供一个Comparator。如果该类没有特定的顺序，这可能成为一个问题。

有时我会对非常小的集合/映射（＜10个项目）使用TreeSet（或实际上是TreeMap），尽管我并没有检查是否真的有什么实际的收益。对于大型集合，差异可能相当大。

如果需要排序，则TreeSet是适当的，尽管即使在这种情况下，如果更新频繁且较少需要排序的结果，有时将内容复制到列表或数组中并对其进行排序可能会更快。

- Kathy Van Stone

这些大元素上的任何数据点，例如10K或更多。 - kuhajeyan

11

如果插入的元素不足以导致哈希表频繁地重新散列（或者如果你的HashSet不能调整大小而出现冲突），那么HashSet肯定会给你带来恒定时间访问的好处。但对于经常增长或缩小的集合，根据实现方式，使用TreeSet可能会获得更好的性能。

如果我没记错，使用红黑树可以获得接近O(1)的平摊时间。Okasaki的书比我说的更好解释这个问题。（或者请参见他的出版物列表）

- JasonTrue

7

HashSet实现方式当然要快得多，因为没有排序，所以开销更小。在http://java.sun.com/docs/books/tutorial/collections/implementations/set.html上提供了对Java中各种Set实现的良好分析。

那里的讨论还指出了一种有趣的“中间地带”方法来解决Tree vs Hash的问题。Java提供了一个LinkedHashSet，它是一个HashSet，其中运行着一个“插入定向”的链接列表，即链接列表中的最后一个元素也是最近插入到Hash中的元素。这样可以避免无序哈希的混乱，而不会增加TreeSet的成本。

- Joseph Weissman

4

TreeSet是两个有序集合之一（另一个是TreeMap）。它使用红黑树结构（但您已经知道了），并保证元素按自然顺序升序排列。可选地，您可以使用具有构造函数的TreeSet来为集合提供您自己的规则，以确定顺序（而不是依赖于元素类定义的顺序），方法是使用Comparable或Comparator。

LinkedHashSet是HashSet的有序版本，它在所有元素中维护双向链接列表。在意迭代顺序时，请使用此类代替HashSet。当您遍历HashSet时，顺序是不可预测的，而LinkedHashSet允许您按照插入顺序遍历元素。

- subhash laghate

4

为什么只吃苹果，不尝试一下橙子呢？

亲爱的朋友们，如果你的集合非常大，并且被反复读写，而你还要支付CPU周期的费用，那么集合的选择只有在需要它更好地执行时才是相关的。然而，在大多数情况下，这并不真的重要——几毫秒的时间对人类来说是无关紧要的。如果真的那么重要，为什么不用汇编或C语言编写代码呢？[引出另一个讨论]。所以，如果你满意使用你选择的任何集合，并且解决了你的问题[即使它不是特定任务的最佳类型的集合]，那就愉快地使用吧。软件是可塑的。必要时优化你的代码。鲍勃大叔说：过早地优化是万恶之源。鲍勃大叔这么说

- KRK Owner

即使您通过 Set<T> 引用使用您的集合，您也必须立即选择一个具体的类来实例化它，并提供所需的方法（equals、compare、hashcode）。没有优化，只是尝试做出适当的选择，以便您以后不必更改它。 - Michel Billaud

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sactiw · Accepted Answer

HashSet比TreeSet更快（对于大多数操作，例如添加、删除和包含，其时间复杂度是常数时间与对数时间的比较），但不像TreeSet那样提供排序保证。

HashSet

该类基本操作（添加、删除、包含和大小）具有常数时间性能。
它不能保证元素的顺序随时间保持不变。
迭代性能取决于HashSet的初始容量和负载系数。
- 接受默认负载系数是相当安全的，但您可能希望指定大约是期望集合增长两倍大小的初始容量。

TreeSet

基本操作（添加、删除和包含）具有log(n)时间成本。
保证集合中的元素将被排序（升序、自然排序或通过其构造函数指定的排序方式）（实现SortedSet）。
不提供任何调整参数以优化迭代性能。
提供一些有用的方法来处理排序集合，如first()，last()，headSet()和tailSet()等等。

重要提示：

两者都保证集合中元素不重复
向HashSet添加元素然后将集合转换为TreeSet进行无重复排序遍历通常更快。
这两种实现都没有同步。也就是说，如果多个线程同时访问一个集合，并且其中至少一个线程修改了集合，则必须在外部进行同步。
LinkedHashSet 在某种意义上介于 HashSet 和 TreeSet 之间。它是一个带有链表的哈希表，提供了按插入顺序迭代的功能，但与 TreeSet 提供的排序遍历不同。

因此，使用哪种集合取决于您的需求，但我认为即使您需要有序集合，您仍应该首选 HashSet 来创建集合，然后将其转换为 TreeSet。

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