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

image.png
  • 集合性能对比
  • 多少集合通过 scala.collection.JavaConverters 可与 Java 集合互相转换
  • 集合区分 generic(scala.collection)、mutable(scala.collection.mutable) 和 immutable(scala.collection.immutable)
    • 如果未明确导入包或使用包路径,默认使用 immutable
  • 集合 traitclass 的伴生对象中,都有 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 中查找元素远快于在 ArrayList 中查找
  • Map 键值对集合,scala.Predef 提供了隐式转换,可直接使用 key -> value 表示 (key, value)
    • SortedMap 按 key 排序

Immutable

file
  • Vector 带下标的集合,支持快速的随机访问,相当于 不可变的 ArrayBuffer

    • 通过高分叉因子的树实现,每个节点包含 32 个元素或子节点
    • 在快速随机选择和快速随机更新之间保持平衡
    • 弥补 List 在随机访问上的缺陷
  • Range 有序的整型集合,步长一致

    • 1 to 10 by 3 即生成 1 到 10 的序列,步长为 3
    • util 不包含上边界,to 包含上边界
    • 不存储实际值,只保存 start, end, step 三个值
  • List 有限的不可变序列

    • 为空 Nil,或包含两部分 head 元素和 tail (子 List)
    • :: 根据给定 headtail 构建新的 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 要慢,因此使用较少
      • 只有在获取第一个元素较频繁时才比较有优势 (即 Listhead)
  • StreamList 类似,但其元素都是延迟计算

    • 长度无限制
    • 只有请求的元素会被计算
      • 可通过 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

    • 包含一个 arraysize (继承自 ResizableArray)
    • 多数操作速度与 Array 相同
    • 可向尾部添加元素 (恒定分摊时间,对于更大的集合也可以高效的添加元素)
  • ListBuffer,类似于 ArrayBuffer 但是基于链表实现

  • LinkedList

    • 元素包含指向下一元素的链接
    • 空链表元素自己指向自己
  • LinkedHashSet 除了 Hash 的特点外,会记录元素插入的顺序

  • mutable.Queue

    • += 添加单个元素;++= 添加多个元素
    • dequeue 移除并返回队首元素
  • mutable.Stack 与不可变版本相同,除了会对原数据发生修改

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,874评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,102评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,676评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,911评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,937评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,935评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,860评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,660评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,113评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,363评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,506评论 1 346
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,238评论 5 341
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,861评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,486评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,674评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,513评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,426评论 2 352

推荐阅读更多精彩内容

  • Scala的集合类可以从三个维度进行切分: 可变与不可变集合(Immutable and mutable coll...
    时待吾阅读 5,812评论 0 4
  • 数组 :new Array[Int](8)与Array[Int](8)的区别:第一种8个元素,第二个定义一个值为8...
    夙夜M阅读 1,767评论 1 2
  • 可变和不可变集合 Scala中的集合可分为可变集合和不可变集合。可变集合可以当场被更新,不可变集合本身是不可变的。...
    liqing151阅读 210评论 0 0
  • 函数式编程 引言 Scala中的函数是Java中完全没有的概念。因为Java是完全面向对象的编程语言,没有任何面向...
    义焃阅读 1,276评论 2 5
  • scala学习笔记 第2章 变量和数据类型 基本数据 scala的核心数据为四种 :字面量、值、变量、类型 值使...
    485b1aca799e阅读 2,121评论 0 1