Java Hashset vs Treeset

Question

我一直都喜欢树木，它们的优美O(n*log(n))和整洁。但是，我认识的每个软件工程师都曾明确地问过我为什么要使用TreeSet。从CS的背景出发，我认为你使用的所有内容都不重要，并且我也不在乎哈希函数和存储桶（对于Java）。

在哪种情况下，我应该使用HashSet over TreeSet？

Answer 1

HashSet比TreeSet快得多（对于大多数操作（如添加，删除和包含），恒定时间与日志时间相对应），但没有提供像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);