java - 哈希集与树集

Question

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

在哪些情况下我应该使用 HashSet超过 TreeSet ?

Answer 1

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

HashSet

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

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