哈希集与树集

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

在什么情况下我应该使用HashSet over a TreeSet?

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

HashSet http://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

• 该类为基本操作（添加、删除、包含和大小）提供恒定的时间性能。
• 它不保证元素的顺序随着时间的推移保持不变
• iteration performance depends on the initial capacity and the load factor of the HashSet.
  • 接受默认负载因子是相当安全的，但您可能需要指定一个初始容量，该容量大约是您期望集合增长到的大小的两倍。

TreeSet http://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html

• 保证基本操作（添加、删除和包含）的 log(n) 时间成本
• 保证 set 的元素将被排序（升序、自然或您通过其构造函数指定的排序）（实现SortedSet http://docs.oracle.com/javase/8/docs/api/java/util/SortedSet.html)
• 不提供任何迭代性能调整参数
• 提供了一些方便的方法来处理有序集，例如first() http://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html#first--, last(), headSet() http://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html#headSet-E-, and tailSet() http://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html#tailSet-E- etc

要点：

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

因此，使用方式的选择完全取决于您的需求，但我认为即使您需要有序集合，您仍然应该更喜欢使用 HashSet 创建 Set，然后将其转换为 TreeSet。

• e.g. SortedSet<String> s = new TreeSet<String>(hashSet);