4

Scala集合

@ def stdDev(a: Array[Double]): Double = {
    val mean = a.sum / a.length
    val squareErrors = a.map(x => x - mean).map(x => x * x)
    math.sqrt(squareErrors.sum / a.length)
  }
</> 4.1.scala

Snippet 4.1: 借助Scala集合操作，计算数组标准差

Scala标准库的核心是 collections：一个通用的容器和数据结构合集，被所有Scala程序共享。Scala集合让你很轻松地操作数组，链表，集 (set)，映射 (map)，以及其它数据结构，它提供了许多实现一个典型应用所需的数据结构。

在逐个讨论数据结构之前，本章先学习可以应用到所有集合类型的通用操作。

4.1 通用操作

Scala集合提供了许多通用操作，用以创建、查询、变换。我们在 Chapter 3: Scala基础 中已经展示了在 Array 上的操作，它们同样适用于本章涵盖的所有集合：不可变向量 (4.2.1)，不可变集 (4.2.3)，不可变映射 (4.2.4)等等。

4.1.1 构建器

@ val b = Array.newBuilder[Int]
b: mutable.ArrayBuilder[Int] = ArrayBuilder.ofInt

@ b += 1

@ b += 2

@ b.result()
res3: Array[Int] = Array(1, 2)
</> 4.2.scala

构建器允许你高效构建一个未知长度的集合，在构建结束时“冻结”它，得到你想要的集合。这非常有助于构建 Array 或者不可变集合，因为这些集合一旦创建就不能增加或者删除元素。

4.1.2 工厂方法

@ Array.fill(5)("hello") // Array with "hello" repeated 5 times
res4: Array[String] = Array("hello", "hello", "hello", "hello", "hello")

@ Array.tabulate(5)(n => s"hello $n") // Array with 5 items, each computed from its index
res5: Array[String] = Array("hello 0", "hello 1", "hello 2", "hello 3", "hello 4")

@ Array(1, 2, 3) ++ Array(4, 5, 6) // Concatenating two Arrays into a larger one
res6: Array[Int] = Array(1, 2, 3, 4, 5, 6)
</> 4.3.scala

工厂方法提供另一种实例化集合的方式：创建相同的元素，基于索引创建元素，或者合并多个小集合。在许多常见用例中比使用 构建器 (4.1.1) 方便。

4.1.3 变换

@ Array(1, 2, 3, 4, 5).map(i => i * 2) // Multiply every element by 2
res7: Array[Int] = Array(2, 4, 6, 8, 10)

@ Array(1, 2, 3, 4, 5).filter(i => i % 2 == 1) // Keep only elements not divisible by 2
res8: Array[Int] = Array(1, 3, 5)

@ Array(1, 2, 3, 4, 5).take(2) // Keep first two elements
res9: Array[Int] = Array(1, 2)

@ Array(1, 2, 3, 4, 5).drop(2) // Discard first two elements
res10: Array[Int] = Array(3, 4, 5)

@ Array(1, 2, 3, 4, 5).slice(1, 4) // Keep elements from index 1-4
res11: Array[Int] = Array(2, 3, 4)

@ Array(1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 7, 8).distinct // Removes all duplicates
res12: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8)
</> 4.4.scala

变换操作就是接收一个已存在集合，修改后创建出一个新集合的操作。注意变换操作会创建集合的副本，不会修改原集合。这意味着你如果仍然使用原数组，它的内容在变换后是不会有变化的：

@ val a = Array(1, 2, 3, 4, 5)
a: Array[Int] = Array(1, 2, 3, 4, 5)

@ val a2 = a.map(x => x + 10)
a2: Array[Int] = Array(11, 12, 13, 14, 15)

@ a(0) // Note that `a` is unchanged!
res15: Int = 1

@ a2(0)
res16: Int = 11
</> 4.5.scala

集合变换中的拷贝带来一些开销，但绝大多数时候不会造成严重问题。如果这部分代码成了瓶颈，拖慢了你的程序，你可以改造 .map/.filter 等变换操作，直接在原始 Array 上改动内容，或者借助 可变集合 (4.3) 的 原地操作 (4.3.4) 来优化性能。

4.1.4 查询

@ Array(1, 2, 3, 4, 5, 6, 7).find(i => i % 2 == 0 && i > 4)
res17: Option[Int] = Some(6)

