0

我正在运行一些基准测试。我的一项测试取决于顺序，因此我为此使用了 TreeSet。我的第二个测试没有，所以我使用了 HashSet。

我知道 TreeSet 的插入速度较慢。但是遍历所有元素呢？

4

3 回答 3

1

来自类似的帖子（Hashset vs Treeset）：

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

哈希集：

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

树集：

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

要点：

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

所以使用的选择完全取决于你的需要，但我觉得即使你需要一个有序的集合，那么你仍然应该更喜欢 HashSet 来创建 Set 然后将其转换为 TreeSet。

  • 例如Set<String> s = new TreeSet<String>(hashSet);
于 2013-11-05T20:34:19.840 回答
1

TreeSets内部使用TreeMapswhich are Red Black Trees(special type of BST) 。

BST中序遍历是O(n)

HashSets内部使用HashMapswhicharray用于保存 Entry 对象。

这里也应该遍历O(n)。

除非您编写基准测试，否则很难证明哪个更快。

于 2013-11-05T20:58:32.487 回答
0

如果您想要（几乎）具有 a 性能的稳定排序HashSet，请使用 a LinkedHashSet。你仍然会得到恒定时间的操作，而我会假设 aTreeSet会让你得到对数时间。

于 2013-11-05T20:33:39.647 回答