十三、其它不可变集合

发布于 2023-07-17 23:38:22 字数 9468 浏览 0 评论 0 收藏 0

Scala 提供了很多具体的不可变集合类，它们实现的特质各不相同（Map,Set,Sequence ），可以是无限的也可以是有限的。
List 是有限的不可变序列。它提供 $ O(1) $ 时间的对首个元素和剩余元素的访问，以及 $ O(1) $ 时间的在列表头部新增元素的操作。其它很多操作都是 $ O(n) $ 时间的。
Stream 和列表很像，不过其元素都是惰性的。因此，Stream 是无限长的，只有被请求到的元素才会被计算。除此之外，流的特性和List 是一样的。
- 列表通过 :: 操作符构造，而流是通过 #:: 来构造：
```
xxxxxxxxxx
val str = 1 #:: 2 #:: 3 #:: Stream.emtpy
```
  流的基本要求是惰性计算，因此它的 toString 方法并不会强制任何额外的求值计算，只会给出头部的结果。如上面的str 的 .toString 为 Stream(1. ?) 。
- 下面是一个更复杂的例子：
```
xxxxxxxxxx
def fibFrom(a: Int， b: Int): Stream[Int] =  a #:: fibFrom(b, a + b)
```
  需要说明的是：计算 Fibonacci 序列的同时不会引发无限递归。如果函数使用了 :: 而不是 #::，那么每次对fibFrom 的调用都会引发另一个调用，这样就会造成无限递归。不过由于它用的是 #:: ，因此表达式右边只会在被请求时才会被求值。如：
```
xxxxxxxxxx
val fibs = fibFrom(1，1).take(7) // 此时 fibs 还没有全部求值
fibs.toList // 此时 fibs 每个元素求值
```
Vector 是对头部之外的其它元素也提供 $ O(1) $ 复杂度访问的集合类型。但是，这个常量时间是 “从效果上讲的常量时间”。
向量的创建和修改和其它序列没有什么不同：
```
xxxxxxxxxx
val vec = Vector.empty
val vec2 = vec :+ 1 :+ 2
val vec3 = 100 +: vec2
```
- 向量的内部结构是宽而浅的树，树的每个顶点包含多达32 个元素、或 32 个子节点。
  - 小于等于 32 个元素的向量可以用单个结点来表示。
  - 小于等于 32 x 32 = 1024 个元素的向量可以通过单次额外的间接跳转来访问。
- 如果我们允许从根部到叶子最多2跳，则向量可以包含多达 $ 2^{15} $ 个元素；如果允许最多 3 跳，则向量可以包含多达 $ 2^{25} $ 个元素。如果允许最多 5 跳，则向量可以包含多达 $ 2^{30} $ 个元素。
  因此对于所有正常大小的向量，选择一个元素只需要最多 5 次基本的数组操作。这就是我们说的“从效果上讲的常量时间”。
- 向量是不可变的，因此无法原地修改向量元素的值。不过，通过 updated 方法可以创建一个与给定向量在单个元素上有差异的新向量：
```
xxxxxxxxxx
val vec = Vector(1,2,3)
val vec2 = vec updated(2,4) // Vector(1,2,4)
```
  和选择操作一样，函数式向量的更新也是消耗“从效果上讲的常量时间”：更新向量中的某个元素可以通过拷贝包含该元素的结点、以及从根部开始到该结点路径上的所有结点，其它结点无需拷贝。
  这意味着一次函数式的向量更新只会创建出 1~5 个新的结点，其中每个结点包含 32 个元素或者子节点。这比可变数组的原地更新要更加昂贵，但是比起拷贝整个向量而言要便宜的多。