@ Array(1, 2, 3, 4, 5, 6, 7).find(i => i % 2 == 0 && i > 10)
res18: Option[Int] = None

@ Array(1, 2, 3, 4, 5, 6, 7).exists(x => x > 1) // are any elements greater than 1?
res19: Boolean = true

@ Array(1, 2, 3, 4, 5, 6, 7).exists(_ < 0) // same as a.exists(x => x < 0)
res20: Boolean = false
</> 4.6.scala

查询操作允许你在集合中搜索元素，返回 Boolean 指示一个待匹配元素是否存在，或者返回 Option 来包含已找到的元素。这让你很方便地在集合中查找东西，而不用编写繁琐的for循环逐个检查元素。

4.1.5 聚合

4.1.5.1 mkString

把集合元素字符串化，用给定分隔符把它们结合成一个长字符串，还可以提供起始分隔符：

@ Array(1, 2, 3, 4, 5, 6, 7).mkString(",")
res21: String = "1,2,3,4,5,6,7"

@ Array(1, 2, 3, 4, 5, 6, 7).mkString("[", ",", "]")
res22: String = "[1,2,3,4,5,6,7]"
</> 4.7.scala

4.1.5.2 foldLeft

接收一个初始值和一个函数，用初始值逐一结合集合元素，产生最终结果：

@ Array(1, 2, 3, 4, 5, 6, 7).foldLeft(0)((x, y) => x + y) // sum of all elements
res23: Int = 28

@ Array(1, 2, 3, 4, 5, 6, 7).foldLeft(1)((x, y) => x * y) // product of all elements
res24: Int = 5040

@ Array(1, 2, 3, 4, 5, 6, 7).foldLeft(1)(_ * _) // same as above, shorthand syntax
res25: Int = 5040
</> 4.8.scala

通常，foldLeft 类似于for循环加一个累积变量，上面调用 foldLeft 实现的求和，可如下等价实现：

@ {
  var total = 0
  for (i <- Array(1, 2, 3, 4, 5, 6, 7)) total += i
  total
  }
total: Int = 28
</> 4.9.scala

4.1.5.3 groupBy

把你的集合按照key分成更小的集合组，并用 Map 存储：

@ val grouped = Array(1, 2, 3, 4, 5, 6, 7).groupBy(_ % 2)
grouped: Map[Int, Array[Int]] = Map(0 -> Array(2, 4, 6), 1 -> Array(1, 3, 5, 7))

@ grouped(0)
res26: Array[Int] = Array(2, 4, 6)

@ grouped(1)
res27: Array[Int] = Array(1, 3, 5, 7)
</> 4.10.scala

4.1.6 组合操作

一般你需要连接多个操作完成你的目标。举个例子，这里有一个计算数值数组标准差的函数：

@ def stdDev(a: Array[Double]): Double = {
    val mean = a.foldLeft(0.0)(_ + _) / a.length
    val squareErrors = a.map(_ - mean).map(x => x * x)
    math.sqrt(squareErrors.foldLeft(0.0)(_ + _) / a.length)
  }

@ stdDev(Array(1, 2, 3, 4, 5))
res29: Double = 1.4142135623730951

@ stdDev(Array(3, 3, 3))
res30: Double = 0.0
</> 4.11.scala

Scala集合提供了辅助方法 .sum 等价于 .foldLeft(0.0)(_ + _) ，因此上述代码可以这样简化：

@ def stdDev(a: Array[Double]): Double = {
    val mean = a.sum / a.length
    val squareErrors = a.map(_ - mean).map(x => x * x)
    math.sqrt(squareErrors.sum / a.length)
  }
</> 4.12.scala

另一个例子，使用 .exists，.map，和 .distinct 检查输入的数字网格是否是一个合法的数独网格：

@ def isValidSudoku(grid: Array[Array[Int]]): Boolean = {
    !Range(0, 9).exists{i =>
      val row = Range(0, 9).map(grid(i)(_))
      val col = Range(0, 9).map(grid(_)(i))
      val square = Range(0, 9).map(j => grid((i % 3) * 3 + j % 3)((i / 3) * 3 + j / 3))
      row.distinct.length != row.length ||
      col.distinct.length != col.length ||
      square.distinct.length != square.length
    }
  }
</> 4.13.scala

