哈希集与树集

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

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

从TreeSet的javadocs:

这个实现为基本操作(add， remove和contains)提供了有保证的log(n)时间成本。

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

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

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

这里的讨论还指出了一种有趣的“中间地带”方法来解决树与哈希的问题。Java提供了一个LinkedHashSet，它是一个HashSet，其中运行着一个“面向插入”的链表，也就是说，链表中的最后一个元素也是最近插入到哈希中的元素。这允许您避免无序散列的无序性，而不会增加TreeSet的成本。

大多数人使用HashSet的原因是操作(平均)是O(1)而不是O(log n)。如果集合包含标准项，你就不会像以前那样“乱搞散列函数”。如果集合包含自定义类，你必须实现hashCode来使用HashSet(尽管Effective Java显示了如何)，但如果你使用TreeSet，你必须使它Comparable或提供Comparator。如果类没有特定的顺序，这可能是一个问题。

我有时会将TreeSet(实际上是TreeMap)用于非常小的集/映射(<10项)，尽管我没有检查这样做是否有任何真正的好处。对于大型机组，差异可能相当大。

现在如果你需要排序，那么TreeSet是合适的，尽管即使这样，如果更新频繁，对排序结果的需求并不频繁，有时将内容复制到列表或数组并对它们排序会更快。

当顺序无关紧要时，就是当。两者都应该给出Log(n) -看看其中一个是否比另一个快5%以上是有用的。HashSet可以在循环中给出O(1)测试，应该可以揭示它是否正确。

和A LinkedHashSet是HashSet的有序版本 在所有元素之间维护一个双链接列表。使用这个类而不是HashSet 当你关心迭代顺序时。迭代HashSet时 顺序是不可预测的，而LinkedHashSet允许您迭代元素

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

HashSet

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

  TreeSet

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

  重要的几点:

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

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

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

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

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

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

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));
}
}

1.HashSet允许空对象。

2.树集不允许空对象。如果你试图添加空值，它将抛出一个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

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

基于@shevchyk可爱的视觉的答案 on Maps，以下是我的看法:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

明明可以吃橘子，为什么要吃苹果?

说真的，如果你的集合很大，读和写的次数很多，而且你要为CPU周期买单，那么只有当你需要它更好地执行时，选择集合才有意义。然而，在大多数情况下，这并不重要——在人类看来，这里那里的几毫秒是不会被注意到的。如果它真的那么重要，你为什么不用汇编程序或C语言写代码?(提示另一场讨论)。因此，关键是如果您喜欢使用您选择的任何集合，并且它解决了您的问题(即使它不是特定的最佳集合类型)，那么请自便。软件是可塑的。在必要的地方优化代码。Bob叔叔说过早的优化是万恶之源。鲍勃叔叔这么说的

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

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

false
真正的< / p >

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

原来回答 .