4.2 不可变集合族
4.2 不可变集合族
List、Vector、Range、Set、Map 的不可变实现是 Scala 的默认武器。本节逐个过它们的结构与手感，重点是每个结构"擅长的那一件事"。
List：递归的形状
val xs = 1 :: 2 :: 3 :: Nil // 等价 List(1,2,3) xs.head // 1 xs.tail // List(2, 3) 1 :: xs // 新列表，O(1)，与 xs 共享尾部
List 是单向链表，: : 在头部构造。结合 3.1 的结构共享：1 :: xs 不复制任何元素。处理它的自然方式是模式匹配递归：
def sum(xs: List[Int]): Int = xs match case Nil => 0 case h :: t => h + sum(t)
追加用 :+ 是 O(n)，频繁尾部追加是错用——那该用 Vector 或 ListBuffer。
Vector：均衡的默认
val v = Vector(1,2,3) v.updated(1, 99) // 新 Vector，原样保留 v :+ 4 // 尾部追加，近似 O(1)
Vector 是 32 叉的树结构，更新与追加都产生结构共享的新实例，随机访问近似 O(1)。没有明确偏好时选它，各项都没有短板。
Range 与视图：按需生成
(1 to 10 by 2) // Range，不占内存 (1 to 1000000).view // 惰性视图，变换不立即求值
view 把 map/filter 变成惰性流水线，链式多步变换大集合时可避免中间集合。要结果时 toList/sum 触发一次性求值。小数据上用 view 反而慢——惰性有簿记成本。
Set 与 Map
val tags = Set("fp", "jvm", "fp") // Set(fp, jvm) 自动去重 val price = Map("a" -> 1, "b" -> 2) tags.contains("fp") // O(1) price("b") // 2，键缺失抛异常！ price.get("zzz") // None —— 安全取法 price.getOrElse("zzz", 0) // 0
⚠️
map(key)在键缺失时直接抛异常。除了确定键必在（比如刚 put 过），一律用 get 返回 Option、getOrElse 给默认值——这是 Option 语境最日常的应用。
Map 的遍历产出键值元组，配合解构：
for (k, v) <- price do println(s"$k -> ${v * 2}")
两个常用变换：
price.map((k, v) => (k.toUpperCase, v * 2)) // 变键值 List("a","b","ab","ba").groupBy(s => s.length) // Map(1 -> List(a,b), 2 -> List(ab,ba))
不可变三剑客的更新方式对比
图 4-2 不可变集合操作复杂度对比矩阵
集合操作链的代价推演
同一段逻辑用不同操作链写，复杂度可以差一个数量级。任务：统计一段文本中长度大于 3 的词频前两名。对照两种写法：
val text = "the quick brown fox jumps over the lazy dog the end" // 写法一：多次中间集合，每个 < 都要重新遍历 val words = text.split(" ").toList val filtered = words.filter(_.length > 3) val grouped = filtered.groupBy(identity) val counted = grouped.view.mapValues(_.size).toList counted.sortBy(-_._2).take(2) // List((the,3), (quick,1)) // 写法二：groupBy 后直接接 sortBy，语义相同，中间结构更少 words.filter(_.length > 3).groupBy(identity) .view.mapValues(_.size).toList .sortBy(-_._2).take(2)
推演要点：groupBy 之后每个词已只出现一次桶内，mapValues 前挂 view 可避免整表复制；sortBy(-_._2) 的负号是升序键做降序的惯技。结果一致，但写法二把中间落地从四次压到两次。集合操作的调优从来不是玄学，就是数中间集合的次数。
不可变 Map 与 Set 的更新语义
val m = Map("a" -> 1) val m2 = m + ("b" -> 2) // 新 Map，m 不变 val m3 = m2 - "a" // 减键同样返回新值 val s = Set(1, 2, 3) val s2 = s ++ Set(3, 4) // 并集：Set(1, 2, 3, 4) val s3 = s & Set(2, 8) // 交集：Set(2)
加减号在不可变世界里读作"得到一个新集合"，这个心智模型一旦建立，并发共享集合的安全问题（6.3 节）就预先消解了一半。
List 与 Vector 的拆装对比实验
val l = List(1, 2, 3) val v = Vector(1, 2, 3) l.map(_ * 10) :+ 40 // List(10, 20, 30, 40)：追加是 O(n) v.map(_ * 10) :+ 40 // Vector 同操作近似 O(log n) l(2) // 随机访问：走两步，O(n) v(2) // 树查找，近似 O(log n)
实验结论对应选型口诀：头部递归与队列式消费用 List；下标访问、随机更新、规模不明就用 Vector。此外 SortedSet 与 SortedMap 按 Ord 排序而不是插入序，遍历顺序确定，做有序输出与范围查询（range 方法）时是唯一选择——不确定排序需求时别误用普通 Set，其遍历顺序是实现细节，两版本之间都可能变化。
本节要点回顾
- List 头部 O(1) 且结构共享，是递归与栈式处理的形状。
- Vector 各项均衡，默认之选；updated 产新不毁旧。
- view 提供惰性流水线，大集合多步变换才值得用。
- Map 取值用 get/getOrElse，避免键缺失异常。