这个实现接收一个用 Array[Array[Int]] 代表的数独网格。i 从 0 到 9 自增，每次我们选择一行，一列，一个 3x3方块。然后对这些行、列、方块调用 .distinct 去除9个数字中的重复数字，然后比较去除前后它们的 .length 是否有变化。

我们可以用一些样例网格检验这个实现是否正确：

@ isValidSudoku(Array(
    Array(5, 3, 4,   6, 7, 8,   9, 1, 2),
    Array(6, 7, 2,   1, 9, 5,   3, 4, 8),
    Array(1, 9, 8,   3, 4, 2,   5, 6, 7),

    Array(8, 5, 9,   7, 6, 1,   4, 2, 3),
    Array(4, 2, 6,   8, 5, 3,   7, 9, 1),
    Array(7, 1, 3,   9, 2, 4,   8, 5, 6),

    Array(9, 6, 1,   5, 3, 7,   2, 8, 4),
    Array(2, 8, 7,   4, 1, 9,   6, 3, 5),
    Array(3, 4, 5,   2, 8, 6,   1, 7, 9)
  ))
res33: Boolean = true
</> 4.14.scala

@ isValidSudoku(Array(
    Array(5, 3, 4,   6, 7, 8,   9, 1, 2),
    Array(6, 7, 2,   1, 9, 5,   3, 4, 8),
    Array(1, 9, 8,   3, 4, 2,   5, 6, 7),

    Array(8, 5, 9,   7, 6, 1,   4, 2, 3),
    Array(4, 2, 6,   8, 5, 3,   7, 9, 1),
    Array(7, 1, 3,   9, 2, 4,   8, 5, 6),

    Array(9, 6, 1,   5, 3, 7,   2, 8, 4),
    Array(2, 8, 7,   4, 1, 9,   6, 3, 5),
    Array(3, 4, 5,   2, 8, 6,   1, 7, 8)
  )) // bottom right cell should be 9
res34: Boolean = false
</> 4.15.scala

用这种方式连接集合变换操作总会有些开销，但是绝大多数用例下开销是值得的，因为这些变换操作带来了方便和简单。如果集合变换操作成为了瓶颈，你可以用 视图 (4.1.8)，原地操作 (4.3.4)，或者自己循环原始 Array，来优化代码。

4.1.7 转换器

你可以使用 .to 方法在 Array 和其他集合之间，比如 Vector (4.2.1) 和 Set (4.2.3)，进行相互转换：

@ Array(1, 2, 3).to(Vector)
res35: Vector[Int] = Vector(1, 2, 3)

@ Vector(1, 2, 3).to(Array)
res36: Array[Int] = Array(1, 2, 3)

@ Array(1, 1, 2, 2, 3, 4).to(Set)
res37: Set[Int] = Set(1, 2, 3, 4)
</> 4.16.scala

4.1.8 视图

当你在一个集合上连接了多个变换操作，我们不断创建许多中间集合，然后立即扔掉它们。如下述例子：

@ val myArray = Array(1, 2, 3, 4, 5, 6, 7, 8, 9)

@ val myNewArray = myArray.map(x => x + 1).filter(x => x % 2 == 0).slice(1, 3)
myNewArray: Array[Int] = Array(4, 6)
</> 4.17.scala

.map .filter .slice 连接操作遍历了集合三次，创建了三个新集合，但是只有最后一个集合最终被存储到 myNewArray，其它的被丢弃。

中间集合的创建和遍历浪费了资源。为了防止一连串集合变换操作成为瓶颈，你可以使用方法 .view 搭配 .to，一口气“熔断”这些操作：

@ val myNewArray = myArray.view.map(_ + 1).filter(_ % 2 == 0).slice(1, 3).to(Array)
myNewArray: Array[Int] = Array(4, 6)
</> 4.18.scala

在 map/filter/slice 变换操作前使用 .view，推迟了集合的遍历和创建，当我们调用 .to 把它转换回具体集合类型时，遍历和创建才真正发生：

这让我们只用一次遍历，创建一个单一输出集合就执行了 map/filter/slice 变换链条。从而节省了不必要的处理和内存分配开销。

4.2 不可变集合

Array 是低级别的原始类型，绝大多数Scala应用搭建在可变、不可变集合之上：Vector、List、Set、以及 Map。这其中，不可变集合使用最为广泛。

