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

Question

我一直在阅读有关该主题的一些文章，到目前为止，从我对添加、删除和搜索操作的理解来看，HashSet 的速度更快，时间复杂度为 O(1)，而 TreeSet 的时间复杂度为 O(log n) 相同的操作。遍历元素时，HashSet 和 TreeSet 的时间复杂度均为 O(n)。

那么 TreeSet 比 HashSet 更快的用例是什么？

Answer 1

通常，您可以通过查看 Java 容器类实现的接口(interface)来最好地比较它们的功能。检查the 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 没有元素排序的概念。这是主要区别。如果你想对元素强加一个顺序，你通常仅限于分别对它们进行排序，而以自然顺序遍历 TreeSets 是每个项目的摊销常数时间。 (遍历的各个步骤可以花费时间成比例的log n。)

在实践中，HashSet 性能的 O(1) 预期摊销时间 与 O(log n) 保证 之间存在差异的用例并不多事实证明，TreeSet 的时间对于它们共有的方法很重要。请记住，log_2(n) 几乎在所有实际用途中都小于 40。执行几条指令 40 次通常会在调用算法的性能中产生噪声。

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

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