Chapter 24《Collections in Depth》

可变和不可变集合

• 1. Scala中的集合可分为可变集合和不可变集合。可变集合可以当场被更新，不可变集合本身是不可变的。
• 2. 所有的集合类都可以在scala.collection或者其子包mutable，immutable或者generic中找到。大多数使用的集合分为三个变种，分别对应不同的可变性特征。分别位于scala.collection，scala.collection.immutable以及scala.collection.mutable。
• 3. scala.collection中的集合既可以是可变的，也可以是不变的。scala.collection.IndexedSeq[T]是scala.collection.immutable.IndexedSeq[T]和scala.collection.mutable.IndexedSeq[T]的超类。一般来说，collection中定义了与不可变集合相同的接口，mutable包中的可变集合会在不可变接口上添加一些有副作用的修改操作。
• 4. Scala的默认集合实现是不可变集合，因为scala包引入的默认绑定是不可变的。

---

集合的一致性

• 每一种集合都可以使用一致的语法创建对象，List(1, 2, 3)，Seq(1, 2, 3)，所有集合的toString方法也会产生一致的输出格式。类型名称加圆括号，其中的元素使用逗号隔开。类的层次结构如下：

  Traversable
      Iterable
         Seq
             IndexedSeq
                Vector
                ResizableArray
                GenericArray
             LinearSeq
                MutableList
                List
                Stream
         Set
             SortedSet
                TreeSet
             HashSet(immutable)
             LinkedHashSet
             HashSet(mutable)
             BitSet
             EmptySet, Set1, Set2, Set3, Set4
         Map
             SortedMap
                TreeMap
             HashMap(immutable)
             LinkedHashMap
             HashMap(mutable)
             EmptyMap, Map1, Map2, Map3, Map4
  

---

Traversable特质

• 1. Traversable中定义了集合的基本操作，都在TraversableLike中。唯一需要重写的方法是foreach：def foreach[U](f: Elem => U)，事实上，foreach并不会保存任何计算结果，返回的是Unit类型。
• 2. Traversable中的方法可以分为以下几类：
  • 添加，++
  • 映射，map, flatMap, collect
  • 转换，toIndexedSeq，toIterable，toStream，toArray，toList，toSeq，toSet，toMap，如果原集合已经匹配则直接返回该集合
  • copy，copyToBuffer：ArrayBuffer和ListBuffer和copyToArray
  • 大小操作，isEmpty，nonEmpty，size和hasDefiniteSize，如果hasDefiniteSize为false，则size方法会报错或者根本不返回。
  • 元素获取，head，last，headOption，lastOption，find，find会选中集合中满足条件的首个元素。并不是所有集合都会有明确的定义，第一个和最后一个。如果某个集合总是以相同的顺序交出元素，那么它就是有序的，否则就是无序的；顺序通常对测试比较重要，Scala对所有集合都提供了有序版本。HashSet的有序版本为LinkedHashSet。
  • 子集获取操作，takeWhile，tail，init，slice，take，drop，filter，dropWhile，filterNot，withFilter
  • 细分，splitAt(x take n, x drop n)，span(x takeWhile p, x dropWhile p)，partition(x filter p, x filterNot p)，groupBy，groupBy生成的是一个Map，分类依据为key，对应的列表为value，将集合元素切分为若干子集合
  • 元素测试，exists，forAll，count
  • 折叠，foldLeft，foldRight，/:，:\，reduceLeft，reduceRight
  • 特殊折叠，sum，product，min和max，用于操作特定类型的集合，数值型或者可比较类型
  • 字符串操作，mkString，addString，stringPrefix
  • 视图操作，view，是一个惰性求值的方法

---

Iterable特质

• 1. Iterable特质的所有方法都是使用iterator方法来定义的，这个抽象方法的作用是逐个交出集合的元素。Iterable中还有两个方法返回迭代器，一个是grouped，一个是sliding。
  • List(1,2,3,4,5): grouped(3)交出的是List(1,2,3)和List(4,5)
  • List(1,2,3,4,5): sliding(3)交出的是List(1,2,3),List(2,3,4),List(3,4,5)，再使用next迭代器就会出错。
