509

我一直很喜欢树木，它们很漂亮O(n*log(n))而且很整洁。然而，我认识的每一位软件工程师都尖锐地问我为什么要使用TreeSet. 从 CS 的背景来看，我认为你使用什么并不重要，我也不想乱用散列函数和存储桶（在 的情况下Java）。

在哪些情况下我应该使用 a HashSetover a TreeSet？

4

14 回答 14

872

HashSet 比 TreeSet 快得多（对于大多数操作，如添加、删除和包含，它是常数时间与日志时间），但不提供像 TreeSet 这样的排序保证。

哈希集

  • 该类为基本操作（添加、删除、包含和大小）提供恒定的时间性能。
  • 它不能保证元素的顺序会随着时间的推移保持不变
  • 迭代性能取决于 HashSet 的初始容量和负载因子。
    • 接受默认负载因子是非常安全的，但您可能希望指定一个初始容量，该容量大约是您期望集合增长到的大小的两倍。

树集

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

要点：

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

所以使用的选择完全取决于你的需求，但我觉得即使你需要一个有序的集合，那么你仍然应该更喜欢 HashSet 来创建 Set 然后将其转换为 TreeSet。

  • 例如SortedSet<String> s = new TreeSet<String>(hashSet);
于 2010-12-16T18:59:54.320 回答
39

a 尚未提及的一个优点TreeSet是它具有更大的“局部性”，这是以下说法的简写： (1) 如果两个条目按顺序靠近，则 aTreeSet将它们放在数据结构中彼此靠近的位置，因此在内存中；(2) 这种布局利用了局部性原则，即应用程序经常以相似的频率访问相似的数据。

这与 a 形成对比HashSet，后者将条目分布在整个内存中，无论它们的键是什么。

当从硬盘读取的延迟成本是从缓存或 RAM 读取的成本的数千倍时，并且当数据确实是本地访问时，这TreeSet可能是一个更好的选择。

于 2011-09-30T18:28:27.067 回答
27

HashSet访问元素是 O(1)，所以它确实很重要。但是保持集合中对象的顺序是不可能的。

TreeSet如果维护订单（根据值而不是插入顺序）对您很重要，这很有用。但是，正如您所指出的，您正在交易订单以获得更慢的访问元素时间：O(log n) 用于基本操作。

来自javadocsTreeSet：

此实现为基本操作（ 和 ）提供有保证的 log(n)add时间remove成本contains。

于 2009-09-23T00:13:50.977 回答
27

基于@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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝
于 2017-04-12T08:18:20.577 回答
23

1.HashSet 允许空对象。

2.TreeSet 不允许空对象。如果您尝试添加空值，它将抛出 NullPointerException。

3.HashSet比TreeSet快很多。

例如

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine
于 2012-11-16T05:26:14.860 回答
13

大多数使用的原因HashSet是操作是（平均）O（1）而不是O（log n）。如果该集合包含标准项目，您将不会像已经为您完成的那样“搞乱哈希函数”。如果集合包含自定义类，则必须实现hashCode才能使用HashSet（尽管 Effective Java 显示了如何），但如果使用 aTreeSet则必须制作Comparable或提供Comparator. 如果类没有特定的顺序，这可能是一个问题。

我有时使用TreeSet（或实际上TreeMap）用于非常小的集合/地图（< 10 个项目），尽管我没有检查这样做是否有任何真正的收获。对于大型集，差异可能相当大。

现在，如果您需要排序，那么TreeSet是合适的，尽管即使更新频繁并且对排序结果的需求很少，有时将内容复制到列表或数组并对其进行排序会更快。

于 2009-09-23T00:27:06.070 回答
11

如果您没有插入足够多的元素而导致频繁的重新散列（或冲突，如果您的 HashSet 无法调整大小），那么 HashSet 肯定会给您带来恒定时间访问的好处。但是在具有大量增长或收缩的集合上，您实际上可能会使用 Treesets 获得更好的性能，具体取决于实现。

