Scala学习系列-集合1：集合概述

Posted on 2021-03-15 Edited on 2021-04-17 In scala Views:

(未完)

概述

collection					collection.immutable					collection.mutable
TraversableOnce
	Iterator
		BufferedIterator
	Traversable				Traversable					Traversable
		Iterable				Iterable					Iterable
			Seq				Seq					Seq
				LinearSeq				LinearSeq					LinearSeq
									<C>List					<C>MutableList
									<C>Stream					<C>LinkedList
									<C>Stack					<C>DoubleLinkedList
									<C>Queue
				IndexedSeq				IndexedSeq					IndexedSeq
									<C>Range					ResizableArray
									<C>Vector						<C>ArrayBuffer
														<C>ArrayStack
														<C>ArraySeq
														<C>StringBuilder
														<C>WrappedArray
													Buffer
														<C>ArrayBuffer
														<C>ListBuffer
													<C>Stack
			Set				Set					Set
				SortedSet				SortedSet					SortedSet
									<C>TreeSet					<C>TreeSet
									<C>BitSet					<C>BitSet
								<C>ListSet					<C>LinkedHashSet
								<C>HashSet					<C>HashSet
													<C>WeakHashSet
			Map				Map					Map
				SortedMap				SortedMap					SortedMap
									<C>TreeMap					<C>TreeMap
								<C>HashMap					<C>HashMap
								<C>ListMap					<C>ListMap
													<C>LinkedHashMap

以下，我们以Scala集合顶层包路径scala.collection中的特质来逐步展开介绍Scala中集合的整体框架。

TraversableOnce

集合可以是只遍历一遍的集合(Iterator)，也可以是可遍历多次的集合(Traversable)。TraversableOnce是集合的顶级模版特质，它存在的主要作用是消除Iterator 和 Traversable之间的重复代码。

TraversableOnce中实现了一些常用的方法，并且很多方法是通过def foreach[U](f: A => U): Unit来实现的。同时，其内还包含有其它几个抽象方法，由子特质Iterator和Traversable负责实现，其中：

特质Iterator的实例只能被遍历一次；
特质Traversable的实例可以被遍历多次；

Traversable

我们看Traversable的定义，它直接继承了特质TraversableLike，TraversableLike中定义了大量的实现方法用来提供对来自GenTraversable、TraversableOnce、GenericTraversableTemplate这三个特质中未实现的方法的支持。

trait Traversable[+A] extends TraversableLike[A, Traversable[A]]
                         with GenTraversable[A]
                         with TraversableOnce[A]
                         with GenericTraversableTemplate[A, Traversable] {
}

TraversableLike中唯一没有提供实现的方法是：def foreach[U](f: A => U): Unit，所以Traversable的子类中必须提供对该方法的实现。

详细API文档，可参考Scala Traversable API。

TraversableLike

TODO

Iterable

我们看特质Iterable的定义，它继承了特质Traversable，同时继承了特质IterableLike；特质IterableLike中定义的方法全部是通过其内部未实现的方法def iterator: Iterator[A]进行实现的，同时特质IterableLike中覆盖了特质IterableLike中的一些方法，这样对于特质Iterable而言，它实现了特质Traversable中方法的Iterator版本（比如，def foreach[U](f: A => U): Unit），之所以覆盖特质IterableLike中方法的实现，其中一个主要原因是使用iterator()方法实现的一些方法比IterableLike中方法可以提供更好的性能。

对于特质IterableLike未实现方法def iterator: Iterator[A]，Traversable的子类必须提供对该方法的实现。

trait Iterable[+A] extends Traversable[A]
                      with GenIterable[A]
                      with GenericTraversableTemplate[A, Iterable]
                      with IterableLike[A, Iterable[A]] {
}

详细API文档，可参考Scala Iterable API。

IterableLike

1	trait IterableLike[+A, +Repr] extends Any with Equals with TraversableLike[A, Repr] with GenIterableLike[A, Repr] {}

TODO

Seq&LinearSeq&IndexedSeq

TODO

Set

TODO

Map

TODO

具体的不可变集合类

List

Stream

Stack

Queue

Range

Vector

哈希字典树

红黑树

BitSet

ListMap

具体的可变集合类

ArrayBuffer

ListBuffer

ListBuffer提供了常量时间的往后追加和往前追加的操作。

StringBuilder

LinkedList

DoubleLinkedList

MutableList

Queue

ArraySeq

Stack

ArrayStack

HashMap

WeakHashMap

ConcurrentHashMap

BitSet

集合之间的转换

集合转换为列表或数组

需要注意，转换成列表或数组通常需要将集合的所有元素做拷贝，因此对于大型集合来说可能会比较耗时。

可变集合与不可变集合之间转换

通常采用的方法是：首先，创建一个空的目标类型的集合，然后使用++或++=进行添加。

1
2
3

val colors = List("blue", "yellow", "red", "green")
val treeSet = immutable.TreeSet[String]() ++ colors
val mutaSet = mutable.Set.empty ++= treeSet

1 2	val muta = mutable.Map("i" -> 1, "ii" -> 2) val immu = Map.empty ++ muta

Notes

本文基于Scala2.12.13