集合（Scala 2.8 - 2.12）

具体不可变集合类

过时通知

Scala 提供了许多具体的不可变集合类供你选择。它们在实现的特征（映射、集合、序列）、是否可以是无限的以及各种操作的速度上有所不同。以下是 Scala 中使用的一些最常见的不可变集合类型。

列表

列表是一个有限的不可变序列。它们提供对第一个元素以及列表其余部分的恒定时间访问，并且它们有一个恒定时间的 cons 操作，用于在列表前面添加新元素。许多其他操作需要线性时间。

列表一直是 Scala 编程的主力，因此这里不需要过多介绍。2.8 中的主要变化是 List 类及其子类 :: 及其子对象 Nil 现在定义在包 scala.collection.immutable 中，它在逻辑上属于那里。在 scala 包中仍然有 List、Nil 和 :: 的别名，因此从用户的角度来看，可以像以前一样访问列表。

另一个更改是，列表现在与集合框架更紧密地集成，并且不像以前那样特殊。例如，最初存在于 List 伴随对象中的所有众多方法都已弃用。它们被每个集合继承的统一创建方法替换。

流

流就像列表，只不过它的元素是延迟计算的。因此，流可以无限长。只有请求的元素才会被计算。否则，流具有与列表相同的性能特征。

列表使用 :: 运算符构建，而流使用类似的 #:: 构建。下面是一个包含整数 1、2 和 3 的流的简单示例

scala> val str = 1 #:: 2 #:: 3 #:: Stream.empty
str: scala.collection.immutable.Stream[Int] = Stream(1, ?)

此流的头部是 1，尾部是 2 和 3。但是，此处未打印尾部，因为它尚未计算！流被指定为延迟计算，流的 toString 方法小心不要强制进行任何额外评估。

下面是一个更复杂的示例。它计算一个流，其中包含从给定两个数字开始的斐波那契数列。斐波那契数列是一个数列，其中每个元素都是数列中前两个元素的和。

scala> def fibFrom(a: Int, b: Int): Stream[Int] = a #:: fibFrom(b, a + b)
fibFrom: (a: Int,b: Int)Stream[Int]

此函数具有欺骗性地简单。数列的第一个元素显然是 a，数列的其余部分是从 b 开始的斐波那契数列，后面跟着 a + b。棘手的部分是在不导致无限递归的情况下计算此数列。如果函数使用 :: 而不是 #::，那么对函数的每次调用都会导致另一个调用，从而导致无限递归。但是，由于它使用 #::，因此右侧不会在被请求之前进行评估。以下是从两个 1 开始的斐波那契数列的前几个元素

scala> val fibs = fibFrom(1, 1).take(7)
fibs: scala.collection.immutable.Stream[Int] = Stream(1, ?)
scala> fibs.toList
res9: List[Int] = List(1, 1, 2, 3, 5, 8, 13)

向量

当处理它们的算法小心地仅处理它们的头部时，列表非常高效。访问、添加和删除列表的头部仅需要常量时间，而访问或修改列表中后面的元素则需要与列表深度成线性的时间。

Vector 是一种集合类型（在 Scala 2.8 中引入），它解决了随机访问列表的低效率问题。Vector 允许在“有效”常量时间内访问列表的任何元素。它比访问列表头部或读取数组元素的常量大，但它仍然是一个常量。因此，使用 vector 的算法不必小心只访问序列的头部。它们可以在任意位置访问和修改元素，因此编写起来会方便得多。

Vector 的构建和修改与任何其他序列一样。

scala> val vec = scala.collection.immutable.Vector.empty
vec: scala.collection.immutable.Vector[Nothing] = Vector()
scala> val vec2 = vec :+ 1 :+ 2
vec2: scala.collection.immutable.Vector[Int] = Vector(1, 2)
scala> val vec3 = 100 +: vec2
vec3: scala.collection.immutable.Vector[Int] = Vector(100, 1, 2)
scala> vec3(0)
res1: Int = 100