• 2. Iterable还对Traversable添加了其他的一些方法，这些方法只有在有迭代器的情况下才能高效实现。
  • 子集合：takeRight，包含后n个元素的集合，如果集合没有顺序，那就是任意的n个。
  • dropRight，集合除去takeRight的部分。
  • 拉链：zip，zipAll(ys, x, y)：xs长度不够使用x填充，ys长度不够使用y填充，zipWithIndex，sameElements ys，检查xs和ys是否含有相同顺序的相同元素。
• 3. 为什么同时会有Traversable和Iterable？
     额外增加一层foreach的原因是有时候提供foreach比提供Iterator更容易。

---

序列型特质Seq，IndexedSeq和LinearSeq

• 1. Seq特质代表序列，序列是一种有长度并且元素有固定下标位置的Iterable。
  • 下标和长度操作：apply，isDefinedAt：测试入参是否在indices中，length：集合类通用size的别名，indices，lengthCompare：用于比较两个集合的长度，无限长度的也可以比较，Seq[T]是一个偏函数
  • 下标检索操作：indexOf，lastIndexOf，indexOfSlice，lastIndexOfSlice，indexWhere，lastIndexWhere，segmentLength(p,i)：从xs(i)开始满足p的片段的长度，prefixLength(p)，xs中满足p的最长前缀长度。
  • 添加：+:，:+，padTo
  • 更新：updated，patch，对mutable.Seq而言还有一个update操作，s(1)=8，可以当场更改元素，但是updated不会。
  • 排序：sorted，sortwith：使用lessThan函数进行比较，sortBy：对元素应用f后进行排序得到
  • 反转：reverse，revereIterator，reverseMap f：对元素应用f后进行倒序交出
  • 比较：startsWith，endsWith，contains，corresponds(ys, p)：查看xs和ys对应元素是否满足p，containsSlice
  • 集合操作：intersect，diff，union，distinct
• 2. 特质Seq有两个子特质，IndexedSeq和LinearSeq，并没有添加新的操作，不过各自拥有不同的性能特征。LinearSeq拥有高效的head和tail操作，IndexedSeq拥有高效的apply，length和随机访问操作。List和Stream都是常用的LinearSeq，Array和ArrayBuffer则是常用的IndexedSeq。Vector是混用两种达到添加和检索都比较高效的数据结构。

缓冲

• 1. 可变序列中比较重要的就是缓冲，缓冲允许对已有元素进行更新，同时还允许元素插入，杀出以及在尾部高效地添加元素。两个常用的Buffer是ListBuffer和ArrayBuffer，都能够高效地转到对应的数据结构，常用的操作有添加和删除。
  • 添加：+= 3，+= (3,4,5)，++= xs，x +=: buf，添加在头部，xs ++=: buf，insert(i, x)，insertAll(i, xs)
  • 删除操作：-= 3，remove(i)，remove(i, n)，trimStart n：移除缓冲中前n个元素，trimEnd：移除缓冲中后n个元素，clear
  • 克隆：clone

---

集

• 1. Set是没有重复元素的Iterable，主要的操作有：
  • 测试：contains，apply等同于contains，subsetOf
  • 添加：+和++
  • 移除：-和--
  • 集合操作：intersect，union，diff，符号版本的有&，|，&~
• 2. 可变集合拥有就地修改的能力，拥有的方法是：
  • 添加：+=，++=，add
  • 移除：-=，--=，remove，clear，retain
  • 更新：update(elem, boolean)，如果boolean为true，就把elem放入到set中；如果boolean为false，就把elem从set中移除。
• 3. 可变集合还提供了add和remove作为+=和-=的变种，add和remove返回值表示该操作是否让集合发生了改变。
• 4. 目前可变集的默认实现使用了哈希表来保存集的元素，不可变集的默认实现使用了一种可以跟集的元素数量适配的底层表示。空集使用单个对象表示，4个元素以内的集合使用Set1，Set2，Set3，Set4的对象表示，更多元素的集使用哈希字典树实现。4个元素以内的集，不可变集合的实现比可变集合的实现更紧凑。如果使用到的集合比较小，尽量使用不可变集。

