scala 系列 ----集合综合篇

淡淡的烟草味﹌ 2022-11-19 09:50 214阅读 0赞

## 一.本章要点 ##

*  所有集合都扩展自Iterable特质;
 *  集合有三大类，分别为序列，集和映射;
 *  对于几乎所有集合类，Scala都同时提供可变和不可变的版本;
 *  Scala列表要么是空的，要么拥有一头一尾，其中尾部本身是一个列表;
 *  集是无小猴次序的集合;
 *  用LinkedHashSet来保留插入顺序，或者用SortedSet来顺序进行迭代;
 *  \+将元素添加到无先后次序的集合中;+：和:+向前或向后追加到序列;++将两个集合串接在一起;-和--移除元素;
 *  Iterable和Seq特质有数十个用于常见操作的方法。在编写冗长繁琐的循环之前，先看看这些方法是否满足你的需要;
 *  映射、折叠和拉链操作是很有用的技巧，用来将函数或操作应用到集合中的元素

## 二.主要的集合特质 ##

Scala集合继承等级中重要的特质：

![f7ed21432e18b865b5c87967866ef81c.png][]

Iterable：是指那些能生成用来访问集合中所有元素的Iterator的集合，如下：

//这是遍历一个集合最基本的方式
    val coll=...//某种Iterable
    val iter=coll.iterator
    while(iter.hasNext)
        ....

Seq：有先后次序的值的序列，如数组，列表等。IndexedSeq允许我们通过整型的下标访问任意元素。

Set：一组没有先后次序的值，在sortedSet中，元素以某种排过序的顺序访问。

Map：一组（键，值）对偶。SortedMap是按键的排序访问其中的实体。

继承等级和Java相似，有一些改进：

映射隶属于同一个继承等级而不是单独的层级关系;

IndexedSeq是数组的超类型，但不是列表的超类型，以便于区分

注：统一创建原则：Scala每个集合特质或类都有一个带有apply方法的伴生对象。

## 三.可变和不可变集合 ##

Scala有可变的也有不可变的集合，优先采用不可变集合。scala.collection包中的伴生对象产生出不可变集合，且scala包和Predef对象指向不可变特质的类型别名List，Set，Map，如Predef.Map和scala.collection.immutable.Map。

## 四.序列 ##

![3a4d300f08ef1ebd8ac16c1b183ba07b.png][]

不可变序列

vector是ArrayBuffer的不可变版本：一个带下标的序列，支持快速的随机访问。向量是以树形结构的形式实现的。每个节点可以有不超过32个字节点。对于100万个元素，只需要访问四层节点（10^6=32^4），在链表中需要500000跳。

Range表示一个整数序列，用to和until构造。

![75dd3fe3eac135719de9c58eb28e540b.png][]

可变序列

栈，队列，优先级队列。。。链表有些特殊

## 五.列表 ##

在Scala中，列表要不是空表（Nil），要不是一个head元素加上一个tail，二tail又是一个列表。

如val digits=List(4,2)，digits.head为4,digits.tail是List(2)，dights.tail..head=2，dights.tail.tail=Nil。

::操作符从给定的头和尾创建一个新的列表，且::是右结合的，如9::List(4,2)得List(9,4,2)

遍历链表：可以使用迭代器，使用递归，模式匹配。。。

//递归
    def sum(lst:List[Int]):Int=
    if(lst=Nil) 0 else lst.head+sum(lst.tail)
    //模式匹配
    def sum(lst:List[Int]):Int=lst match{
    case Nil=>0
    case h::t=>h+sum(t)
    }

## 六.可变列表 ##

可变的LinkedList和不可变的List相似，可以通过对elem引用赋值来修改其头部，对next引用赋值修改其尾部。

## 七.集 ##

集是不重复元素的集合，是无序的（缺省情况下是哈希表实现的）。\[允许集对它们从新排列，块\]

链式哈希可以记住元素插入顺序，会维护一个链表来达到这个目的（LInkedHashSet）;

按照以排序的方式访问集中的元素（SortedSet），红黑树实现。

位集是集的一种实现，以一个字位序列的方式存放非负整。

contains方法检查某个集是否包含给定的值，subsetOf检查某个集当中的所有元素是否被另一个集包含。union（++）、intersect（--）、diff是常用的操作，也可以写作|、&,&~　。

## 八.用于添加或去除元素的操作符 ##

![6f5eaf9ba43fa034b9c2efc84ed0f3b6.png][]

![a001adcb7f2258697ab880fb9a2da2b7.png][]

## 九.常用方法 ##

Iterable重要方法：

![67188253a92202a09da5a71025f0bd44.png][]

![63d4eae157895baf22f3dfed7e8d2e53.png][]

Seq特质重要的方法：

![9097b9261db6eea29430f63a8cd527e0.png][]

![1fa68f2925a6b06b650aa2b50df822ef.png][]

注：这些方法都不改变原有集合，而是返回与原有集合相同类型的集合，这叫”统一返回类型“原则。

## 十.将函数映射到集合 ##

例如map，filter等等。

flatMap产出一个集合而不是一个值。

collect用于偏函数——没有对所有可能输入值进行定义的函数。

## 十一.化简、折叠和扫描 ##

二元函数组合集合中的元素。如List(1,7,2,9).reduceLeft(\_ - \_)得((1-7)-2)-9=-17，同样Left(1,7,2,9).reduceRight(\_ - \_)得1-(7-(2-9))=-13，List(1,7,2,9).foldLeft(0)(\_ - \_)得0-1-7-2-9=-19（可以用:/来写foldLeft）。