Vector 表示为具有高分支因子的树（树或图的分支因子是每个节点的子节点数）。每个树节点最多包含 32 个 vector 元素或最多包含 32 个其他树节点。最多包含 32 个元素的 vector 可以表示为单个节点。最多包含 32 * 32 = 1024 个元素的 vector 可以用单个间接表示。从树根到最终元素节点的两跳足以表示最多包含 2¹⁵ 个元素的 vector，三跳表示最多包含 2²⁰ 个元素的 vector，四跳表示最多包含 2²⁵ 个元素的 vector，五跳表示最多包含 2³⁰ 个元素的 vector。因此，对于所有合理大小的 vector，元素选择涉及最多 5 个原始数组选择。当我们写元素访问是“有效常量时间”时，这就是我们的意思。

Vector 是不可变的，所以你不能更改 vector 的元素，同时仍然保留一个新 vector。但是，使用 updated 方法，你可以创建一个新 vector，它与给定 vector 仅在一个元素上有所不同。

scala> val vec = Vector(1, 2, 3)
vec: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)
scala> vec updated (2, 4)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4)
scala> vec
res1: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)

如上所示的最后一行，对 updated 的调用对原始 vector vec 没有影响。与选择一样，函数式 vector 更新也是“有效常量时间”。可以通过复制包含该元素的节点以及指向该元素的每个节点（从树根开始）来更新 vector 中间的元素。这意味着函数式更新创建 1 到 5 个节点，每个节点最多包含 32 个元素或子树。这当然比可变数组中的就地更新要昂贵，但仍然比复制整个 vector 便宜得多。

因为向量在快速随机选择和快速随机函数更新之间取得了良好的平衡，所以它们目前是不可变索引序列的默认实现

scala> collection.immutable.IndexedSeq(1, 2, 3)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)

不可变栈

如果您需要一个后进先出序列，可以使用 Stack。使用 push 将元素推入栈中，使用 pop 弹出元素，使用 top 查看栈顶而不移除它。所有这些操作都是常量时间。

以下是针对栈执行的一些简单操作

scala> val stack = scala.collection.immutable.Stack.empty
stack: scala.collection.immutable.Stack[Nothing] = Stack()
scala> val hasOne = stack.push(1)
hasOne: scala.collection.immutable.Stack[Int] = Stack(1)
scala> stack
stack: scala.collection.immutable.Stack[Nothing] = Stack()
scala> hasOne.top
res20: Int = 1
scala> hasOne.pop
res19: scala.collection.immutable.Stack[Int] = Stack()

不可变栈在 Scala 程序中很少使用，因为它们的函数已被列表取代：不可变栈上的 push 等同于列表上的 ::，栈上的 pop 等同于列表上的 tail。

不可变队列

Queue 就像一个栈，只不过它是先进先出，而不是后进先出。

以下是创建空不可变队列的方法

scala> val empty = scala.collection.immutable.Queue[Int]()
empty: scala.collection.immutable.Queue[Int] = Queue()

您可以使用 enqueue 将元素附加到不可变队列

scala> val has1 = empty.enqueue(1)
has1: scala.collection.immutable.Queue[Int] = Queue(1)

要将多个元素附加到队列，请使用 enqueue，并将其集合作为其参数

scala> val has123 = has1.enqueue(List(2, 3))
has123: scala.collection.immutable.Queue[Int]
  = Queue(1, 2, 3)

要从队列头部删除元素，请使用 dequeue

scala> val (element, has23) = has123.dequeue
element: Int = 1
has23: scala.collection.immutable.Queue[Int] = Queue(2, 3)

请注意，dequeue 返回一个对，其中包含已删除的元素和队列的其余部分。

范围

Range 是一个有序的整数序列，它们之间的间隔相等。例如，“1、2、3”是一个范围，“5、8、11、14”也是一个范围。要在 Scala 中创建范围，请使用预定义的方法 to 和 by。

