十四、其它可变集合

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

ArrayBuffer 数组缓冲：数组缓冲包含一个数组和一个大小。对数组缓冲的大部分操作和数组的速度一样，因为这些操作只是简单地访问和修改底层的数组。
数组缓冲可以在尾部高效地添加数据，对数组缓冲追加数据需要的时间为平摊的 $ O(1) $ 时间。因此，数组缓冲对于那些通过向尾部追加新元素来构建大型集合的场景非常有用。
```
xxxxxxxxxx
val buf = collection.mutable.ArrayBuffer.empty[Int]
buf += 1
buf += 10
buf.toArray // Array[Int](1,10)
```
ListBuffer 列表缓冲：列表缓冲和数组缓冲很像，但是它内部使用的是链表而不是数组。如果你打算在构建完成之后，再将缓冲转换为链表，则可以考虑使用列表缓冲。
```
xxxxxxxxxx
val buf = collection.mutable.ListBuffer.empty[Int]
buf += 1
buf += 10
buf.toList // List[Int](1, 10)
```
StringBuilder ：用于构建字符串。由于它非常常用，因此已经被引入到默认的命名空间中。只需要简单地使用 new StringBuilder 就可以创建：
```
xxxxxxxxxx
val buf = new StringBuilder
buf += 'a'
buf ++= "bcdefg"
buf.toString // 转换为字符串
```
链表LinkedList：链表是由用 next 指针链接起来的节点组成的可变序列。
在大多数语言中，null 表示空链表，但是在 scala 中行不通。因为即使是空的链表也需要支持所有的链表操作（其它集合也是类似的）。尤其是 LinkedList.empty.isEmpty 应该返回 true ，而不是抛出 NullPointerException 异常。因此，空链表是特殊处理的：它们的 next 字段指向节点本身。
跟它的不可变版本一样，链表支持的最佳操作是顺序操作。不仅如此，在链表中插入元素或者其他链表非常容易。
双向链表 DoubleLinkedList ：和 LinkedList 很相似，只不过双向链表除了 next 指针之外，还有一个 prev 指针指向当前节点的前一个节点。这个额外的链接使得移除元素的操作非常快。
可变列表MutableList：可变列表由一个单向链表和一个指向该链表末端的空节点组成，这使得向链表尾部追加元素是 $ O(1) $ 复杂度的，因为它避免了遍历链表来找到末端的需要。
目前 Scala 的 mutable.LinearSeq 是采用 MutableList 来实现的。
队列 Queue ： scala 除了不可变队列之外还提供了可变队列。可以像使用不可变队列一样使用可变队列，不过不是用 enqueue 而是用 += 或 ++= 操作符来追加元素。
另外，对于可变队列而言，dequeue 方法只会简单地移除头部的元素并返回。
```
xxxxxxxxxx
val queue = new scala.collection.mutable.Queue[String]
queue += "a"
queue += List("b","c")
queue.dequeue // 返回 "a"，此时 queue 仅剩下元素 "b"，"c"
```
数组序列 ArraySeq：数组序列是固定大小的，内部使用 Array[AnyRef] 来存放元素的可变序列。
如果你想要数组的性能，但是又不想创建泛型的序列实例（你不知道元素类型，也没有一个可以在运行时提供类型信息的 ClassTag），可以选用 ArraySeq 。

栈 Stack：前面介绍了不可变的栈，可变的栈的工作机制和不可变版本一样，只是它的修改是原地的。


xxxxxxxxxx
val stack = new scala.collection.mutable.Stack[Int]
stack.push(1)
stack.push(2)
stack.top // 返回2， stack 元素还是 1,2
stack.pop // 返回2， stack 元素现在只有 1

数组栈 ArrayStack：它是可变栈的另一种实现，内部是一个 Array，在需要时重新改变大小。它提供了快速的下标索引，一般而言对于大多数操作而言都比普通的可变栈更快。
哈希表 HashMap（也叫哈希映射）：哈希表底层用数组存放其元素，元素的存放位置取决于该元素的哈希码。
向哈希表中添加元素只需要 $ O(1) $ 时间，只要数组中没有其他元素拥有相同的哈希码。因此，只要哈希表中的对象能够按照哈希码分布得足够均匀，哈希表的操作就非常快。正因为如此，scala 中默认的可变 Map 和可变 Set 的实现都是基于哈希表的。
```
xxxxxxxxxx
val map = collection.mutable.HashMap.empty[Int, String]
map += ( 1 -> "a")
map(1) // 返回 "a"
```
对哈希表的遍历并不能保证按照某个特定的顺序，遍历只不过是简单地遍历底层的数组，底层数组的顺序是什么样就是什么样。如果你需要某种有保障的迭代顺序，则可以使用链式的HashMap 或哈希HashSet ，而不是常规的 HashMap 或 HashSet 。
链式的 HashMap 或 HashSet 的区别在于：链式的版本额外包含了一个按照元素的添加顺序保存的元素链表。对这样的集合进行遍历，则总是按照元素添加的顺序来进行的。
弱哈希映射WeakHashMap：WeakHashMap 是一种特殊的HashMap ，对于这种HashMap，垃圾收集器并不会跟踪映射到其中的键的链接。这意味着：如果没有其他引用指向某个键，则该键和它关联值就会从映射中消失。
WeakHashMap 对于类似缓存这类的任务而言十分有用。如果缓存的 key -> value 是保存在常规的哈希映射当中，这个哈希映射就会无限增长，所有的键都不会被当做垃圾来处理。
使用弱哈希映射可以避免这个问题：一旦某个键对象不再使用，则该项就会从弱哈希表中移除。scala 中弱哈希表的实现是对底层 Java 实现 java.util.WeakHashMap 的包装。
并发映射ConcurrentHashMap：并发映射可以被多个线程同时访问。除了常见的Map 操作外，它还提供了如下原子操作：
- m putIfAbsent (k, v) ：除非 k 已经在 m 中，否则添加 k -> v 到 m 中。
- m remove(k, v)：如果 k 已经在 m 中，则移除该项。
- m replace( k, old, new)：如果 k 原先在 m 中且它对应的值为 old，则将 k 对应的值修改为 new。
- m replace(k, v)：如果 k 原先在 m 中，则将 k 对应的值修改为 v 。
并发映射是 Scala 标准类库中的一个特质。目前它唯一的实现是 Java 的 java.util.concurrent.ConcurrentHashMap ，通过标准的 Java/Scala 集合转换，可以自动转换为 Scala 映射。
可变位组 BitSet：可变位组和不可变位组一样，只是它可以原地修改。可变位组在更新方面比不可变位组效率稍高，因为它们不需要将那些没有改变的 Long 复制来复制去。
```
xxxxxxxxxx
val bits = scala.collection.mutable.BitSet.empty
bits += 1
bits += 3 
```