折叠有时候可以替换循环，如计算字母出现频率，一种是遍历这个字符串然后更新映射，另一种是将频率映射和新遇到的字母结合产生一个新的频率映射，这就是折叠，例：

(Map[Char,Int]()/:"TESthahaLYq"){
    (m,c)=>m+(x->(m.getOrElse(c,0)+1))
    }

## 十二.拉链操作 ##

将两个集合相互对应的元素结合在一起。如果两个集合长度不一致，zip则按短的来;zipAll会让你指出较短列表的缺省值zipWithIndex返回对偶的列表。

## 十三.迭代器 ##

可以用iterator方法从集合中获得一个迭代器（hasext(),next()等方法，遍历一次该迭代器九不能使用了），减少代价，但是迭代器很脆弱，每次对next的调用都会改变迭代器的指向。

## 十四.流 ##

流提供的是一个不可变的替代品（尾部被来计算的不可变的列表），这是懒执行的，只有当用到时才会执行。

使用\#::来构建一个流，例def numsFrom(n:BigInt):Stream\[BigInt\]=n \#::numsFrom(n+1)。

## 十五.懒视图 ##

可以对其他集合应用view方法得到同样懒执行的效果，例：val power=(0 until 1000).view.map(pow(10,\_))将产出一个未被求值的集合，再次调用会从新计算。（对于处理那种需要以多种方式进行交换的大型集合很有好处，避免了构建大型中间集合的需要）。

## 十六.与Java集合的互操作 ##

使用JavaConversions对象转换，转换转出的都是包装器。

![9b92e0248ff014ab49fa3e17bc11ae65.png][]

## 十七.线程安全的集合 ##

当多个线程访问一个可变集合时，确保自己不会在其他线程正在访问它时修改，可以用六个特质同步：

![903ed64257a43842ed41c306e0e3f705.png][]

最好使用java.util.concurrent中的ConcurrentHashMap或ConcurrentSkipListMap。

## 十八.并行集合 ##

并行集合coll，如并发的求和coll.par.sum，对数组、缓冲、哈希表、平衡树而言，并行实现会直接重用底层实际集合的实现，很高效。

例：一个是顺序产出，一个是按产出顺序

![7ed777e8bca0e2fb2cf487eea4e74d54.png][]

注：如果并行运算修改了共享的变量，则结果无法预知;

par方法返回的并行集合的类型为扩展自ParSeq、ParSet或ParMap特质的类型，所有这些特质都是ParIterable的子类型，但并不是Iterable的子类型，因此不能将并行集合传递给预期的Iterable、Seq、Set或Map的方法，可以用ser方法将并行集合传递给串行化的版本。

![5b7803bd6434e65fb8f989ff2cadb396.png][]

## 十九.练习 ##

![0b7f186d9efd74238c6d3888415818b6.png][]

![8870a9bee286b78dd0969825da5b5185.png][]

[f7ed21432e18b865b5c87967866ef81c.png]: /images/20221119/8be2830134514a39954bf4a96651045d.png
[3a4d300f08ef1ebd8ac16c1b183ba07b.png]: https://img-blog.csdnimg.cn/img_convert/3a4d300f08ef1ebd8ac16c1b183ba07b.png
[75dd3fe3eac135719de9c58eb28e540b.png]: https://img-blog.csdnimg.cn/img_convert/75dd3fe3eac135719de9c58eb28e540b.png
[6f5eaf9ba43fa034b9c2efc84ed0f3b6.png]: https://img-blog.csdnimg.cn/img_convert/6f5eaf9ba43fa034b9c2efc84ed0f3b6.png
[a001adcb7f2258697ab880fb9a2da2b7.png]: https://img-blog.csdnimg.cn/img_convert/a001adcb7f2258697ab880fb9a2da2b7.png
[67188253a92202a09da5a71025f0bd44.png]: https://img-blog.csdnimg.cn/img_convert/67188253a92202a09da5a71025f0bd44.png
[63d4eae157895baf22f3dfed7e8d2e53.png]: https://img-blog.csdnimg.cn/img_convert/63d4eae157895baf22f3dfed7e8d2e53.png
[9097b9261db6eea29430f63a8cd527e0.png]: https://img-blog.csdnimg.cn/img_convert/9097b9261db6eea29430f63a8cd527e0.png
[1fa68f2925a6b06b650aa2b50df822ef.png]: https://img-blog.csdnimg.cn/img_convert/1fa68f2925a6b06b650aa2b50df822ef.png
[9b92e0248ff014ab49fa3e17bc11ae65.png]: https://img-blog.csdnimg.cn/img_convert/9b92e0248ff014ab49fa3e17bc11ae65.png
[903ed64257a43842ed41c306e0e3f705.png]: https://img-blog.csdnimg.cn/img_convert/903ed64257a43842ed41c306e0e3f705.png
[7ed777e8bca0e2fb2cf487eea4e74d54.png]: https://img-blog.csdnimg.cn/img_convert/7ed777e8bca0e2fb2cf487eea4e74d54.png
[5b7803bd6434e65fb8f989ff2cadb396.png]: https://img-blog.csdnimg.cn/img_convert/5b7803bd6434e65fb8f989ff2cadb396.png
[0b7f186d9efd74238c6d3888415818b6.png]: https://img-blog.csdnimg.cn/img_convert/0b7f186d9efd74238c6d3888415818b6.png
[8870a9bee286b78dd0969825da5b5185.png]: https://img-blog.csdnimg.cn/img_convert/8870a9bee286b78dd0969825da5b5185.png