不可变集合杜绝了由于意料之外的修改而造成的类bug，在多线程场景中极其有用，你可以在线程间安全地传递不可变集合，而不用担心线程安全问题。绝大多数不可变集合使用 结构共享 (4.2.2) 使得创建并更新副本很廉价，推荐你在除了性能要求极高的关键代码之外的任何场景中使用它们。

4.2.1 不可变向量

Vector 是大小固定的，不可变线性序列。它是良好的、通用目的序列数据结构，绝大多数操作提供高效的 O(log n) 性能。

@ val v = Vector(1, 2, 3, 4, 5)
v: Vector[Int] = Vector(1, 2, 3, 4, 5)

@ v(0)
res42: Int = 1

@ val v2 = v.updated(2, 10)
v2: Vector[Int] = Vector(1, 2, 10, 4, 5)

@ v2
res44: Vector[Int] = Vector(1, 2, 10, 4, 5)

@ v // note that `v` did not change!
res45: Vector[Int] = Vector(1, 2, 3, 4, 5)
</> 4.19.scala

@ val v = Vector[Int]()
v: Vector[Int] = Vector()

@ val v1 = v :+ 1
v1: Vector[Int] = Vector(1)

@ val v2 = 4 +: v1
v2: Vector[Int] = Vector(4, 1)

@ val v3 = v2.tail
v3: Vector[Int] = Vector(1)
</> 4.20.scala

不像 Array 中 a(...) = ... 会原地改动元素，Vector 的 .updated 方法返回修改后的新 Vector，旧 Vector 保持不变。得益于 结构共享 (4.2.2)，这是一个较高效的 O(log n) 操作。同样的，使用 :+ 和 +: 在某端添加元素，或者使用 .tail 获取除首元素外的子序列，通通会返回新 Vector，效率也是 O(log n)：

Vector 也支持 Array 和其它集合的 通用操作 (4.1)：构建器 (4.1.1)，工厂方法 (4.1.2)，变换 (4.1.3) 等等。

通常，当你知道一个序列不会改变，而且需要灵活处理时，Vector 用起来就很顺手。它的树结构让绝大多数操作比较高效，尽管它不可能像 Array 原地更新，或者像 不可变链表 (4.2.5) 在头部添加或者删除元素时那样快速。

4.2.2 结构共享

Vector 通过重用部分树结构实现 O(log n) 的“复制-更新”操作。这避免了复制整个树，获得的新 Vector 共享了旧树的部分内容，然后只做少量修改。

考虑一个大 Vector，v1：

@ val v1 = Vector(1, 2, 0, 9,  7, 2, 9, 6,  ...,  3, 2, 5, 5,  4, 8, 4, 6)

这里展示了树结构的内存，宽度和深度依赖于 Vector 的大小：

这个例子做了简化 - Scala中每个树节点有32个元素，而非上述的4个 - 但是它足够向我们展示 Vector 数据结构是如何工作的。

让我们看看执行更新会发生什么，例如，更新上面 Vector 第5个元素的值：

@ val v2 = v1.updated(4, 8)

@ v2
res50: Vector[Int] = Vector(1, 2, 0, 9, 8, 2, 9, 6, ..., 3, 2, 5, 5, 4, 8, 4, 6)
</> 4.21.scala

只需创建我们更新节点所在路径的节点副本，并重用其它节点：

这个例子中，Vector 有9个节点，只需要复制3个节点，需要复制的节点个数和树高成正比，同时其它节点可被重用：这种结构共享使得 Vector 更新副本的创建只用 O(log n) 时间完成。这比可变的 Array 或者其它数据结构用 O(n) 时间完整复制一遍集合要快速得多。

然而，更新 Vector 总是涉及一定量的复制，不会如可变数据结构原地更新来得快。在某些性能很重要的，并且需要频繁更新集合的场景，你可以考虑可变的 ArrayDeque (4.3.1)，它具有 O(1) 的update/append/prepend操作，或者如果你提前知道集合大小，你可以使用原始 Array。

不可变集 (4.2.3) 和 不可变映射 (4.2.4) 也是用类似的树形结构实现的。

4.2.3 不可变集

Scala不可变集 (Set) 是元素无重复的无序集合。提供高效的 O(log n) .contains 方法。Set 可以用 + 添加元素，- 删除元素，或者 ++ 合并两个集合，其中重复的元素会被丢弃：