---

映射

• 1. Map是由键值对组成的Iterable，Predef中提供了一个隐式转换，可以使用key -> value这样的写法表示(key, value)这个对偶。Map的操作和Set基本相似，可变Map提供额外的更多操作。
  • 查找：apply，get，getOrElse，contains，isDefinedAt
  • 更新：+，++，updated
  • 移除：-，--
  • 产生子集：keys，KeySet，KeysIterator，valuesIterator，values
  • 变换：filterKeys，mapValues
• 2. 可变Map的操作：
  • 更新：ms(k) = v，+=，++=，put，getOrElseUpdate
  • 移除：-=，--=，remove，retain
  • 变换：transform
  • 复制：copy
• 3. getOrElseUpdate通常被用做缓存。getOrElseUpdate(k, f)，第二个参数是传名参数，只有在get(k) = None的时候才会被触发调用。

---

具体的不可变集合类

列表

• 列表，head和tail以及在头部添加元素是常量时间，剩余的许多操作都是线性时间。

流

• 流和列表很像，不过其元素是惰性计算的，流可以是无限长的，只有被请求到的元素才会被计算，剩余的特征性能和列表是一样的。流的构造方法

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

  流可以用在无限的递归调用中，使用toList会强制计算其中的惰性部分。

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

向量

• 1. 向量可以访问和修改任意位置的元素。向量使用:+和:+来添加元素，Vector.empty
• 2. 向量的内部是宽而浅的树，树的每个节点上多达32个元素或者32个其他节点。元素个数在32以内的可以使用单个节点解决，2^10个元素可以使用一跳解决，对于正常大小的向量，选择一个元素最多需要5次基本操作就可以。向量的更新也是实效上的常量时间，只会复制从根节点到受影响元素这条path上的节点。目前是不可变IndexedSeq的默认实现。

不可变的栈

• 很少使用，push相当于List的::操作，pop相当于List的tail操作

不可变的队列

• enqueue(List(1,2,3))，dequeue是个元组，第一个元素是出队的元素，第二个元素是队列中剩下的元素组成的Queue。
• 可变队列的dequeue就直接是出队的元素。

区间

• range，它的内部表示占据常量的空间，因为Range的对象可以使用三个数来表示，start，end，step。

哈希字典树

• 是实现高效的不可变集和不可变Map的方式，内部类似于向量，每个节点有32个元素或者32个节点，但是选择是基于哈希码，使用最低5位找到第一棵子树，接下来的5位找到第二棵子树，当某个节点所有元素的哈希码各不相同时，这个选择过程就停止了。因此并不是用到哈希码的所有部分，哈希字典树在随机查找和插入删除之间有比较好的平衡，因此是不可变集以及映射的默认实现。

位组

• bit set是用来表示更大整数的小整数的集合。比如包含3,2,0的位组可以使用整数1101表示，转成十进制就是13。从内部讲，位组使用的是一个64位的Long数组，第一个Long表示0-63的整数，对位组的操作非常快，测试某个位组是否包含某个值只需要常量时间。

列表映射

• ListMap将Map表示为一个由键值对组成的链表，很少用，因为标准的不可变Map几乎总是比ListMap快，除非经常使用列表中的首个元素。

---

具体的可变集合类

数组缓冲

• 数组缓冲包含一个数组和一个大小，对数组缓冲的大部分操作跟数组一样，因为这些操作只是简单地访问和修改底层的数组。数组缓冲可以周期尾部高效地添加数据，非常适用于通过往尾部追加新元素来高效构建大集合的场景。可以使用ArrayBuffer.toArray方法构建Array数组。

列表缓冲

• 列表缓冲和数组缓冲很像，构建之后可以将列表缓冲转换为列表，内部使用的是链表而不是数组。

字符串构造器

• 字符串构造器有助于构建字符串，使用new StringBuilder创建即可，可使用toString方法

