scala 容器详细解释

Tim在路上

发布于 2020-08-04 15:07:08

1.4K00

代码可运行

文章被收录于专栏：后台技术底层理解后台技术底层理解

运行总次数：0

代码可运行

scala 中的所有集合类位于 scala.collection 或 scala.collection.mutable，scala.collection.immutable，scala.collection.generic 中

scala.collection.immutable 包是的集合类确保不被任何对象改变。

scala.collection.mutable 包的集合类则有一些操作可以修改集合。

scala.collection 包中的集合，既可以是可变的，也可以是不可变的。

所有的集合类都继承了 Traverable 接口,也就都具有相似的功能.

scalaCollection.png

Traverable

Traversable（遍历）是容器(collection)类的最高级别特性，它唯一的抽象操作是foreach:

def foreach[U](f: Elem => U)

需要实现Traversable的容器(collection)类仅仅需要定义与之相关的方法，其他所有方法可都可以从Traversable中继承。

foreach方法用于遍历容器（collection）内的所有元素和每个元素进行指定的操作（比如说f操作）。操作类型是Elem => U，其中Elem是容器（collection）中元素的类型，U是一个任意的返回值类型。对f的调用仅仅是容器遍历的副作用，实际上所有函数f的计算结果都被foreach抛弃了。

Traversable同时定义的很多具体方法，如下表所示。这些方法可以划分为以下类别：

相加操作++（addition）表示把两个traversable对象附加在一起或者把一个迭代器的所有元素添加到traversable对象的尾部。
Map操作有map，flatMap和collect，它们可以通过对容器中的元素进行某些运算来生成一个新的容器。
转换器（Conversion）操作包括toArray，toList，toIterable，toSeq，toIndexedSeq，toStream，toSet，和toMap，它们可以按照某种特定的方法对一个Traversable 容器进行转换。等容器类型已经与所需类型相匹配的时候，所有这些转换器都会不加改变的返回该容器。例如，对一个list使用toList，返回的结果就是list本身。
拷贝（Copying）操作有copyToBuffer和copyToArray。从字面意思就可以知道，它们分别用于把容器中的元素元素拷贝到一个缓冲区或者数组里。
Size info操作包括有isEmpty，nonEmpty，size和hasDefiniteSize。Traversable容器有有限和无限之分。比方说，自然数流Stream.from(0)就是一个无限的traversable 容器。hasDefiniteSize方法能够判断一个容器是否可能是无限的。若hasDefiniteSize返回值为ture，容器肯定有限。若返回值为false，根据完整信息才能判断容器（collection）是无限还是有限。
元素检索（Element Retrieval）操作有head，last，headOption，lastOption和find。这些操作可以查找容器的第一个元素或者最后一个元素，或者第一个符合某种条件的元素。注意，尽管如此，但也不是所有的容器都明确定义了什么是“第一个”或”最后一个“。例如，通过哈希值储存元素的哈希集合（hashSet），每次运行哈希值都会发生改变。在这种情况下，程序每次运行都可能会导致哈希集合的”第一个“元素发生变化。如果一个容器总是以相同的规则排列元素，那这个容器是有序的。大多数容器都是有序的，但有些不是（例如哈希集合）– 排序会造成一些额外消耗。排序对于重复性测试和辅助调试是不可或缺的。这就是为什么Scala容器中的所有容器类型都把有序作为可选项。例如，带有序性的HashSet就是LinkedHashSet。
子容器检索（sub-collection Retrieval）操作有tail，init，slice，take，drop，takeWhilte，dropWhile，filter，filteNot和withFilter。它们都可以通过范围索引或一些论断的判断返回某些子容器。
拆分（Subdivision）操作有splitAt，span，partition和groupBy，它们用于把一个容器（collection）里的元素分割成多个子容器。
元素测试（Element test）包括有exists，forall和count，它们可以用一个给定论断来对容器中的元素进行判断。
折叠（Folds）操作有foldLeft，foldRight，/:，:\，reduceLeft和reduceRight，用于对连续性元素的二进制操作。
特殊折叠（Specific folds）包括sum, product, min, max。它们主要用于特定类型的容器（数值或比较）。
字符串（String）操作有mkString，addString和stringPrefix，可以将一个容器通过可选的方式转换为字符串。
视图（View）操作包含两个view方法的重载体。一个view对象可以当作是一个容器客观地展示。接下来将会介绍更多有关视图内容。 https://docs.scala-lang.org/zh-cn/overviews/collections/trait-traversable.html