@ val s = Set(1, 2, 3)
s: Set[Int] = Set(1, 2, 3)

@ s.contains(2)
res51: Boolean = true

@ s.contains(4)
res52: Boolean = false
</> 4.22.scala

@ Set(1, 2, 3) + 4 + 5
res53: Set[Int] = HashSet(5, 1, 2, 3, 4)

@ Set(1, 2, 3) - 2
res54: Set[Int] = Set(1, 3)

@ Set(1, 2, 3) ++ Set(2, 3, 4)
res55: Set[Int] = Set(1, 2, 3, 4)
</> 4.23.scala

当你想要确保集合不包含任何重复元素时，Set 中元素的唯一性就会很有用。

你可以使用for循环迭代 Set，但是元素顺序是不确定的，不应该被依赖的：

@ for (i <- Set(1, 2, 3, 4, 5)) println(i)
5
1
2
3
4
</> 4.24.scala

不可变 Set 的绝大多数操作时间复杂度是 O(log n)，其中 n 是 Set 元素个数。这在绝大多数场景已经足够快了，当无法满足需要时，你可以转而使用 可变集 (4.3.2)，以获得更好性能。Set 同样支持所有集合的通用标准操作。

4.2.4 不可变映射

不可变映射 (Map) 是关于key-value对的无序集合，可以使用key高效地查询：

@ val m = Map("one" -> 1, "two" -> 2, "three" -> 3)
m: Map[String, Int] = Map("one" -> 1, "two" -> 2, "three" -> 3)

@ m.contains("two")
res58: Boolean = true

@ m("two")
res59: Int = 2
</> 4.25.scala

如果你不清楚这个映射是否包含某个key，你也可以使用 .get。若key存在则返回 Some(v)，不存在则返回 None：

@ m.get("one")
res60: Option[Int] = Some(1)

@ m.get("four")
res61: Option[Int] = None
</> 4.26.scala

Map 支持其它集合一样的通用操作，另外它被视作元组的集合，每个元组代表一对 key-value。.to 方法要求原集合是一个元组的集合，+ 把元组当做key-value对添加到 Map，元组也可以用 for 循环遍历：

@ Vector(("one", 1), ("two", 2), ("three", 3)).to(Map)
res62: Map[String, Int] = Map("one" -> 1, "two" -> 2, "three" -> 3)

@ Map[String, Int]() + ("one" -> 1) + ("three" -> 3)
res63: Map[String, Int] = Map("one" -> 1, "three" -> 3)

@ for ((k, v) <- m) println(k + " " + v)
one 1
two 2
three 3
</> 4.27.scala

同 Set 一样，迭代 Map 时元素的顺序是不确定的，不应该被依赖的，不可变 Map 绝大多数操作的时间复杂度是 O(log n)，其中n是 Map 包含的元素个数。

4.2.5 不可变链表

@ val myList = List(1, 2, 3, 4, 5)
myList: List[Int] = List(1, 2, 3, 4, 5)

@ myList.head
res66: Int = 1

@ val myTail = myList.tail
myTail: List[Int] = List(2, 3, 4, 5)

@ val myOtherList = 0 :: myList
myOtherList: List[Int] = List(0, 1, 2, 3, 4, 5)

@ val myThirdList = -1 :: myList
myThirdList: List[Int] = List(-1, 1, 2, 3, 4, 5)
</> 4.28.scala

Scala不可变链表 (List) 是单链表数据结构。链表中每个节点除了值，还有指向下一个节点的指针，最后一个节点是 Nil。List 有一个 快速的 O(1) 方法 .head，用来查找链表的第一项。一个快速的 O(1) 方法 .tail，用来返回不带第一项的子链表。还有一个快速的 O(1) 操作符 ::，用来得到在原链表头部添加一个元素后的新链表。

.tail 和 :: 高效的原因是它们共享了原 List 的许多节点：.tail 直接返回单链结构的第二个节点的引用，:: 在链表前面直接添加一个节点。实际上多个链表间可以共享节点，这意味着上述例子中 myList，myTail，myOtherList，以及 myThirdList 几乎是同样的数据结构：