链表，2.11.0之后已经被deprecated了。

链表是由用next指针链接起来的节点组成的可变序列，在Scala中，并不使用null表示空链表，空链表的表示是next字段指向自己。LinkedList.empty.isEmpty返回的是true而不是抛出NullPointerException的异常。

可变列表

• MutableList是由一个链表和一个指向该列表末端的空节点组成，这使得往列表尾部的追加操作是常量时间的，因为它免除了遍历列表来寻找末端的需要，MutableList目前是scala的mutable.LinearSeq的标准实现。

队列

• 在可变队列中，enqueue是可以使用+=和++=来替代的，dequeue方法返回的是头部元素。

数组序列

• 数组序列是固定大小的，内部使用Array[AnyRef]来存放元素，Scala中的实现是ArraySeq类。

栈

• 和不可变版本是一样的，但是可以就地修改栈

数组栈

• ArrayStack是可变栈的另一种实现，内部是一个Array，在需要时需要改变大小。提供了快速的下标索引，一般而言大多数操作都比普通的可变栈更快。

哈希表

• 哈希表使用数组来存放元素，元素的存放位置取决于该元素的哈希码。往哈希表中添加元素只需要常量时间，只要数组中不发生碰撞。只要哈希表中的对象能够按照哈希码分布地非常均匀，操作就很快。因此Scala中默认的可变映射和可变集的实现都是基于哈希表的。HashSet和HashMap。

弱哈希映射

• 对于这种哈希映射，垃圾收集器并不会跟踪映射到其中的键的链接。如果没有其他引用指向这个键，那么关联值就会消失。弱哈希映射对于类似缓存这样的任务十分有用。如果是在常规的HashMap中，这个映射会无限增长，所有的键都不会被当做垃圾处理，使用弱哈希映射就可以避免这个问题。Scala中弱哈希的实现是基于Java中的WeakHashMap实现的。

并发映射

• 并发映射可以被多个线程同时访问。除了常见的Map操作之外，还提供了如下原子操作：m putIfAbsent(k, v)如果不存在k,v的绑定，添加k->v的绑定；m remove (k,v)如果k映射到v，移除该条目；m replace(k, old, new)如果k绑定到old，将k关联的值更新为new；m replace(k, v)，如果k绑定到某个值，将k关联的值替换为v。实现是基于Java的ConcurrentHashMap。

可变位组

• 可变位组可以被当前修改，在更新方面比不可变位组高效一点。

---

数组

