java - 当 O(1) 与 O(log n) 无关紧要时，TreeSet 与 HashSet 的小集合速度

Question

我一直在阅读有关 HashSet 与 TreeSet 的复杂性的研究，并且到处都能找到解释的主题:“HashSet 更快，因为它O(1) 而不是 O(log n)。”我当然知道这一点。

但是，这仅适用于处理非常大的集合时。另一方面，我需要处理数以百万计的“小”集合，每个集合最多包含 200 个对象，并且最多包含更少(低于 20 个)。对它们的操作非常多样化(创建、添加、删除、成员测试、克隆……)，因此我对如何最好地衡量/模拟差异感到困惑。

对于如此小的集合大小，这两个类中哪个类的开销最小？在速度和内存开销方面。那么 LinkedHashSet 呢？

Answer 1

and hence I'm puzzled on how to best measure/simulate the difference.

使用分析器。如果 Set 操作不支配结果(CPU 时间、内存占用、分配率)，那么由于 amdahl's law.，您的选择在实践中不会产生影响。 .

TreeSet 的最大优点是排序。

而且这两种实现都不是特别节省内存，还有更好的 Sets，具体取决于您最关心的性能指标。它们是相应 Map 实现的包装器，而 Map 本身也不是特别有效。

它们更注重灵 active ，提供大量的 API，而不是优化任何特定的性能方面。