如果你有大量在一侧具有相同元素的集合，比如文件系统路径，它们有相同的前缀，这将显著节省内存。不必用 O(n) 时间创建一个 Array 的更新副本，或者用 O(log n) 时间创建一个 Vector，只需要一个快速的 O(1) 操作在 List 头部添加一个元素即可

List 的缺点是基于索引查询 myList(i) 是一个很慢的 O(n) 操作，因为你需要从头遍历链表寻找你想要的元素。在链表尾部追加或者删除元素也是很慢的O(n)复杂度，因为它需要复制整个链表。如果你想要快速的基于索引查询，或者快速的在尾部追加、删除，你应该考虑使用 Vectors (4.2.1) 或者 可变的 ArrayDeque (4.3.1)。

4.3 可变集合

当使用原地操作时，可变集合通常比它们的不可变等价物效率更高。然而可变性是有代价的：在程序不同部分共享它们时要更加小心。当一个可变集合被意外更新时非常容易出bug，一旦发生意味着迫使你在一个大型代码库中找出意外执行了更新的代码行。

当需要解决性能瓶颈时，一个常用的做法是仅在局部函数中使用可变集合，或者把它设为类的私有访问属性。然后在性能不是主要关注点的其他地方都使用不可变集合。这既享受到可变集合带给你的高性能，又享受到不可变集合在你应用逻辑的其他地方带来的安全性。

4.3.1 ArrayDeque

ArrayDeque 是一个通用目的的可变线性集合，提供高效的 O(1) 索引查询，O(1) 索引更新，O(1) 双端插入或删除：

@ val myArrayDeque = collection.mutable.ArrayDeque(1, 2, 3, 4, 5)
myArrayDeque: collection.mutable.ArrayDeque[Int] = ArrayDeque(1, 2, 3, 4, 5)

@ myArrayDeque.removeHead()
res71: Int = 1

@ myArrayDeque.append(6)
res72: collection.mutable.ArrayDeque[Int] = ArrayDeque(2, 3, 4, 5, 6)

@ myArrayDeque.removeHead()
res73: Int = 2

@ myArrayDeque
res74: collection.mutable.ArrayDeque[Int] = ArrayDeque(3, 4, 5, 6)
</> 4.29.scala

ArrayDeque 是一个循环缓冲，缓冲区用指针指明集合逻辑上的开始和结束。上述操作的可视化过程如下：

ArrayDeque尽可能复用底层的 Array，当任意一端元素被添加或删除，只需移动 start 和 end 指针。当且仅当元素总个数超出容量时，底层 Array 重新被分配，并且容量大小增加一个固定倍数，使得重分配操作的平摊开销很小。

于是 ArrayDeque 比等价的 Vector 操作快许多，因为 Vector 不得不为每个操作分配新的树节点。

ArrayDeque 支持标准化 通用操作 (4.1)。它可以扮演很多角色：

• 一个可以增长的 Array：使用 Array.newBuilder 构建数组的过程中，既不允许基于索引查询或修改，也不允许添加元素。而在 ArrayDeque 中，两者都是被允许的

• 一个更快速的，可变 Vector 的备选项：如果你发现无论从哪头进行添加、删除元素，使用 :+/+: 或 .tail/.init 成为了性能瓶颈。请记住在 ArrayDeque 头尾添加元素比等价的 Vector 操作要快很多

• 一个先入先出的队列：通过 .append 入队，.removeHead 出队

• 一个先入后出的栈：通过 .append 入栈，.removeLast 出栈

如果你想“冻结”一个可变的 ArrayDeque，得到一个不可变的 Vector，使用 .to(Vector)：

@ myArrayDeque.to(Vector)
res75: Vector[Int] = Vector(3, 4, 5, 6)
</> 4.30.scala

注意这将创建整个集合的副本。

ArrayDeque 实现了抽象接口 collection.mutable.Buffer，因此也可以使用语法 collection.mutable.Buffer(...) 来创建它。

4.3.2 可变集

Scala标准库提供了可变 Set，它是不可变 Set 的对应物。可变集提供了高效的 .contains 检查 （O(1)），但是不再用 + 和 - 来创建 Set 的新备份，而是使用 .add 和 .remove 来添加和删除元素：

@ val s = collection.mutable.Set(1, 2, 3)
s: mutable.Set[Int] = HashSet(1, 2, 3)

@ s.contains(2)
res77: Boolean = true

