SortedSet的性能特性

Question

我希望将项目保存在列表中，以便进行快速访问。添加/检索性能很重要，但是我找不到关于SortedSet：https://docs.scala-lang.org/overviews/collections/performance-characteristics.html的性能特性的任何信息。

当我的项目被排序时，SortedSet是快速添加/检索的最佳类吗？

Answer 1

Scala2.12中SortedSet的默认实现使用TreeSet

scala> val s = scala.collection.SortedSet(3, 5, 1)
s: scala.collection.SortedSet[Int] = TreeSet(1, 3, 5)

在内部，TreeSet是使用红黑树实现的。这意味着搜索和插入操作都将在O(log(n))中。如果这是“快速”，这真的取决于您的应用程序的特点，在其中，我不知道足够提供一个更广泛的答案。

有关集合性能的详细信息，请参阅李浩毅的这篇博文是一个很好的起点。