Iterable

容器（collection）结构的上层还有另一个trait。这个trait里所有方法的定义都基于一个抽象方法，迭代器（iterator，会逐一的产生集合的所有元素）。从Traversable trait里继承来的foreach方法在这里也是利用iterator实现。

def foreach[U](f: Elem => U): Unit = {
  val it = iterator
  while (it.hasNext) f(it.next())
}

许多Iterable 的子类覆写了Iteable的foreach标准实现，因为它们能提供更高效的实现。

Iterable有两个方法返回迭代器：grouped和sliding。然而，这些迭代器返回的不是单个元素，而是原容器（collection）元素的全部子序列。

scala> val xs = List(1, 2, 3, 4, 5)
xs: List[Int] = List(1, 2, 3, 4, 5)
scala> val git = xs grouped 3
git: Iterator[List[Int]] = non-empty iterator
scala> git.next()
res3: List[Int] = List(1, 2, 3)
scala> git.next()
res4: List[Int] = List(4, 5)
scala> val sit = xs sliding 3
sit: Iterator[List[Int]] = non-empty iterator
scala> sit.next()
res5: List[Int] = List(1, 2, 3)
scala> sit.next()
res6: List[Int] = List(2, 3, 4)
scala> sit.next()
res7: List[Int] = List(3, 4, 5)

抽象方法： xs.iterator xs迭代器生成的每一个元素，以相同的顺序就像foreach一样遍历元素。其他迭代器： xs grouped size 一个迭代器生成一个固定大小的容器（collection）块。 xs sliding size 一个迭代器生成一个固定大小的滑动窗口作为容器（collection）的元素。子容器（Subcollection）： xs takeRight n 一个容器（collection）由xs的最后n个元素组成（或，若定义的元素是无序，则由任意的n个元素组成）。 xs dropRight n 一个容器（collection）由除了xs 被取走的（执行过takeRight （）方法）n个元素外的其余元素组成。拉链方法（Zippers）： xs zip ys 把一对容器 xs和ys的包含的元素合成到一个iterabale。 xs zipAll (ys, x, y) 一对容器 xs 和ys的相应的元素合并到一个iterable ，实现方式是通过附加的元素x或y，把短的序列被延展到相对更长的一个上。 xs.zip WithIndex 把一对容器xs和它的序列，所包含的元素组成一个iterable 。比对： xs sameElements ys 测试 xs 和 ys 是否以相同的顺序包含相同的元素。

seq

seq 的apply操作是用于索引的访问使用()作用

索引和长度的操作 apply、isDefinedAt、length、indices，及lengthCompare。序列的apply操作用于索引访问；因此，Seq[T]类型的序列也是一个以单个Int（索引下标）为参数、返回值类型为T的偏函数。换言之，Seq[T]继承自Partial Function[Int,T]。
序列各元素的索引下标从0开始计数，最大索引下标为序列长度减一。序列的length方法是collection的size方法的别名。lengthCompare方法可以比较两个序列的长度，即便其中一个序列长度无限也可以处理。
索引检索操作（indexOf、lastIndexOf、indexofSlice、lastIndexOfSlice、indexWhere、lastIndexWhere、segmentLength、prefixLength）用于返回等于给定值或满足某个谓词的元素的索引。
加法运算（+:，:+，padTo）用于在序列的前面或者后面添加一个元素并作为新序列返回。
更新操作（updated，patch）用于替换原序列的某些元素并作为一个新序列返回。
排序操作（sorted, sortWith, sortBy）根据不同的条件对序列元素进行排序。
反转操作（reverse, reverseIterator, reverseMap）用于将序列中的元素以相反的顺序排列。
比较（startsWith, endsWith, contains, containsSlice, corresponds）用于对两个序列进行比较，或者在序列中查找某个元素。
多集操作（intersect, diff, union, distinct）用于对两个序列中的元素进行类似集合的操作，或者删除重复元素。