scala> 1 to 3
res2: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3)
scala> 5 to 14 by 3
res3: scala.collection.immutable.Range = Range(5, 8, 11, 14)

如果您想创建一个不包含其上限的范围，请使用便捷方法 until 代替 to

scala> 1 until 3
res2: scala.collection.immutable.Range = Range(1, 2)

范围以常量空间表示，因为它们可以用三个数字定义：它们的开始、结束和步长值。由于这种表示，大多数范围操作都非常快。

哈希尝试

哈希树是高效实现不可变集合和映射的标准方式。它们由类 immutable.HashMap 支持。它们的表示类似于向量，因为它们也是每个节点具有 32 个元素或 32 个子树的树。但是，现在基于哈希码选择这些键。例如，要在映射中查找给定的键，首先获取键的哈希码。然后，使用哈希码的最低 5 位选择第一个子树，然后使用接下来的 5 位，依此类推。一旦存储在节点中的所有元素的哈希码在已选择到此级别的位中彼此不同，选择就会停止。

哈希树在相当快的查找和相当高效的功能插入 (+) 和删除 (-) 之间取得了很好的平衡。这就是它们成为 Scala 的不可变映射和集合的默认实现的基础。事实上，Scala 对包含少于五个元素的不可变集合和映射进行了进一步优化。具有一个到四个元素的集合和映射存储为仅包含元素（或映射中的键/值对）作为字段的单个对象。空不可变集合和空不可变映射在每种情况下都是单个对象 - 无需为它们重复存储，因为空不可变集合或映射将始终保持为空。

红黑树

红黑树是一种平衡二叉树，其中一些节点被指定为“红色”，而其他节点被指定为“黑色”。与任何平衡二叉树一样，对它们的运算都可靠地以树的大小对数时间完成。

Scala 提供了使用红黑树的不可变集合和映射的实现。以 TreeSet 和 TreeMap 的名称访问它们。

scala> scala.collection.immutable.TreeSet.empty[Int]
res11: scala.collection.immutable.TreeSet[Int] = TreeSet()
scala> res11 + 1 + 3 + 3
res12: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 3)

红黑树是 Scala 中 SortedSet 的标准实现，因为它们提供了一个高效的迭代器，该迭代器以排序顺序返回所有元素。

不可变位集

一个 BitSet 将一组小整数表示为较大整数的位。例如，包含 3、2 和 0 的位集将表示为二进制中的整数 1101，即十进制中的 13。

在内部，位集使用 64 位 Long 的数组。数组中的第一个 Long 适用于整数 0 到 63，第二个适用于 64 到 127，依此类推。因此，只要集合中最大的整数小于几百个左右，位集就会非常紧凑。

对位集执行的操作非常快。包含性测试需要常量时间。向集合中添加一个项目所需的时间与位集数组中的 Long 数量成正比，而这个数量通常很小。以下是位集使用的一些简单示例

scala> val bits = scala.collection.immutable.BitSet.empty
bits: scala.collection.immutable.BitSet = BitSet()
scala> val moreBits = bits + 3 + 4 + 4
moreBits: scala.collection.immutable.BitSet = BitSet(3, 4)
scala> moreBits(3)
res26: Boolean = true
scala> moreBits(0)
res27: Boolean = false

列表映射

一个 ListMap 将映射表示为键值对的链表。通常，对列表映射执行的操作可能必须遍历整个列表。因此，对列表映射执行的操作所需的时间与映射的大小成线性关系。事实上，在 Scala 中几乎没有使用列表映射，因为标准不变映射几乎总是更快。对此唯一的可能例外是，如果映射出于某种原因以这样一种方式构建，即列表中的第一个元素比其他元素更频繁地被选中。

scala> val map = scala.collection.immutable.ListMap(1->"one", 2->"two")
map: scala.collection.immutable.ListMap[Int,java.lang.String] =
   Map(1 -> one, 2 -> two)
scala> map(2)
res30: String = "two"