Scala 为你提供了许多具体不可变集合类供你选择。它们在实现的特性（映射、集合、序列）方面有所不同，它们是否可以是无限的，以及各种操作的速度。以下是 Scala 中使用的一些最常见的不可变集合类型。
列表
列表是一个有限的不可变序列。它们提供对第一个元素以及列表其余部分的恒定时间访问，并且它们有一个恒定时间的 cons 操作，用于将新元素添加到列表的前面。许多其他操作需要线性时间。
惰性列表
一个 LazyList 就像一个列表，只不过它的元素是惰性计算的。因此，一个惰性列表可以无限长。只有请求的元素才会被计算。否则，惰性列表具有与列表相同的性能特征。
列表是用 :: 运算符构造的，而惰性列表是用类似的 #:: 构造的。下面是一个包含整数 1、2 和 3 的惰性列表的简单示例
scala> val lazyList = 1 #:: 2 #:: 3 #:: LazyList.empty
lazyList: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)
此惰性列表的头部是 1，尾部是 2 和 3。但是，这里没有打印任何元素，因为列表尚未计算！惰性列表被指定为惰性计算，而惰性列表的 toString 方法小心地不强制进行任何额外的求值。
下面是一个更复杂的示例。它计算一个惰性列表，其中包含从给定的两个数字开始的斐波那契数列。斐波那契数列是一个数列，其中每个元素都是数列中前两个元素的和。
scala> def fibFrom(a: Int, b: Int): LazyList[Int] = a #:: fibFrom(b, a + b)
fibFrom: (a: Int,b: Int)LazyList[Int]
此函数具有欺骗性地简单。数列的第一个元素显然是 a，而数列的其余部分是从 b 开始的斐波那契数列，后面跟着 a + b。棘手的部分是在不导致无限递归的情况下计算此序列。如果函数使用 :: 而不是 #::，那么对函数的每次调用都会导致另一个调用，从而导致无限递归。然而，由于它使用 #::，因此右侧不会在被请求之前进行求值。以下是从两个 1 开始的斐波那契数列的前几个元素
scala> val fibs = fibFrom(1, 1).take(7)
fibs: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)
scala> fibs.toList
res9: List[Int] = List(1, 1, 2, 3, 5, 8, 13)
不可变 ArraySeq
当处理它们的算法仅处理它们的头部时，列表非常高效。访问、添加和删除列表的头部仅需恒定时间，而访问或修改列表中后面的元素则需要线性时间，与列表的深度成正比。
ArraySeq 是一种集合类型（在 Scala 2.13 中引入），它解决了列表随机访问效率低的问题。ArraySeq 允许在恒定时间内访问集合的任何元素。因此，使用 ArraySeq 的算法不必谨慎地仅访问集合的头部。它们可以访问任意位置的元素，因此编写起来会方便得多。
ArraySeq 的构建和更新与任何其他序列一样。
scala> val arr = scala.collection.immutable.ArraySeq(1, 2, 3)
arr: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 3)
scala> val arr2 = arr :+ 4
arr2: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 3, 4)
scala> arr2(0)
res22: Int = 1
ArraySeq 是不可变的，因此你不能就地更改元素。但是，updated、appended 和 prepended 操作会创建新的 ArraySeq，它们与给定的 ArraySeq 仅在一个元素上有所不同
scala> arr.updated(2, 4)
res26: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 4)
scala> arr
res27: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 3)
如上所示的最后一行，对 updated 的调用对原始 ArraySeq arr 没有影响。
ArraySeq 将其元素存储在私有 Array 中。这是一个紧凑的表示形式，支持快速索引访问，但更新或添加一个元素是线性的，因为它需要创建另一个数组并复制所有原始数组的元素。
向量
我们在前几节中看到，List 和 ArraySeq 在某些特定用例中是高效的数据结构，但它们在其他用例中效率也低：例如，对 List 来说，前置一个元素是恒定的，但对 ArraySeq 来说是线性的，反之，对 ArraySeq 来说，索引访问是恒定的，但对 List 来说是线性的。
Vector 是一种集合类型，它为其所有操作提供了良好的性能。向量允许在“有效”恒定时间内访问序列的任何元素。它比访问列表的头部或读取 ArraySeq 的元素的常量更大，但它仍然是一个常量。因此，使用向量的算法不必谨慎地仅访问序列的头部。它们可以访问和修改任意位置的元素，因此编写起来会方便得多。
向量的构建和修改与任何其他序列一样。
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
向量表示为具有高分支因子的树（树或图的分支因子是每个节点的子节点数）。有关如何实现此操作的详细信息在 Scala 2.13.2 中已更改，但基本思想保持不变，如下所示。
每个树节点最多包含向量的 32 个元素，或最多包含 32 个其他树节点。最多包含 32 个元素的向量可以用单个节点表示。最多包含 32 * 32 = 1024 个元素的向量可以用单个间接表示。从树的根到最终元素节点的两跳足以表示最多包含 215 个元素的向量，三跳表示最多包含 220 个元素的向量，四跳表示最多包含 225 个元素的向量，五跳表示最多包含 230 个元素的向量。因此，对于所有合理大小的向量，元素选择涉及最多 5 个基本数组选择。当我们写元素访问“有效地是常量时间”时，这就是我们的意思。
与选择类似，函数向量更新也是“有效地是常量时间”。可以通过复制包含该元素的节点以及指向该元素的每个节点（从树的根开始）来更新向量中间的元素。这意味着函数更新会在一个到五个节点之间创建每个节点最多包含 32 个元素或子树。这当然比可变数组中的就地更新要昂贵，但仍然比复制整个向量便宜得多。
由于向量在快速随机选择和快速随机函数更新之间取得了良好的平衡，因此它们目前是不可变索引序列的默认实现
scala> collection.immutable.IndexedSeq(1, 2, 3)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)
不可变队列
队列是先进先出的序列。您可以使用 enqueue 将元素排入队列，并使用 dequeue 将元素出列。这些操作是常量时间。
以下是如何创建空的不可变队列
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)
要将多个元素附加到队列，请使用 enqueueAll 调用，并以集合作为其参数
scala> val has123 = has1.enqueueAll(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 返回一个对，其中包含已删除的元素和队列的其余部分。
范围
一个 范围 是一个以相等间隔排列的整数的有序序列。例如，“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)
范围以常量空间表示，因为它们可以用三个数字来定义：它们的开始、结束和步长值。由于这种表示，对范围的大多数操作都非常快。
压缩哈希数组映射前缀树
哈希尝试是有效实现不可变集合和映射的标准方式。 压缩哈希数组映射前缀树 是针对 JVM 上的哈希尝试的一种设计，它改进了局部性并确保树保持规范且紧凑的表示形式。它们受类 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
矢量映射
一个 VectorMap 使用键的 Vector 和 HashMap 来表示一个映射。它提供了一个迭代器，以插入顺序返回所有条目。
scala> val vm = scala.collection.immutable.VectorMap.empty[Int, String]
vm: scala.collection.immutable.VectorMap[Int,String] =
VectorMap()
scala> val vm1 = vm + (1 -> "one")
vm1: scala.collection.immutable.VectorMap[Int,String] =
VectorMap(1 -> one)
scala> val vm2 = vm1 + (2 -> "two")
vm2: scala.collection.immutable.VectorMap[Int,String] =
VectorMap(1 -> one, 2 -> two)
scala> vm2 == Map(2 -> "two", 1 -> "one")
res29: Boolean = true
第一行显示 VectorMap 的内容保留了插入顺序，最后一行显示 VectorMap 可以与其他 Map 进行比较，并且此比较不考虑元素的顺序。
列表映射
一个 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"