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

Question

我一直在阅读这个主题，到目前为止，从我对添加、删除和搜索操作的理解来看，HashSet 速度更快，时间复杂度为 O(1)，而 TreeSet 的时间复杂度为 O(log n)。当遍历元素时，HashSet 和 TreeSet 的时间复杂度都是 O(n)。

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

标签： javadata-structurescomputer-science

Answer 1

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

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

在实践中，没有太多用例，其中 O(1)的 HashSet 性能预期摊销时间和 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 实际上使用树集作为存储桶，以避免被坏人利用。