Scala 集合(二)

柔情只为你懂 2022-04-15 02:28 289阅读 0赞

# Scala 通用、可变、不可变、并发以及并行集合 #

Scala程序设计 第2版 - 原版.pdf 下载：[https://download.csdn.net/download/u014646662/10805074][https_download.csdn.net_download_u014646662_10805074]

1 scala.collection包

2 collection.concurrent包

3 collection.convert包

4 collection.generic包

5 collection.immutable包

6 scala.collection.mutable包

7 scala.collection.parallel包

对人工智能感兴趣的同学，可以点击以下链接：

[现在人工智能非常火爆，很多朋友都想学，但是一般的教程都是为博硕生准备的，太难看懂了。最近发现了一个非常适合小白入门的教程，不仅通俗易懂而且还很风趣幽默。所以忍不住分享一下给大家。点这里可以跳转到教程。][Link 1]

[https://www.cbedai.net/u014646662][Link 1]

# 集合包介绍 #

## 1 scala.collection包 ##

在collection 包中声明的类型定义了可变及不可变的序列、可变及不可变的并行、并发集合类型共享的抽象，其中有的不仅声明，而是直接进行了定义。这就意味着，比如只能在可变类型中使用的带破坏性的（可变的）操作不是在这里定义的。不过，在运行时如果集合是可变的，我们可能要考虑线程的安全问题。 从Predef 得到的Seq 类型是collection.Seq， 而Predef 引入的其他公共类型是以collection.immutable 开头的，如List、Map 和Set。Predef 使用collection.Seq 的原因是要让Scala可以像处理序列一样处理Java 的数组，而Java 的数组是可变的（Predef 事实上定义了从Java 数组到collection.mutable.ArrayOps的隐式转换，而后者支持序列的相关操作）。Scala计划在未来的版本中用不可变的Seq 代替它。不幸的是，就目前而言，这也意味着如果一个方法声明它返回一个序列，它可能会返回一个可变的序列实例。同样地，如果一个方法需要一个序列参数，调用者也可以传入一个可变的序列实例。如果你更喜欢用更安全的immutable.Seq 作为默认的Seq，常见的方法是，为你的项目定义一个包对象，其中定义了Seq 类型，以覆盖Predef 定义的Seq，如下所示：

package cn.com.tengen.test.obj
    package object safeseq {
      type Seq[T] = collection.immutable.Seq[T]
    }
    //import  cn.com.tengen.test.obj.safeseq._
    class Test {
    }
    
    object Test extends App {
    
      val s1: Seq[Int] = List(1,2,3,4)
      println(s1)
      val s2: Seq[Int] = Array(1,2,3,4)
      println(s2)
    
    }

程序中导包的哪一行，注释一旦放开，程序就会报错

放到命令行在执行一遍

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ2NDY2NjI_size_16_color_FFFFFF_t_70][]

前两个Seq 是由Predef 暴露的默认项collection.Seq。第一个Seq 引用了一个不可变列表，第二个Seq 引用了可变的（经过包装的）Java 数组。然后我们导入了新的Seq 定义，从而遮蔽了Predef 中的Seq 定义。在重新创建Seq类型之前，引用的是 type Seq\[+A\] = scala.collection.Seq\[A\]，重新定义之后引用的是collection.immutable.Seq\[T\]。无论哪种方式，如果我们想取集合的前几个元素或希望从集合的一端遍历到另一端，Seq都是具体集合的一个方便、好用的抽象。

## 2 collection.concurrent包 ##

这个包只定义了两种类型：collection.concurrent.Map特征和实现了该trait 的collection.concurrent.TrieMap类。Map 继承了collection.mutable.Map，但它使用了原子操作，因此得以支持线程安全的并发访问。collection.mutable.Map的实现是一个字典树散列类collection.concurrent.TrieMap。它实现了并发、无锁的散列数组，其目的是支持可伸缩的并发插入和删除操作，并提高内存使用效率。

## 3 collection.convert包 ##

在这个包中定义的类型是用来实现隐式转换方法的，隐式转换将Scala 的集合包装为Java集合，反之亦然。

## 4 collection.generic包 ##

collection 包声明的抽象适用于所有集合，而collection.generic 只为实现特定的可变、不可变、并行及并发集合提供一些组件。这里的大多数类型只对集合的实现者有意义。

## 5 collection.immutable包 ##

大部分时间你都会与immutable 包中定义的集合打交道。这些类型提供了单线程（与并行相对）操作，由于类型是不可变的，因而是线程安全的。

<table> 
 <tbody> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;width:78pt;">BitSet</td> 
 <td style="vertical-align:bottom;">非负整数的集合，内存效率高。元素表示为可变大小的比特数组，其中比特被打包为64 比特的字。最大元素个数决定了内存占用量</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">HashMap</td> 
 <td style="vertical-align:bottom;">用字典散列实现的映射表</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">HashSet</td> 
 <td style="vertical-align:bottom;">用字典散列实现的集合</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">List</td> 
 <td style="vertical-align:bottom;">用于相连列表的trait，头节点访问复杂度为O(1)，其他元素为 O(n)。其伴随对象有apply 方法和其他“工厂”方法，可以用来构造List 的子类实例</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">ListMap</td> 
 <td style="vertical-align:bottom;">用列表实现的不可变映射表</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">ListSet</td> 
 <td style="vertical-align:bottom;">用列表实现的不可变集合</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Map</td> 
 <td style="vertical-align:bottom;">为所有不可变的映射表定义的trait，随机访问复杂度为O(1)，其伴随对象有apply 方法和其他“工厂”方法，可以用来构造其子类实例</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Nil</td> 
 <td style="vertical-align:bottom;">用来表示空列表的对象</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">NumericRange</td> 
 <td style="vertical-align:bottom;">Range 类的推广版本，将适用范围推广到任意完整的类型。使用时，必须提供类型的完整实现</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Queue</td> 
 <td style="vertical-align:bottom;">不可变的FIFO（先入先出）队列</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Seq</td> 
 <td style="vertical-align:bottom;">为不可变序列定义的trait，其伴随对象有apply 方法和其他“工厂”方法，可以用来构造其子类实例</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Set</td> 
 <td style="vertical-align:bottom;">特征，为不可变集合定义了操作，其伴随对象有apply方法和其他“工厂”方法，可以用来构造其子类实例</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">SortedMap</td> 
 <td style="vertical-align:bottom;">为不可变映射表定义的trait，包含一个可按特定排列顺序遍历元素的迭代器。其伴随对象有apply 方法和其他“工厂”方法，可以用来构造其子类实例</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">SortedSet</td> 
 <td style="vertical-align:bottom;">为不可变集合定义的trait，包含一个可按特定排列顺序遍历元素的迭代器。其伴随对象有apply 方法和其他“工厂”方法，可以用来构造其子类实例</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Stack</td> 
 <td style="vertical-align:bottom;">不可变的LIFO（后入先出）栈</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Stream</td> 
 <td style="vertical-align:bottom;">对元素惰性求值的列表，可以支持拥有无限个潜在元素的序列</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">TreeMap</td> 
 <td style="vertical-align:bottom;">不可变映射表，底层用红黑树实现，操作的复杂度为O(log(n))</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">TreeSet</td> 
 <td style="vertical-align:bottom;">不可变集合，底层用红黑树实现，操作的复杂度为O(log(n))</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:bottom;">Vector</td> 
 <td style="vertical-align:bottom;">不可变、支持下标的序列的默认实现</td> 
 </tr> 
 </tbody> 
</table>

## 6 scala.collection.mutable包 ##

有些时候你需要一个在单线程操作中的可变集合类型。我们已经讨论了不可变集合为何应该成为默认选项的问题。对这些集合做可变操作不是线程安全的。然而，为了提高性能等原因，有原则、谨慎地使用可变数据也是恰当的。

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:bottom;width:92pt;">AnyRefMap</td> 
 <td style="vertical-align:bottom;">为AnyRef 类型的键准备的映射表，采用开放地址法解决冲突。大部分操作通常都比HashMap 快</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">ArrayBuffer</td> 
 <td style="vertical-align:bottom;">内部用数组实现的缓冲区类，追加、更新与随机访问的均摊时间复杂度为O(1)，头部插入和删除操作的复杂度为O(n)</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">ArrayOps</td> 
 <td style="vertical-align:bottom;">Java 数组的包装类，实现了序列操作</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">ArrayStack</td> 
 <td style="vertical-align:bottom;">数组实现的栈，比通用的栈速度快</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">BitSet</td> 
 <td style="vertical-align:bottom;">内存效率高的非负整数集合</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">HashMap</td> 
 <td style="vertical-align:bottom;">基于散列表的可变版本的映射</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">HashSet</td> 
 <td style="vertical-align:bottom;">基于散列表的可变版本的集合</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">HashTable</td> 
 <td style="vertical-align:bottom;">用于实现基于散列表的可变集合的trait</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">ListMap</td> 
 <td style="vertical-align:bottom;">基于列表实现的映射</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">LinkedHashMap</td> 
 <td style="vertical-align:bottom;">基于散列表实现的映射，元素可以按其插入顺序进行遍历</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">LinkedHashSet</td> 
 <td style="vertical-align:bottom;">基于散列表实现的集合，元素可以按其插入顺序进行遍历</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">LongMap</td> 
 <td style="vertical-align:bottom;">键的类型为Long，基于散列表实现的可变映射，采用开放地址法解决冲突。大部分操作都比HashMap 快</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">Map</td> 
 <td style="vertical-align:bottom;">Map 特征的可变版，其伴随对象有apply 方法和其他“工厂”方法，可以用来构造List的子类实例</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">MultiMap</td> 
 <td style="vertical-align:bottom;">可变的映射，可以对同一个键赋以多个值</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">PriorityQueue</td> 
 <td style="vertical-align:bottom;">基于堆的，可变优先队列。对于类型为A 的元素，必须存在隐含的Ordering[A] 实例。</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">Queue</td> 
 <td style="vertical-align:bottom;">可变的FIFO（先入先出）队列</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">Seq</td> 
 <td style="vertical-align:bottom;">表示可变序列的trait，其伴随对象有apply 方法和其他“工厂”方法，可以用来构造List的子类实例</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">Set</td> 
 <td style="vertical-align:bottom;">声明了可变集合相关操作的trait，其伴随对象有apply 方法和其他“工厂”方法，可以用来构造List 的子类实例</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">SortedSet</td> 
 <td style="vertical-align:bottom;">表示可变集合的trait，包含一个可按特定排列顺序遍历元素的迭代器。其伴随对象有apply方法和其他“工厂”方法，可以用来构造List 的子类实例</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">Stack</td> 
 <td style="vertical-align:bottom;">可变的LIFO（后入先出）栈</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">TreeSet</td> 
 <td style="vertical-align:bottom;">可变集合，底层用红黑树实现，操作的复杂度为O(log(n))</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">WeakHashMap</td> 
 <td style="vertical-align:bottom;">可变的散列映射，引用元素时采用弱引用。当元素不再有强引用时，就会被删除。该类包装了WeakHashMap</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:bottom;">WrappedArray</td> 
 <td style="vertical-align:bottom;">Java 数组的包装类，支持序列的操作</td> 
 </tr> 
 </tbody> 
</table>

WrappedArray 与ArrayOps 差不多完全相同，差别仅在于它们各自返回Array 的方法上。对于ArrayOps，返回的是新的Array\[T\]，而WrappedArray 返回的是新的WrappedArray\[T\]。所以，如果用户需要Array，更适合用ArrayOps；但当用户并不关心这一点的时候，如果涉及序列转换，使用WrappedArray 会更加高效。这是因为WrappedArray 避免了ArrayOps中对数组的“打包”和“分拆”工作。

## 7 scala.collection.parallel包 ##

并行集合的思想是利用现代多核系统提供的并行硬件多线程。根据定义，任何可以并行指定的集合操作都可以利用这种并行性。具体地说，集合被分成多个片段，操作（如map）应用在各个片段上，然后将结果组合在一起，形成最终结果。也就是说，这里用了分而治之的策略。

在实践中，并行集合没有被广泛使用，因为在许多情况下，并行化的开销可能会掩盖它的优点，而且不是所有的操作都可以并行执行。开销包括线程调度、数据分块、以及最后对结果的合并。通常情况下，除非该集合规模极大，否则串行执行速度会更快。所以，一定要仔细评估真实世界里的场景，确定集合是否足够大，并行操作是否足够快，来让我们选择并行集合。

对于具体的并行集合类型，你可以直接用与非并行集合相同的惯例来实例化它，也可以对相应的非并行集合调用par 方法。并行集合的组合也与非并行集合类似。它们在scala.collection.parallel 包中具有共同的trait 和类，在immutable 子包中定义了相同的不可变具体集合，在mutable 子包中定义了相同的可变具体集合。

最后，有一点有必要理解，并行意味着嵌套操作的顺序是未定义的。考虑如下示例，我们将从1 到10 的数字连接起来放进一个字符串中：

object Test extends App {
      val t1 = ((1 to 30) fold "") ((s1, s2) => s"$s1-$s2")
      val t2 = ((1 to 30) fold "") ((s1, s2) => s"$s1-$s2")
      val t3 = ((1 to 30).par fold "") ((s1, s2) => s"$s1-$s2")
      val t4 = ((1 to 30).par fold "") ((s1, s2) => s"$s1-$s2")
      println(t1)
      println(t2)
      println(t3)
      println(t4)
    }

输出：

-1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-24-25-26-27-28-29-30
    -1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-24-25-26-27-28-29-30
    -1--2--3--4--5--6--7--8--9--10--11--12--13--14-15--16--17-18--19-20-21-22--23--24--25-26--27-28-29-30
    -1--2-3--4--5--6--7--8--9--10-11--12--13--14--15--16--17-18--19-20-21-22--23-24-25-26-27-28-29-30

t1与t2的计算过程是一样的，因为是单线程，所以结果也一样

t3与t4的计算过程是一样的，因为是多线程，所以结果有可能就一样

但对于求和运算，与多少个线程没关系：

object Test extends App {
      val t1 = (1 to 300) reduce (_ + _)
      val t2 = (1 to 300)reduce (_ + _)
      val t3 = (1 to 300).par reduce (_ + _)
      val t4 = (1 to 300).par reduce (_ + _)
      println(t1)
      println(t2)
      println(t3)
      println(t4)
    }

执行结果：

45150
    45150
    45150
    45150

[https_download.csdn.net_download_u014646662_10805074]: https://download.csdn.net/download/u014646662/10805074
[Link 1]: https://www.cbedai.net/u014646662
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ2NDY2NjI_size_16_color_FFFFFF_t_70]: /images/20220415/343007b3af18457096e609332d9994b5.png