• 在Scala中数组是一种特殊的集合，一方面，Scala的数组和Java的数组一一对应。Scala的数组Array[Int]是Java的int[]表示，Array[Double]对应double[]，另一方面，Scala提供了更多的功能。首先Scala的数组支持泛型，可以存在Array[T]，T是类型参数，其次，Scala数组和Seq是兼容的，数组还支持所有的序列操作。
• Scala的数据是用的Java中的数组表示的，如何支持序列的操作，主要是因为使用了隐式转换。每当数组被用作Seq的时候，会被隐式的转为Seq的子类，这个子类的名称是mutable.WrappedArray。另外一个可以被应用的隐式转换，这个转换只是简单地将所有的序列方法添加到数组，而不是将数组本身变成序列。将这个数组被包装成另一个类型为ArrayOps的对象，这个对象支持所有的序列方法。这个对象的声明周期很短，通常在调用完序列方法之后就不再访问了，存储空间可以被回收。现代的VM会完全避免创建这个对象。
• 编译器会选择ArrayOps的toInt方法而不是WarppedArray.toInt方法主要是因为WarppedArray的隐式转换定义在LowPriorityImplicits中，而ArrayOps的隐式转换定义在Predef中，Predef继承了LowPriorityImplicits。
• 在Scala中，可以使用Array[T]这样的表示，像Array[T]这样的泛型数组在运行的时候可以是Array[Int]等八种基本数据类型数组，也可以是对象的数组。在运行时，当类型为Array[T]的数组元素被更新或者访问时，有一系列的类型检查来决定实际的数据类型，在一定程度上减慢了数组操作。对泛型数组的访问会比确定类型的数组访问慢上几倍。

  // This is wrong!因为类型擦除时T的真正类型被隐去了
  def evenElems[T](xs: Vector[T]): Array[T] = {
  val arr = new Array[T]((xs.length + 1) / 2)
  for (i <- 0 until xs.length by 2)
  arr(i / 2) = xs(i)
  arr
  }
  error: cannot find class tag for element type T
  val arr = new Array[T]((arr.length + 1) / 2)
  ^
  

  需要提供线索来帮助编译器确定evenElems实际的类型参数是什么。使用scala.reflect.ClassTag的类标签，类标签描述的是给定类型"被擦除的类型"，对于许多场景，编译器可以自己生成类标签，对于完全泛化的场景，通常的做法是使用上下文界定传入类型标签，设定了一个隐式参数ClassTag[T]。如果能够找到，则可以正确构建数组。

  // This works
  import scala.reflect.ClassTag
  def evenElems[T: ClassTag](xs: Vector[T]): Array[T] = {
  val arr = new Array[T]((xs.length + 1) / 2)
  for (i <- 0 until xs.length by 2)
  arr(i / 2) = xs(i)
  arr
  }
  

  对于所有具体类型，编译器都可以构建一个隐式的ClassTag对象，但是入参本身是一个类型而且不带类标签，则不能使用。

  scala> def wrap[U](xs: Vector[U]) = evenElems(xs)
  <console>:9: error: No ClassTag available for U
  def wrap[U](xs: Vector[U]) = evenElems(xs)
               ^
  

  编译器需要得到关于类型U的ClassTag对象，但是没有找到，解决方法，在U后面使用上下文界定引入:ClassTag。

---

字符串

• 字符串转为序列的隐式转换也存在两个，一个是优先级较低的WarppedString，将字符串转换为序列，一个是优先级较高的StringOps，为字符串添加了所有不支持的序列操作。

---

性能特征

相等性

• 集合类库对相等性的处理和哈希的处理方式是一样的。
  • 1. 首先分为三大类，Seq，Set和Map，不同类下的集合永不相等。
  • 2. 另一方面如果是有序的序列，在元素相等的情况下，元素的顺序也要相等。使用可变元素作为哈希集或者哈希映射的键是不好的做法，因为使用键的哈希码来进行查找，如果键改变了，哈希码也就改变了，可能就找不到了，或者别的键也改变了，哈希码恰巧为修改的那个键，那么查到的就是错的。所以一般不推荐使用可变的对象来作为哈希的键值。

视图

• 集合中有map，filter等变换器来接收一个集合并产出一个集合。变换器可以通过两种主要的方法实现，一种是严格的，一种是惰性的。严格的变换器会构造出带有所有元素的新集合，惰性的变换器只是构造出结果集合的一个代理，元素会按需构造。

  def lazyMap[T, U](coll: Iterable[T], f: T => U) =
  new Iterable[U] {
  def iterator = coll.iterator map f
  }
  

  只有当新集合使用iterator方法的时候才会生成新的集合。系统化的方式可以将每个集合转换成惰性的版本，或者是反过来，这个就是集合视图。视图是一种特殊的集合，代表了某个基础集合，但是使用惰性的方式实现所有的变换器。seq.view方法得到集合的视图。例如 v map (_ + 1) map (_ * 2)会生成中间结果，如果一次性执行map操作会更快，方法就是将集合转换为视图，执行map操作，再将视图转回到集合。
  (v.view map (_ + 1) map (_ * 2)).force
  v.view产生一个SeqView对象，是一个惰性求值的Seq。有两个类型参数，Int表示该视图的元素类型，Vector[Int]表示该视图取回时要转回的类型集合。
  v.view map (_ + 1)得到一个SeqViewM[Int, Seq[]]表示一个含有函数map(+1)的操作需要被应用到v的包装器，M表示Map操作。map (_ * 2)之后得到SeqViewMM对象，最后使用force可以得到转换之后的结果。
  第一次应用Map的时候就丢失了关于集合类型Vector的信息，因为视图的代码非常多，通常只是对一般的集合而不是特定的集合实现视图。
  findPalindrome(words take 1000000)会构造出来一个1000000容量的中间结果，不管回文单词是否已经发生。会造成大量的不必要的开销，使用words.view take 1000000可以减少中间结果的开销。 实验发现并没有？？？
  view还没有看完

