Hashset vs Treeset
我一直都很喜欢树木，那个漂亮的O（n * lg（n））和它们的整洁。 但是，我所知道的每一位软件工程师都尖锐地问我为什么要使用TreeSet 。 从CS的背景来看，我认为这不重要，而且我不关心散列函数和存储区（在Java的情况下）。
在哪种情况下，我应该使用TreeSet的HashSet ？
HashSet比TreeSet快很多（大多数操作（如add，remove和contains）的常量时间和日志时间），但是并没有像TreeSet那样的顺序保证。
HashSet的
- 类为基本操作（添加，删除，包含和大小）提供恒定的时间performance。
- 但并不能保证元素的顺序会随着时间的推移保持不变
- 迭代性能取决于HashSet的初始容量和负载因子 。
- 接受默认加载因子是相当安全的，但是您可能需要指定一个初始容量，该容量大约是您希望增长的大小的两倍。
TreeSet中
- 保证log（n）基本操作的时间成本（添加，删除和包含）
- 保证set的元素将被sorting（升序，自然，或者通过你的构造函数指定的）（实现
SortedSet） - 不会为迭代性能提供任何调整参数
- 提供了一些方便的方法来处理像
first()，last()，headSet()和tailSet()等有序集
重要的一点：
- 两者都保证元素的免费收集
- 将元素添加到HashSet通常会更快，然后将集合转换为TreeSet以进行无重复sorting的遍历。
- 这些实现都没有同步。 也就是说，如果多个线程同时访问一个集合，并且至less有一个线程修改了集合，那么它必须在外部同步。
- LinkedHashSet在某种意义上介于
HashSet和TreeSet之间。 作为一个哈希表来实现，链表通过它运行，但是它提供的插入顺序迭代与TreeSet保证的sorting遍历不一样 。
所以使用的select完全取决于你的需求，但我觉得即使你需要一个有序集合，你仍然应该更喜欢HashSet来创buildSet，然后将其转换为TreeSet。
- 例如
SortedSet<String> s = new TreeSet<String>(hashSet);
TreeSet还没有提到的一个优点是它具有更大的“局部性”，这就是说：（1）如果两个条目在顺序附近，则TreeSet将它们放在数据结构中彼此靠近，因此在内存中; （2）这种布局利用了局部性原理，即类似的数据经常被类似频率的应用访问。
这与HashSet相反， HashSet将条目遍布整个内存，而不pipe它们的密钥是什么。
当从硬盘读取的延迟成本是从caching或RAM中读取的成本的数千倍时，并且当数据真正用本地访问时， TreeSet可能是更好的select。
HashSet是O（1）来访问元素，所以它肯定是重要的。 但是维持对象的顺序是不可能的。
如果维护一个订单（根据数值而不是插入顺序），则TreeSet很有用。 但是，正如你所指出的那样，为了访问一个元素，你要交易的时间较慢：O（log n）用于基本操作。
从TreeSet的javadocs ：
这个实现为基本操作（
add，remove和contains）提供了保证的log（n）时间成本。
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
大多数情况下使用HashSet的原因是操作（平均）O（1）而不是O（log n）。 如果该集合包含标准项目，那么您将不会像为您所做的那样“散列哈希函数”。 如果该集合包含自定义类，则必须实现hashCode以使用HashSet （尽pipeEffective Java显示方式如何），但是如果使用TreeSet ，则必须将其设置为Comparable或提供Comparator 。 如果class级没有特定的顺序，这可能是一个问题。
我有时使用TreeSet （或实际上是TreeMap ）来处理非常小的集合/地图（<10项），尽pipe我没有检查是否有真正的收益。 对于大集合，差异可能是相当大的。
现在，如果你需要sorting，那么TreeSet是适当的，即使如此，如果更新频繁并且对sorting结果的需要不频繁，有时将内容复制到列表或数组并sorting它们可能会更快。
如果你没有插入足够的元素来导致频繁的重新哈希（或冲突，如果你的HashSet不能resize），HashSet肯定会给你持续时间访问的好处。 但在具有大量增长或收缩的集合上，取决于实现，您可能实际上使用Treeset获得更好的性能。
如果记忆为我服务，那么摊销时间可以接近O（1），并带有一个function性的红黑树。 冈崎的书会有比我更好的解释。 （或者看他的出版物清单 ）
当然，HashSet的实现速度要快得多，因为没有sorting。 在http://java.sun.com/docs/books/tutorial/collections/implementations/set.html上提供了Java中各种Set实现的良好分析。;
那里的讨论也指出了Tree vs Hash问题的一个有趣的“中间地带”方法。 Java提供了一个LinkedHashSet，它是一个带有“插入导向”链表的HashSet，也就是说，链表中的最后一个元素也是最近插入到Hash中的。 这样可以避免不必要的散列乱序，而不会增加TreeSet的成本。
基于@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 ║ ╚══════════════╩═══════════════════════════════════════════════════════════════╝
TreeSet是两个有序集合之一（另一个是TreeMap）。 它使用红黑树的结构（但你知道），并保证元素将按照自然顺序从小到大。 或者，您可以使用构造函数构造一个TreeSet，通过使用Comparable或Comparator，您可以让该集合拥有自己的规则（而不是依赖元素的类定义的顺序）
而LinkedHashSet是HashSet的一个有序版本，它在所有元素之间维护一个双向链表。 当您关心迭代顺序时，请使用此类而不是HashSet。 在迭代HashSet时，顺序是不可预知的，而LinkedHashSet允许您按插入顺序遍历元素
基于技术考虑，特别是在性能方面，已经给出了很多答案。 据我TreeSet ， TreeSet和HashSet之间的select很重要。
但我宁愿说这个select应该首先由概念上的考虑所驱动。
如果对于需要操作的对象，自然sorting没有意义，那么不要使用TreeSet 。
它是一个有序集合，因为它实现了SortedSet 。 所以这意味着你需要重载函数compareTo ，它应该和返回函数equals一致。 例如，如果您有一组名为Student的类的对象，那么我不认为TreeSet是合理的，因为学生之间没有自然的顺序。 你可以按他们的平均等级来定购，但是这不是一个“自然顺序”。 函数compareTo不仅在两个对象代表同一个学生时返回0，而且当两个不同的学生具有相同的等级时。 对于第二种情况， equals会返回错误（除非您决定在两个不同的学生具有相同等级时使后者返回真，这将使得equals函数具有误导性含义，而不是错误的含义）。
请注意， equals和compareTo之间的一致性是可选的，但强烈build议。 否则，接口Set的合同被破坏，使你的代码误导给其他人，从而也可能导致意想不到的行为。
这个链接可能是关于这个问题的一个很好的信息来源。
消息编辑（ 完全重写 ）订单无关紧要时，即时。 两者都应该给Log（n） – 看看是否比另一个快5％以上是有用的。 HashSet可以给循环中的O（1）testing显示是否是。
为什么有苹果，当你可以有橘子？
认真的人和gals – 如果你的collections是大的，阅读和书面的时代，并且你正在支付CPU周期，那么收集的select是相关的，只有当你需要它performance更好。 然而，在大多数情况下，这并不重要 – 从人类的angular度来看，这里和那里几毫秒都没有被注意到。如果真的这么重要，为什么不用编译器或c编写代码呢？ [提示另一个讨论]。 所以问题是，如果你喜欢使用你select的任何一个集合，并且它解决了你的问题（即使它不是专门为这个任务devise的最好的集合types），那就自己敲一下。 软件是可塑的。 在必要时优化您的代码。 叔叔鲍勃说过早优化是万恶之源。 鲍伯叔叔这样说
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)); } }