由于向量在快速的任意位置的索引，以及任意位置的函数式更新之间取得了较好的平衡，因此它们目前是不可变的带下标索引的序列IndexedSeq的默认实现。
immutable.Stack 是不可变的栈。可以使用 push 来压一个元素入栈；可以用 pop 来弹一个元素出栈；可以用 top 来查看栈顶的元素而不是将它弹出。所有这些操作都是常量时间。
```
xxxxxxxxxx
val stack = scala.collection.immutable.Stack.empty
val stack1 = stack.push(1)
```
不可变的栈在 Scala 中很少用到，因为它们的功能完全被List 包含。对不可变的栈的 push 操作对应于 List 的 :: 操作，对不可变的栈的 pop 操作对应于List 的 tail 操作。
immutable.Queue 是不可变的队列。可以用 enqueue 来追加一个元素或者一组元素，可以用 dequeue 来移除头部的元素（出队列）：
```
xxxxxxxxxx
val queue = scala.collection.immutable.Queue
val queue1 = queue.enqueue(1)
val queue2 = queue.enqueue(List(1,2,3))
val (ele,queue3) = queue.dequeue
```
注意：dequeue 返回的是一个包含被移除元素以及队列剩余部分的tuple 。
immutable.Range 是一个有序的整数序列，整数之间有相同的间隔。在Scala 中创建Range 的方法是to 和 by：
```
xxxxxxxxxx
val range1  = 1 to 3 // Range(1,2,3)
val range2 = 5 to 14 by 3 // Rnage(5,8,11,14)
```
其中 to 指定Range 的起止位置，by 指定Range 间隔。
如果需要创建的Range 不包含上限，则可以用 until 而不是 to：
```
xxxxxxxxxx
val range3 = 1 until 3 // Range(1,2)
```
Range 的内部表示占据了 $ O(1) $ 的空间，因为它只需要用三个数来表示：开始位置、结束位置、步长。因此大多数Range 操作非常快。
哈希字典树 Hash Trie：哈希字典树是实现高效的不可变Set 和不可变Map 的标准方式。它们的内部表现形式和向量类似，也是每个结点有 32个元素或 32棵子树的树，不过元素选择是基于哈希码的（而不是指针）。
举例来说：要想找到Map 中给定的键，首先用键的哈希码的最低5 位找到第一棵子树、然后用哈希码的下一个5 位找到第二棵子树，依次类推。当某个结点所有元素的哈希码（已用到部分）各不相同时，该选择过程就停止了。
哈希字典树在快速的查找、高效的函数式插入+ 、高效的函数式删除- 之间取得了不错的平衡。这也是为什么它是不可变Map 和不可变Set 默认的实现的原因。
实际上，Scala 对于元素少于5个的不可变Set 和不可变Map 还有进一步的优化：
- 带有 k（1<=k <=4) 个元素的Set 和 Map 采用的是包含对应 k个字段的单个对象，每个元素对应一个字段。
- 空的Set 和 Map 使用单例对象来表示。
红黑树：红黑树是一种平衡二叉树，某些结点标记为”红色“、某些结点标记为”黑色“。和其它平衡二叉树一样，对它们的操作可以可靠地在 $ O(\log n) $ 时间内完成。
Scala 的 TreeSet, TreeMap 的内部使用红黑树来实现，红黑树也是 SortedSet 的标准实现。
```
xxxxxxxxxx
val set = collection.immutable.TreeSet.empty[Int]
set +1 +3 +3
```
不可变位组bit set ：位组bit set 用于表示某个非负整数的bit 的集合。从内部讲，位组使用一个 Array[Long] 来表示。第一个Long （64位）表示整数 0~63 ，第二个Long 表示整数64~127，以此类推。
如果集合中最大整数在数百这个量级，则位组非常紧凑；如果集合中最大整数非常大，比如 100万，则它需要 1.00万/64 大约 1.6 万个Long 来表示。
对位组的操作非常快：测试某个整数是否在位组中只需要 $ O(1) $ 的时间；向位组中添加整数的时间复杂度和底层 Array[Long] 的长度成正比，而这个长度通常很小。
```
xxxxxxxxxx
val bitSet = scala.collection.immutable.BitSet.empty
val bitSet2 = bitSet ++ List(3,4,4,0)
// 内部表示为 Array[Long](25)。 3,4,4,0 用 bit 序列表示为 10011，我们从左到右某个 bit 为 1 代表该位置下标对应的整数出现。 10011 转换为十进制就是 25。
```
列表映射ListMap：将 Map 表示为一个由键值对构成的链表。一般而言，对ListMap 的操作需要遍历整个链表，因此对于 ListMap 的操作耗时为 $ O(n) $ 。
事实上Scala 对于 ListMap 用得很少，因为标准的不可变 Map 几乎总是比 ListMap 更快。唯一可能有区别的场景是：因为某种原因，需要经常访问List 的首个元素的频率远高于访问其它元素时。
```
xxxxxxxxxx
val map = collection.immutable.ListMap(1 -> "a", 2 -> "b")
map(1) // 返回 "a"
```