排序集的性能特征

Question

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

SortedSet

是用于快速添加/检索项目的最佳类吗？

Answer 1

Scala 2.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))中。这是否足够"快速"实际上取决于您的应用程序的特征，我不知道其中提供更广泛的答案。

有关收藏性能的更多详细信息，李浩义的这篇博文是一个很好的起点