Scala Data Structure

arrays

• array 固定长度；arraybuffer 可变长度
  • arr.tobuffer, buf.toarray
• 初始化是不要使用 new
• 使用 () 访问元素
• 使用 for (elem <- arr) 遍历元素；倒序 arr.reverse
• 使用 for (elem <- arr if ...) ... yield ... 转换为新的数组
  • 等价于 arr.filter(...).map(...) 或者更简洁 arr filter { ... } map {...}
• 与 java 的数组通用，如果是 arraybuffer， 可配合 scala.collection.javaconversions 使用
• 在做任何操作前都会转换为 arrayops 对象
• 构建多维数组
  • val matrix = array.ofdim[double](3, 4) // 3 行 4 列

maps & tuples

• 创建、查询、遍历 map 的语法便捷
  • val scores = map("a" -> 100, "b" -> 90, "c" -> 95) 创建的默认为 immutable 的 hash map
  • 可变的 map 需要显式指定 scala.collection.mutable.map
  • 创建空的 map 需指定类型 new scala.collection.mutable.hashmap[string, int]
  • map 是键值对的集合，键值对类型可不相同
    • "a" -> 100 等价于 ("a", 100)；创建的另一种写法 map(("a", 100), ("b", 90), ("c", 95))
  • 访问
    • scores("a") //返回 option
    • scores("d").getorelse(0) // 返回实际值
  • mutable 更新
    • 更新值 scores("a") = 80
    • 增加元素 scores += ("d" -> 70, "e" -> 50)
    • 删除元素 scores -= "a"
  • immutable 不可更新，修改时会产生新的 map， 但公共部分的元素数据是共享的
    • 添加元素会产生新的 map，scores + ("d" -> 70, "e" -> 50)
    • 删除元素产生新的 map scores - "a"
  • 遍历 for((k,v) <- map) ...
  • 排序 map
    • 按照 key 排序存放 scala.collection.immutable.sortedmap("d" -> 1, "b" -> 2, "c" -> 3) // map(b -> 2, c -> 3, d -> 1)
    • 按照插入顺序排放 scala.collection.mutable.linkedhashmap("d" -> 1, "b" -> 2, "c" -> 3) // map(d -> 1, b -> 2, c -> 3)
• 区分 mutable 和 immutable
• 默认 hash map，也可使用 tree map
• 与 java 中的 map 转换方便 scala.collection.javaconverters
  • 在很多时候需要使用 java 的接口完成任务，但是处理结果时可转换为 scala 的数据接口来处理更方便，如文件操作等
• tuples 在聚合操作时很有用
  • map 中的键值对就是最简单的元组形式 (k, v)
  • 类型不必一致 val a = (1, 3.14, "hello")
  • 下标访问 a._1 // 1
  • 模式匹配访问 val (first, second, _) = a
  • 用于返回多个值
• zipping
  • 元组可用于绑定多个值同时处理
  • zip 方法

collections

• 多少集合通过 scala.collection.javaconverters 可与 java 集合互相转换
• 集合区分 generic(scala.collection)、mutable(scala.collection.mutable) 和 immutable(scala.collection.immutable)
  • 如果未明确导入包或使用包路径，默认使用 immutable
• 集合 trait 或 class 的伴生对象中，都有 apply 方法，可直接构造集合实例，如 array(1,2,3)
• traversable 集合层级的顶部，只有 foreach 方法是抽象的，其他方法都可直接继承使用
• iterable ，只有 iterator 方法是抽象的，其他方法都可直接继承使用
  • 与 traversable 的区别在于，iterator （可选择获取下一个元素的时间，在获取下一个元素之前会一直跟踪集合中的位置）
  • iterable 中的 foreach 通过 iterator 实现
• seq 有序序列，包含 length，有固定下标
  • indexedseq 快速随机访问，通过 vector 实现
  • linearseq 高效的 head/ tail 操作，通过 listbuffer 实现
• set 无序集合、无重复元素
  • 默认实现为 hashset，即元素其实是按照对应的哈希值排序的
    • 在 hashset 中查找元素远快于在 array 或 list 中查找
• map 键值对集合，scala.predef 提供了隐式转换，可直接使用 key -> value 表示 (key, value)
  • sortedmap 按 key 排序

immutable

• vector 带下标的集合，支持快速的随机访问，相当于 不可变的 arraybuffer
  • 通过高分叉因子的树实现，每个节点包含 32 个元素或子节点
  • 在快速随机选择和快速随机更新之间保持平衡
  • 弥补 list 在随机访问上的缺陷
• range 有序的整型集合，步长一致
  • 1 to 10 by 3 即生成 1 到 10 的序列，步长为 3
  • util 不包含上边界，to 包含上边界
  • 不存储实际值，只保存 start, end, step 三个值
• list 有限的不可变序列
  • 为空 nil，或包含两部分 head 元素和 tail (子 list)
  • :: 根据给定 head 和 tail 构建新的 list
    • 右结合性，即从右侧开始调用 1 :: 2 :: nil 等价于 1 :: (2 :: nil) // 结果 `list(1,2)

  • 根据 head, tail 的特性，可很容易进行递归操作

    def multi(l: list[int]): int = l match {
      case nil    => 1
      case h :: t => h * multi(t)
    }

  • 复杂度
    • 获取 head, tail 只需要常数时间 o(1)
    • 在头部添加元素也只需要常数时间 o(1)；可使用 mutable.listbuffer 可在头部 或 尾部进行增/删元素操作
    • 其他操作需要线性时间 o(n)

• sortedset 有序集合，按顺序访问元素，默认实现为红黑树

• immutable.bitset 非负整数集合，底层使用 long 数组存储
  • 用较小的整型表示较大的整型，如 3,2,0 二进制表示为 1101，即十进制的 13
• listmap
  • 通过键值对的 linkedlist 来表示 map
  • 多数情况下比标准的 map 要慢，因此使用较少
    • 只有在获取第一个元素较频繁时才比较有优势 (即 list 的 head)
• stream 与 list 类似，但其元素都是延迟计算的
  • 长度无限制
  • 只有请求的元素会被计算
    • 可通过 force 来强制进行计算所有元素
  • 通过 #:: 构造，1 #:: 2 #:: 3 #:: stream.empty 结果为 stream(1, ?) 此处只打印了 head 1，而 tail 未打印，因为还未计算 tail
• immutable.stack lifo 序列
  • push 入栈 , pop 出栈, top 查看栈顶元素
  • 很少使用，因为其操作都可以被 list 包括(push = ::, pop = tail, top = head)
• immutable.queue fifo 序列
  • enqueue 入列，可使用集合做参数，一次性入列多个元素
  • dequeue 出列，结果包含两部分 (element, rest)

mutable

• arraybuffer
  • 包含一个 array 和 size (继承自 resizablearray)
  • 多数操作速度与 array 相同
  • 可向尾部添加元素 (恒定分摊时间，对于更大的集合也可以高效的添加元素)

• listbuffer，类似于 arraybuffer 但是基于链表实现

• linkedlist
  • 元素包含指向下一元素的链接
  • 空链表元素自己指向自己

• linkedhashset 除了 hash 的特点外，会记录元素插入的顺序

• mutable.queue
  • += 添加单个元素；++= 添加多个元素
  • dequeue 移除并返回队首元素

• mutable.stack 与不可变版本相同，除了会对原数据发生修改

• mutable.bitset 直接修改原数据，更新操作比 immutable.bitset 更高效