特性（trait) Seq 具有两个子特征（subtrait） LinearSeq和IndexedSeq。它们不添加任何新的操作，但都提供不同的性能特点：线性序列具有高效的 head 和 tail 操作，而索引序列具有高效的apply, length, 和 (如果可变) update操作。

Buffer

Buffers是可变序列一个重要的种类。它们不仅允许更新现有的元素，而且允许元素的插入、移除和在buffer尾部高效地添加新元素。

ListBuffer和ArrayBuffer是常用的buffer实现。顾名思义，ListBuffer依赖列表（List），支持高效地将它的元素转换成列表。而ArrayBuffer依赖数组（Array），能快速地转换成数组。

map

查询类操作：apply、get、getOrElse、contains和DefinedAt。它们都是根据主键获取对应的值映射操作。例如：def get(key): Option[Value]。“m get key” 返回m中是否用包含了key值。如果包含了，则返回对应value的Some类型值。否则，返回None。这些映射中也包括了apply方法，该方法直接返回主键对应的值。apply方法不会对值进行Option封装。如果该主键不存在，则会抛出异常。
添加及更新类操作：+、++、updated，这些映射操作允许你添加一个新的绑定或更改现有的绑定。
删除类操作：-、–，从一个映射（Map）中移除一个绑定。
子集类操作：keys、keySet、keysIterator、values、valuesIterator，可以以不同形式返回映射的键和值。
filterKeys、mapValues等变换用于对现有映射中的绑定进行过滤和变换，进而生成新的映射。

mutable.Map 类是一个可变的Map

SychronizedMap trait

无论什么样的Map实现，只需混入SychronizedMap trait，就可以得到对应的线程安全版的Map。例如，我们可以像下述代码那样在HashMap中混入SynchronizedMap。

具体不可变集实体类

List

列表List是一种有限的不可变序列式。提供了常数时间的访问列表头元素和列表尾的操作，并且提供了常数时间的构造新链表的操作，该操作将一个新的元素插入到列表的头部。其他许多操作则和列表的长度成线性关系。

8 :: list

注意只能插入到链表的头

Stream

流Stream与List很相似，只不过其中的每一个元素都经过了一些简单的计算处理。也正是因为如此，stream结构可以无限长。只有那些被要求的元素才会经过计算处理，除此以外stream结构的性能特性与List基本相同.

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

stream定义为惰性的计算

Verctor

对于只需要处理数据结构头结点的算法来说，List非常高效。可是相对于访问、添加和删除List头结点只需要固定时间，访问和修改头结点之后元素所需要的时间则是与List深度线性相关的。

向量Vector是用来解决列表(list)不能高效的随机访问的一种结构.

val vec = scala.collection.immutable.Vector.empty  
 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)

val vec = Vector(1, 2, 3)
vec: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)
scala> vec updated (2, 4)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4)

具体可变容器类

ArrayBuffer

是一个数组缓冲,因为这些操作直接访问、修改底层数组.

val buf = scala.collection.mutable.ArrayBuffer.empty[Int]
buf: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()

scala> buf += 1
res0: buf.type = ArrayBuffer(1)

scala> buf += 10
res1: buf.type = ArrayBuffer(1, 10)

scala> buf.toArray
res2: Array[Int] = Array(1, 10)

ListBuffer

ListBuffer 类似于数组缓冲。区别在于前者内部实现是链表，而非数组.

val buf = scala.collection.mutable.ListBuffer.empty[Int]
buf: scala.collection.mutable.ListBuffer[Int] = ListBuffer()
scala> buf += 1
res35: buf.type = ListBuffer(1)
scala> buf += 10
res36: buf.type = ListBuffer(1, 10)
scala> buf.toList
res37: List[Int] = List(1, 10)

StringBuilders

数组缓冲用来构建数组，列表缓冲用来创建列表。

val buf = new StringBuilder
buf: StringBuilder =
scala> buf += 'a'
res38: buf.type = a
scala> buf ++= "bcdef"
res39: buf.type = abcdef
scala> buf.toString
res41: String = abcdef