集合 (Scala 2.8 - 2.12)

具體不可變集合類別

過時公告

Scala 提供多種具體不變集合類別供您選擇。它們在實作的特質（映射、集合、序列）、是否可以是無限的，以及各種運算的速度上有所不同。以下是一些 Scala 中最常使用的不可變集合類型。

清單

一個清單是有限的不變序列。它們提供常數時間存取其第一個元素以及清單的其餘部分，並且它們有一個常數時間 cons 運算，用於將新元素新增到清單的前面。許多其他運算需要線性時間。

清單一直是 Scala 程式設計的要角，因此這裡不需要對它們多做說明。2.8 中的主要變更在於 List 類別及其子類別 :: 及其子物件 Nil 現在定義在套件 scala.collection.immutable 中，這才是它邏輯上應該存在的地方。在 scala 套件中仍然有 List、Nil 和 :: 的別名，因此從使用者的角度來看，清單可以像以前一樣存取。

另一個變更在於清單現在更緊密地整合到集合架構中，而且不像以前那樣是一個特例。例如，原本存在於 List 伴隨物件中的所有方法都已標示為不建議使用。它們已被每個集合繼承的統一建立方法取代。

串流

一個串流類似於清單，但其元素是以延遲運算的方式計算的。因此，串流可以無限長。只有那些被要求的元素才會被計算。否則，串流具有與清單相同的效能特性。

列表是用 :: 算子建構的，串流是用看起來相似的 #:: 建構的。以下是包含整數 1、2 和 3 的串流的簡單範例

scala> val str = 1 #:: 2 #:: 3 #:: Stream.empty
str: scala.collection.immutable.Stream[Int] = Stream(1, ?)

此串流的頭部是 1，尾部有 2 和 3。不過，尾部在此處不會列印出來，因為它尚未計算！串流會設定為延遲計算，而串流的 toString 方法會小心避免強制進行任何額外的評估。

以下是一個更複雜的範例。它會計算一個串流，其中包含從給定的兩個數字開始的費氏數列。費氏數列是一個數列，其中每個元素都是數列中前兩個元素的總和。

scala> def fibFrom(a: Int, b: Int): Stream[Int] = a #:: fibFrom(b, a + b)
fibFrom: (a: Int,b: Int)Stream[Int]

這個函數看似簡單，但其實不然。數列的第一個元素顯然是 a，而數列的其餘部分是從 b 開始的費氏數列，後面接著 a + b。棘手的部分是計算此數列時不會造成無限遞迴。如果函數使用 :: 而不是 #::，則每次呼叫函數都會導致另一個呼叫，從而造成無限遞迴。不過，由於它使用 #::，因此在要求之前不會評估右側。以下是從兩個 1 開始的費氏數列的前幾個元素

scala> val fibs = fibFrom(1, 1).take(7)
fibs: scala.collection.immutable.Stream[Int] = Stream(1, ?)
scala> fibs.toList
res9: List[Int] = List(1, 1, 2, 3, 5, 8, 13)

向量

當處理它們的演算法小心地只處理它們的頭部時，列表非常有效率。存取、新增和移除列表的頭部只需要常數時間，而存取或修改列表中後面的元素則需要與列表深度成線性的時間。

Vector 是一種集合類型（Scala 2.8 中引入），用於解決清單中隨機存取的低效率問題。Vector 允許在「有效」恆定時間內存取清單中的任何元素。這是一個比存取清單開頭或讀取陣列元素更大的恆定值，但它仍然是一個恆定值。因此，使用 Vector 的演算法不必小心只存取序列的開頭。它們可以存取和修改任意位置的元素，因此寫起來可以更方便。

Vector 的建立和修改方式與任何其他序列相同。

scala> val vec = scala.collection.immutable.Vector.empty
vec: scala.collection.immutable.Vector[Nothing] = Vector()
scala> val vec2 = vec :+ 1 :+ 2
vec2: scala.collection.immutable.Vector[Int] = Vector(1, 2)
scala> val vec3 = 100 +: vec2
vec3: scala.collection.immutable.Vector[Int] = Vector(100, 1, 2)
scala> vec3(0)
res1: Int = 100

