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 更高效