什么时候使用 TreeSet 比使用 HashSet 更快？

Question

我一直在阅读有关此主题的内容，到目前为止，根据我对添加、删除和搜索操作的理解，HashSet 速度更快，时间复杂度为 O(1)，而 TreeSet 对于相同操作的时间复杂度为 O(log n)。当迭代元素时，HashSet 和 TreeSet 的时间复杂度都是 O(n)。

那么当 TreeSet 比 HashSet 更快时，什么是用例呢？

Answer 1

一般来说，您可以通过查看 Java 容器类实现的接口来最好地比较它们的功能。检查HashSet javadoc，您会看到它有Iterable<E>, Collection<E>, Set<E>. TreeSet有Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>.

所以区别是SortedSet和NavigableSet。这些是 TreeSet 提供而 HashSet 不提供的方法。如果您反过来查找他们的 javadoc，您将发现一系列组织起来的行为，以利用 TreeSet 中元素的顺序。HashSet 没有元素排序的概念。这是主要的区别。如果要对元素强加顺序，通常只能对它们进行单独排序，而按自然顺序遍历 TreeSet 则需要每个项目的摊销常量时间。（遍历的各个步骤所花费的时间可能与 log n 成正比。）

在实践中，并没有太多用例表明HashSet 性能的O(1)预期摊销时间与TreeSet 的共同方法的O(log n)保证时间之间的差异很重要。请记住，几乎所有实际用途的 log_2(n) 都小于 40。执行一些指令 40 次通常会导致调用算法的性能出现噪音。

当差异很重要时，您仍然需要考虑哈希性能的预期摊销add()性质，因为任何给定都可能需要 O(n) 时间来扩展内部存储桶数组并重新哈希所有内容。在某些应用中，这是一个杀手。例如，您的游戏通常运行得像闪电一样，但偶尔会在 10 Mb 哈希集增长到 20 Mb 时出现卡顿。类似地，如果您的数据恰好无法与 HashMap 的哈希函数配合使用（或者数据可能来自故意试图破坏它的恶意用户），则性能可能更像是 O(n)，而不是 O(1)。

TreeSet 的性能没有这么大的性能怪癖。例如，重组红黑树所花费的时间仅与 log_(n) 成正比，而这种情况很少见。也就是说，HashSet 的更高版本实际上使用树集作为存储桶，以避免被坏人利用。