Vector 以具有高分支因子的樹狀結構表示（樹狀結構或圖形的分支因子是每個節點的子節點數量）。每個樹狀節點最多包含 32 個 Vector 元素，或最多包含 32 個其他樹狀節點。最多包含 32 個元素的 Vector 可以表示在單一節點中。最多包含 32 * 32 = 1024 個元素的 Vector 可以表示為單一間接引用。從樹狀結構的根節點到最後一個元素節點的兩次跳躍足以表示最多包含 2¹⁵ 個元素的 Vector，三次跳躍表示最多包含 2²⁰ 個元素的 Vector，四次跳躍表示最多包含 2²⁵ 個元素的 Vector，五次跳躍表示最多包含 2³⁰ 個元素的 Vector。因此，對於所有合理大小的 Vector，元素選取最多涉及 5 次基本陣列選取。這就是我們在寫元素存取是「有效恆定時間」時的意思。

Vector 是不可變的，因此您無法變更 Vector 的元素，並仍然保留新的 Vector。不過，使用 updated 方法，您可以建立一個新的 Vector，它只在單一元素中與既有的 Vector 不同

scala> val vec = Vector(1, 2, 3)
vec: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)
scala> vec updated (2, 4)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4)
scala> vec
res1: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)

如上所示的最後一行，呼叫 updated 對原始向量 vec 沒有影響。與選取類似，函式向量更新也是「有效地恆定時間」。更新向量中間的元素，可以透過複製包含該元素的節點，以及指向該節點的每個節點，從樹的根節點開始。這表示函式更新會建立 1 到 5 個節點，每個節點包含最多 32 個元素或子樹。這當然比可變陣列中的就地更新昂貴，但仍然比複製整個向量便宜許多。

由於向量在快速隨機選取和快速隨機函式更新之間取得良好的平衡，因此它們目前是不可變索引序列的預設實作

scala> collection.immutable.IndexedSeq(1, 2, 3)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)

不可變堆疊

如果您需要最後進、第一出的序列，可以使用 Stack。您可以使用 push 將元素推入堆疊，使用 pop 彈出元素，並使用 top 查看堆疊頂端而不移除元素。所有這些操作都是恆定時間。

以下是對堆疊執行的一些簡單操作

scala> val stack = scala.collection.immutable.Stack.empty
stack: scala.collection.immutable.Stack[Nothing] = Stack()
scala> val hasOne = stack.push(1)
hasOne: scala.collection.immutable.Stack[Int] = Stack(1)
scala> stack
stack: scala.collection.immutable.Stack[Nothing] = Stack()
scala> hasOne.top
res20: Int = 1
scala> hasOne.pop
res19: scala.collection.immutable.Stack[Int] = Stack()

在 Scala 程式中很少使用不可變堆疊，因為其功能已被清單取代：不可變堆疊上的 push 與清單上的 :: 相同，而堆疊上的 pop 與清單上的 tail 相同。

不可變佇列

一個 Queue 就如同一個堆疊，只不過它是先進先出，而不是後進先出。

以下是建立一個空的不可變佇列的方法

scala> val empty = scala.collection.immutable.Queue[Int]()
empty: scala.collection.immutable.Queue[Int] = Queue()

你可以使用 enqueue 將一個元素附加到一個不可變佇列

scala> val has1 = empty.enqueue(1)
has1: scala.collection.immutable.Queue[Int] = Queue(1)

若要將多個元素附加到一個佇列，請呼叫 enqueue，並將一個集合作為其引數

scala> val has123 = has1.enqueue(List(2, 3))
has123: scala.collection.immutable.Queue[Int]
  = Queue(1, 2, 3)

若要從佇列的頭部移除一個元素，請使用 dequeue

scala> val (element, has23) = has123.dequeue
element: Int = 1
has23: scala.collection.immutable.Queue[Int] = Queue(2, 3)

請注意，dequeue 會傳回一個包含已移除元素和佇列其餘部分的配對。

範圍

一個 Range 是一個等距的整數有序序列。例如，「1、2、3」是一個範圍，「5、8、11、14」也是一個範圍。若要在 Scala 中建立一個範圍，請使用預先定義的方法 to 和 by。