@ s.contains(4)
res78: Boolean = false
</> 4.31.scala

@ s.add(4)

@ s.remove(1)

@ s
res81: mutable.Set[Int] = HashSet(2, 3, 4)
</> 4.32.scala

你可以使用 .to(Set) 把一个可变 Set “冻结”为一个不可变 Set，你不再能使用 .add 或 .remove 改动新集合。你也可以再使用同样方式转换回可变 Set，但注意每次转换会创建整个集合的副本。

4.3.3 可变映射

可变 Map 类似不可变 Map，但允许你通过添加、删除key-value对，来改动 Map：

@ val m = collection.mutable.Map("one" -> 1, "two" -> 2, "three" -> 3)
m: mutable.Map[String, Int] = HashMap("two" -> 2, "three" -> 3, "one" -> 1)

@ m.remove("two")
res83: Option[Int] = Some(2)

@ m("five") = 5

@ m
res85: mutable.Map[String, Int] = HashMap("five" -> 5, "three" -> 3, "one" -> 1)
</> 4.33.scala

可变 Map 有一个方便的函数 getOrElseUpdate，允许你通过key查询value，如果不存在则估值你给定的value并插入：

@ val m = collection.mutable.Map("one" -> 1, "two" -> 2, "three" -> 3)

@ m.getOrElseUpdate("three", -1) // already present, returns existing value
res87: Int = 3

@ m // `m` is unchanged
res88: mutable.Map[String, Int] = HashMap("two" -> 2, "three" -> 3, "one" -> 1)

@ m.getOrElseUpdate("four", -1) // not present, stores new value in map and returns it
res89: Int = -1

@ m // `m` now contains "four" -> -1
res90: mutable.Map[String, Int] = HashMap(
  "two" -> 2,
  "three" -> 3,
  "four" -> -1,
  "one" -> 1
)
</> 4.34.scala

.getOrElseUpdate 可以方便地把可变 Map 当做缓存：.getOrElseUpdate 的第二个参数是延迟估值的传名参数，仅当 Map 中找不到key时，才进行估值。这提供了一种通用工作流：检查key是否存在，是则返回其值，否则估值并插入，然后返回该值。我们会在 Chapter 5: Scala特性 介绍更多关于传名参数的细节。

可变 Map 用哈希表实现，m(...) 查询和 m(...)= ... 更新操作都是 O(1) 复杂度。

4.3.4 原地操作

所有的可变集合和 Array 的许多通用操作有对应的“原地操作“版本。这些原地操作让你避免创建集合副本：

@ val a = collection.mutable.ArrayDeque(1, 2, 3, 4)
a: mutable.ArrayDeque[Int] = ArrayDeque(1, 2, 3, 4)

@ a.mapInPlace(_ + 1)
res92: mutable.ArrayDeque[Int] = ArrayDeque(2, 3, 4, 5)

@ a.filterInPlace(_ % 2 == 0)
res93: mutable.ArrayDeque[Int] = ArrayDeque(2, 4)

@ a // `a` was modified in place
res94: mutable.ArrayDeque[Int] = ArrayDeque(2, 4)
</> 4.35.scala

除了上述已展现的，还有 dropInPlace，sliceInPlace，sortInPlace等等。使用原地操作而非普通的变换操作，避免了分配变换后新集合的开销，能够在性能至上的场景发挥作用。

4.4 公共接口

在许多案例中，代码并不关心正被操作的集合是什么具体类型。比如，按序迭代的代码只需要接收一个 Seq[T] 作为输入：

@ def iterateOverSomething[T](items: Seq[T]) = {
    for (i <- items) println(i)
  }

@ iterateOverSomething(Vector(1, 2, 3))
1
2
3

@ iterateOverSomething(List(("one", 1), ("two", 2), ("three", 3)))
(one,1)
(two,2)
(three,3)
</> 4.36.scala

提供高效索引查询的代码不关心被操作集合是 Array 还是 Vector，只要不是 List 就行。在这里，你的代码可以接收一个 IndexedSeq[T] 作为输入：

@ def getIndexTwoAndFour[T](items: IndexedSeq[T]) = (items(2), items(4))

@ getIndexTwoAndFour(Vector(1, 2, 3, 4, 5))
res99: (Int, Int) = (3, 5)