---

迭代器

• 迭代器不是集合，是逐个访问集合元素的一种方式。两个基本操作是next和hasNext，对it.next的调用会返回迭代器的下一个元素并将迭代器的状态往前推进一步。对同一个迭代器再次调用next会交出在前一个返回的基础上更进一步的元素。如果没有更多的元素可以返回，那么对next的调用就会抛出NoSuchElementException，可以使用hasNext的方法来检测是否还有更多的元素可以返回。

• Scala的迭代器还提供了Traversable，Iterable和Seq特质中的大部分方法，它们提供了foreach用来对迭代器返回的每个元素执行给定的过程。

• 迭代器的foreach和可遍历集合Traversable的同名方法有一个重要的区别，对迭代器调用foreach，执行完之后会将迭代器留在末端，再次调用next会抛出异常，但是可遍历集合的foreach不会，可以连续两次执行foreach。Iterator中其他操作也会出现同样的问题，操作完之后迭代器被留在末端。比如说map方法。只有一个方法允许使用同一个迭代器，duplicate方法，返回一个元组。这两个迭代器互相独立，原始的迭代器it在这个方法调用完成之后被推到了末端。

• 总体来说，Iterator和Traversable的行为还是比较类似的，因此抽取出来了一个公共的接口为TraversableOnce，该接口的对象可以使用foreach进行遍历，但是遍历完之后该对象的状态是不明确的，如果是Iterator，则迭代器在尾部，如果是Traversable，则对象保持原状。

• 迭代器的主要操作，next，hasNext，grouped，sliding，……和集合的操作是很相似的。添加的一个主要功能是buffered，将迭代器转换为带缓冲的迭代器。带缓冲的迭代器等于是有一个前哨，可以使用head返回迭代器的第一个元素，但是不向前推进迭代器。例如：使用这样的判断语句进行判断的时候，while (iterator.next() >= 2) {}，会丢失迭代器中的一个元素，第一个<2的元素是得不到的，正确的方法是使用带缓冲的iterator.head的方法来进行探寻。iterator.buffered得到的迭代器和iterator本身使用的是同一套迭代器。

---

从头构建集合

• Collection集合下面的所有类的伴生对象中都具有配套的apply方法，可以直接使用List(1,2,3)或者Map(1->3, 3->4)这样的方式来构建集合。对于接口类型，Traversable(1,2,3)会调用该接口的默认实现。在每一个伴生对象中也定义了一个空对象empty，List.empty = List()。

• Seq的子类伴生对象中定义有许多新的功能，比如说fill可填充表达式，tabulate可填充表达式，iterate可对指定的元素进行指定次数的计算。

---

Java和Scala集合的转换

• Scala提供了Java和Scala中主要集合之间的隐式转换，这些转换在import collection.JavaConversions._，转换的时候使用的是wrapper的对象，不做copy的操作，如果从Java集合转到了Scala集合，然后又从Scala集合转回到Java，这两个集合是同一个对象。在转换到Java集合的时候不考虑是否为可变集合，如果在不可变集合上试图进行可变操作，Java会抛出异常。

• 有双向转换：

  Iterator ⇔ java.util.Iterator
  Iterator ⇔ java.util.Enumeration
  Iterable ⇔ java.util.Iterable
  Iterable ⇔ java.util.Collection
  mutable.Buffer ⇔ java.util.List
  mutable.Set ⇔ java.util.Set
  mutable.Map ⇔ java.util.Map

• 有单向转换

  Seq ⇒ java.util.List
  mutable.Seq ⇒ java.util.List
  Set ⇒ java.util.Set
  Map ⇒ java.util.Map