scala> 1 to 3
res2: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3)
scala> 5 to 14 by 3
res3: scala.collection.immutable.Range = Range(5, 8, 11, 14)

如果你想要建立一個不包含其上限的範圍，請使用便利方法 until，而不是 to

scala> 1 until 3
res2: scala.collection.immutable.Range = Range(1, 2)

範圍以常數空間表示，因為它們可以用三個數字定義：它們的開始、結束和步進值。由於這個表示，範圍上的大多數運算都非常快。

雜湊嘗試

雜湊嘗試是實作不可變集合和映射的標準方式。它們受類別 immutable.HashMap 支援。它們的表示類似於向量，因為它們也是樹，其中每個節點有 32 個元素或 32 個子樹。但現在這些金鑰的選取是根據雜湊碼進行的。例如，要在映射中找到給定的金鑰，首先取得金鑰的雜湊碼。然後，雜湊碼的最低 5 位元用於選取第一個子樹，接著是下一個 5 位元，依此類推。選取會在節點中儲存的所有元素的雜湊碼在已選取到此層級的位元中彼此不同時停止。

雜湊嘗試在相當快速的查詢和相當有效率的功能插入 (+) 和刪除 (-) 之間取得良好的平衡。這就是它們成為 Scala 不可變映射和集合預設實作的原因。事實上，Scala 對包含少於五個元素的不可變集合和映射進一步最佳化。包含一到四個元素的集合和映射儲存為單一物件，其中僅包含元素（或在映射的情況下為金鑰/值對）作為欄位。空的不可變集合和空的不可變映射在每個情況下都是單一物件 - 不需要為它們重複儲存，因為空的不可變集合或映射將永遠保持為空。

紅黑樹

紅黑樹是一種平衡二元樹，其中一些節點指定為「紅色」，而另一些節點指定為「黑色」。與任何平衡二元樹一樣，對它們的操作可靠地以樹大小的對數時間完成。

Scala 提供了使用紅黑樹的不可變集合和映射的實作。在名稱 TreeSet 和 TreeMap 下存取它們。

scala> scala.collection.immutable.TreeSet.empty[Int]
res11: scala.collection.immutable.TreeSet[Int] = TreeSet()
scala> res11 + 1 + 3 + 3
res12: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 3)

紅黑樹是 Scala 中 SortedSet 的標準實作，因為它們提供了一個有效的迭代器，以排序順序傳回所有元素。

不可變位元集

BitSet 將小整數集合表示為較大整數的位元。例如，包含 3、2 和 0 的位元集將表示為二進制的整數 1101，十進制為 13。

在內部，位元集使用 64 位元 Long 陣列。陣列中的第一個 Long 用於整數 0 到 63，第二個用於 64 到 127，依此類推。因此，只要集合中最大的整數小於幾百個左右，位元集就會非常緊湊。

位元集上的操作非常快速。包含測試需要常數時間。將項目新增到集合需要與位元集陣列中的 Long 數量成正比的時間，這通常是一個小數字。以下是使用位元集的一些簡單範例

scala> val bits = scala.collection.immutable.BitSet.empty
bits: scala.collection.immutable.BitSet = BitSet()
scala> val moreBits = bits + 3 + 4 + 4
moreBits: scala.collection.immutable.BitSet = BitSet(3, 4)
scala> moreBits(3)
res26: Boolean = true
scala> moreBits(0)
res27: Boolean = false

清單映射

ListMap 將映射表示為鍵值對的連結清單。一般來說，對清單映射的操作可能必須遍歷整個清單。因此，對清單映射的操作需要與映射大小成線性的時間。事實上，Scala 中幾乎沒有使用清單映射，因為標準不可變映射幾乎總是更快。唯一的可能例外是，如果映射出於某種原因以清單中的第一個元素比其他元素更常被選取的方式建構。

scala> val map = scala.collection.immutable.ListMap(1->"one", 2->"two")
map: scala.collection.immutable.ListMap[Int,java.lang.String] =
   Map(1 -> one, 2 -> two)
scala> map(2)
res30: String = "two"