如果没有记错的话，使用功能红黑树的摊销时间可以接近 O(1)。冈崎的书会有比我能理解的更好的解释。（或查看他的出版物列表）

于 2009-09-23T00:21:39.213 回答
7

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

那里的讨论还指出了一种有趣的“中间立场”方法来解决 Tree vs Hash 问题。Java提供了一个LinkedHashSet，它是一个HashSet，其中运行着一个“面向插入”的链表，即链表中的最后一个元素也是最近插入到Hash中的元素。这使您可以避免无序散列的不规则性，而不会增加 TreeSet 的成本。

于 2009-09-23T00:25:26.847 回答
4

TreeSet是两个排序集合之一（另一个是 TreeMap）。它使用红黑树结构（但您知道这一点），并保证元素按照自然顺序升序排列。或者，您可以使用 Comparable 或 Comparator 构造一个带有构造函数的 TreeSet，该构造函数允许您为集合提供您自己的顺序规则（而不是依赖于元素类定义的顺序）

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

于 2010-12-10T08:01:09.510 回答
4

既然可以吃橙子，为什么还要吃苹果？

说真的，伙计们-如果您的集合很大，读取和写入无数次，并且您要为 CPU 周期付费，那么只有当您需要它以更好地执行时，集合的选择才是相关的。然而，在大多数情况下，这并不重要——从人类的角度来看，这里和那里的几毫秒都不会被注意到。如果它真的那么重要，为什么不用汇编程序或 C 编写代码呢？[提示另一个讨论]。因此，关键是如果您对使用您选择的任何集合感到满意，并且它可以解决您的问题（即使它不是专门针对该任务的最佳集合类型），那么您就会被淘汰出局。该软件具有延展性。在必要时优化您的代码。Bob叔叔说过早优化是万恶之源。鲍伯叔叔这么说

于 2017-05-16T23:50:28.300 回答
2

即使在 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));

尝试猜测输出，然后将鼠标悬停在代码段下方以查看实际输出是什么。准备好？干得好：

假
真

没错，对于与 equals 不一致的比较器，它们不具有等价关系。这样做的原因是 aTreeSet使用比较器来确定等价，而HashSet使用equals. 他们在内部使用HashMap，TreeMap因此您也应该期望上述Maps 的这种行为。

最初回答

于 2020-07-22T06:24:22.203 回答
1

消息编辑（完全重写）当顺序无关紧要时，那就是时候了。两者都应该给出 Log(n) - 看看其中一个是否比另一个快 5% 以上会很有用。HashSet 可以在一个循环中给出 O(1) 测试应该揭示它是否是。

于 2009-09-23T00:28:50.580 回答
1

基于技术考虑，特别是在性能方面，已经给出了很多答案。在我看来，和之间的选择TreeSet很HashSet重要。

但我宁愿说选择应该首先由概念考虑驱动。

如果对于您需要操作的对象，自然排序没有意义，那么不要使用TreeSet.
它是一个排序集，因为它实现了SortedSet. 所以这意味着你需要覆盖函数compareTo，这应该与返回函数的内容一致equals。例如，如果您有一组名为 Student 的类的对象，那么我不认为TreeSet这是有道理的，因为学生之间没有自然的顺序。你可以按他们的平均成绩排序，好吧，但这不是“自然排序”。compareTo不仅当两个对象代表同一个学生时，而且当两个不同学生的成绩相同时，函数都会返回 0。对于第二种情况，equals将返回 false（除非您决定让后者在两个不同学生的成绩相同时返回 true，这会使equals函数具有误导性的含义，而不是说错误的含义。）
请注意和之间的这种equals一致性compareTo是可选的，但强烈推荐。否则接口的约定Set被破坏，使你的代码误导其他人，从而也可能导致意想不到的行为。

这个链接可能是关于这个问题的一个很好的信息来源。

于 2013-02-11T03:24:09.733 回答
-3 
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
于 2012-09-25T23:00:46.110 回答