@ getIndexTwoAndFour(Array(2, 4, 6, 8, 10))
res100: (Int, Int) = (6, 10)
</> 4.37.scala

目前为止，我们看到的数据结构层次如下：

根据代码输入，你可以从层次图里选择相关的类型：Iterable，collection.Seq，Seq，IndexedSeq 等等。通常，绝大多数代码默认使用不可变的 Seq，Set，以及 Map。可变集合放置在 collection.mutable 包下，仅当必要时才会使用，最好把它们保持在局部函数或者设置为类的私有属性。collection.{Seq,Set,Map} 是可变和不可变集合的公共接口。

4.5 总结

本章我们浏览了Scala标准库的基本集合：Array，不可变的 Vector/Set/Map/List，以及可变的 ArrayDeque/Set/Map。我们知道了如何创建集合，查询集合，从一种集合转换到另一种集合，以及编写适用于多种集合类型的函数。

本章为你打下驾驭Scala集合库的基础，这些库广泛应用在每一个Scala程序。接下来，我们会接触到更多属于Scala语言独一无二的特性，完成你的Scala入门学习。

@ isValidSudoku(Array(
    Array(3, 1, 6,   5, 7, 8,   4, 9, 2),
    Array(5, 2, 9,   1, 3, 4,   7, 6, 8),
    Array(4, 8, 7,   6, 2, 9,   5, 3, 1),

    Array(2, 6, 3,   0, 1, 0,   0, 8, 0),
    Array(9, 7, 4,   8, 6, 3,   0, 0, 5),
    Array(8, 5, 1,   0, 9, 0,   6, 0, 0),

    Array(1, 3, 0,   0, 0, 0,   2, 5, 0),
    Array(0, 0, 0,   0, 0, 0,   0, 7, 4),
    Array(0, 0, 5,   2, 0, 6,   3, 0, 0)
  ))
res101: Boolean = true
</> 4.38.scala

@ isValidSudoku(Array(
    Array(3, 1, 6,   5, 7, 8,   4, 9, 3),
    Array(5, 2, 9,   1, 3, 4,   7, 6, 8),
    Array(4, 8, 7,   6, 2, 9,   5, 3, 1),

    Array(2, 6, 3,   0, 1, 0,   0, 8, 0),
    Array(9, 7, 4,   8, 6, 3,   0, 0, 5),
    Array(8, 5, 1,   0, 9, 0,   6, 0, 0),

    Array(1, 3, 0,   0, 0, 0,   2, 5, 0),
    Array(0, 0, 0,   0, 0, 0,   0, 7, 4),
    Array(0, 0, 5,   2, 0, 6,   3, 0, 0)
  )) // top right cell should be 2
res102: Boolean = false
</> 4.39.scala

@ renderSudoku(Array(
    Array(3, 1, 6,   5, 7, 8,   4, 9, 2),
    Array(5, 2, 9,   1, 3, 4,   7, 6, 8),
    Array(4, 8, 7,   6, 2, 9,   5, 3, 1),

    Array(2, 6, 3,   0, 1, 0,   0, 8, 0),
    Array(9, 7, 4,   8, 6, 3,   0, 0, 5),
    Array(8, 5, 1,   0, 9, 0,   6, 0, 0),

    Array(1, 3, 0,   0, 0, 0,   2, 5, 0),
    Array(0, 0, 0,   0, 0, 0,   0, 7, 4),
    Array(0, 0, 5,   2, 0, 6,   3, 0, 0)
  ))
</> 4.40.scala

res103: String = """
+-------+-------+-------+
| 3 1 6 | 5 7 8 | 4 9 2 |
| 5 2 9 | 1 3 4 | 7 6 8 |
| 4 8 7 | 6 2 9 | 5 3 1 |
+-------+-------+-------+
| 2 6 3 |   1   |   8   |
| 9 7 4 | 8 6 3 |     5 |
| 8 5 1 |   9   | 6     |
+-------+-------+-------+
| 1 3   |       | 2 5   |
|       |       |   7 4 |
|     5 | 2   6 | 3     |
+-------+-------+-------+
"""
</> 4.41.output-scala

@ Array(3, 1, 6,   5, 7, 8,   4, 9, 2).grouped(3).toArray
res104: Array[Array[Int]] = Array(Array(3, 1, 6), Array(5, 7, 8), Array(4, 9, 2))
</> 4.42.scala