Scala集合库

Scala集合库提供了大量不同的存储和操作数据的方法。其中可以分为三类：

• 不可变和可变集合
• 即时和延迟计算集合
• 线性和并行计算集合

这六类中的每一种都很有用。有时候并行执行可以极大提高吞吐量，也有时候延迟计算可以提高性能。

下面介绍了与集合相关的包：

从Predef得到的Seq类型是collection.Seq，而Predef引用的其他公共类型是以collection.immutable开头的，如List、Map和Set。

1 最常用的不可变集合

不可变集合的设计目标是提供既高效又安全的实现。特别是可以在多线程之间共享而无需加锁。这个集合中的大部分都是使用高级技巧来在集合的不同版本之间“共享”内存。三个最常用的不可变的集合为Vector、List和Stream。

1.1 Vector

Scala的Vector实现为一组嵌套数组，在分割和连接时非常有效率。适用于大部分通用算法，因为它有高效的下标计算能力，以及能够在使用像+:和++方法时共享大部分内部结构的能力。

Vector的随机访问复杂度是log_32(N)，使用32位整数下标时在JVM上是个效率不错的小常量。同时Vector是完全不可变的，而且有合理的共享内存特性。

• 存储方式

Vector是个由元素的下标组成的前缀树（trie），前缀树是给定路径上的所有子节点功用某种形式的公共键值。 上图给出了下标为0到7的前缀树，其根节点为空，到达前缀树的指定下标的路径可以由下标数字的二进制表示计算出来。

• 数组结构与访问机制

Scala的Vector集合非常类似于一个分支系数为32的下标前缀树。关键区别在于Vector用一个数组来表示分支。这使整个结构变成数组的数组（嵌套数组）。

下图是分支系数为2的二进制Vector： 其中有三个基本素组：display0、display1和display2.这些数组代表原始前缀树的深度。每个显示元素（display element）都是一个更深一层的的嵌套数组（display0是元素的数组，display1是数组的数组，display2是数组的数组的数组）。查找集合元素的步骤是先判断其深度，然后用跟前缀树一样的方式确定元素所在的数组。比如找数字4，其深度为2，所以先选择display2数组，4的二进制形式100，所以外层数组是下标为1的位置上，中层数组下标为0，最后4就位于结果数组的下标0的位置上。

二进制前缀树根据下标随机取值的复杂度是log_2(n)，Scala的Vector的分支系数为32，那么访问任何元素的时间复杂度是log_32(n)，对32位的下标也就大约是7，对64位大约是13.而对于较小的集合，排序的开销也会降低，所以访问速度会更快。所以随机访问的时间复杂度与前缀树的大小成正比。

• 共享方式

前缀树支持的共享级别很高。如果集合是不可变的，那么修改指定下标的值可以重用前缀树的部分数据。 上图中，下标0位置的值修改为new，创建新的前缀树共享重用了原来的大部分节点，这样有助于降低修改集合的开销。对于分支系数为2的前缀树，修改一个节点的开销是log_2(n)，可以通过增加分支系数进一步降低。

• 优点

Scala的Vector为32分支，这除了带来查找时间和修改时间可以随集合大小伸缩外，它还提供了不错的缓存一致性，因为集合里相近的元素有很大可能位于同一个内存数组里。其高效结合不可变所带来的线程安全使之成为库里最强大的有序集合。

当然，如果频繁执行头尾分解，最好选择LinearSeq特质的子类List。

1.2 List

Scala的List是个单链表，适用于将列表头和尾分离处理的递归算法。如果总是在列表头上做添加或删除操作，那么它的性能不错。如果使用的模式比较高级，那它就比较吃力了。List不如Vector那么通用，所以应该仅用在符合它期望的算法里。

• List的基本结构

List由两部分组成，一是代表空列表的Nil，另一个是“Cons”格子，也称为链接节点。Cons格子持有两个引用，一个指向值，另一个指向对列表后续元素

List集合继承自LinearSeq，因此它支持O(1)复杂度的头尾分解和头部添加操作。

在只是用头部添加和头尾分解操作的时候，List可以支持极大的共享数据，但是如果列表中间的元素被修改，那前半个列表都需要重新生成，这就是List不如Vector适合开发的原因。

1.3 Stream

之前的List是个即时计算的集合，当列表完成时，头尾都已经计算完成了。Stream是一种延迟持久（lazy persistent）的集合。故流可以颜值计算其元素的值，逐渐持久它们。流可以用来表示无限序列而不用担心内存溢出。流还可以记住其生命周期里已经计算的元素，从而提供对已计算过的值的高效访问。

• 基本结构

Stream也是由Cons格子和空stream组成，类似于List类。Stream和List的最大区别是Stream会延迟计算自己。也就是说，Stream并不保存实际元素，而是保存能用来计算头元素和其余部分(tail)的函数对象。这使得Stream可以保存无限序列——一种把信息和另一个集合连接起来的常用办法。

使用#::操作来构造流，使用Stream.empty代表空流。并且流不会重复计算

Stream的绝佳使用场所之一是从前个值计算下个值。这在计算斐波那契数列时特别明显，斐波那契的下个元素是前两个元素的和。

如果最终结果大到内存放不下，那么流也解决不了问题。在这种情况下，最好是用TraversableView来避免不必要的操作，同时允许内存回收。

val fibs2 = new Traversable[Int] {
    def foreach[U](f: Int => U): Unit = {
        def next(a: Int, b: Int): Unit = {
            f(a)
            next(b, a+b)
        }
        next(0, 1)
    }
} view

fibs2 drop 3 take 5 toList

定义的Traversable[Int]，立刻用view方法把这个Traversable转化为TraversableView，以免其foreach方法被立刻调用。View是一种延迟计算操作的集合

TraversableView不把计算过的值保存下来，这样意味着反复根据相同的下标从TraversableView里取值时开销是很大的。最好仅在Stream太大无法装进内存的场景下使用它。

2 最常用的可变集合

2.1 ArrayBuffer

ArrayBuffer是一种可变数组，其大小与所含元素不一定一直。这样无需拷贝整个数组就可以添加元素。ArrayBuffer内部是一个数组并保存了当前大小。当添加新元素到ArrayBuffer时，它会检查这个大小值，如果底层数组没满，那这个元素就直接加进数组。如果已经满了，则创建更大的数组，然后把所有元素复制到新数组中。重点是新数组也会创建的比加入当前元素所需要的要大一些。尽管有时候要把整个数组赋值到新数组里，但是添加元素的摊销成本是个常数。

ArrayBuffer集合类似于Java的java.util.ArrayList。两者的主要区别在于Java的ArrayList试图摊销移除和添加元素到列表头和列表尾的开销，而Scala的ArrayBuffer只优化了添加和移除列表尾的操作。

2.2 监听集合特质

Scala的可变集合库提供了三个特质：ObservableMap、ObservableBuffer和ObservableSet，可以用来监听集合的修改事件。在恰当的集合上混入三个特质之一可以让对集合的修改除法事件发给观察者。

添加元素1触发了Include事件，移除元素除法了Remove事件。