讀古今文學網 > Java程序員修煉之道 > 9.5 數據結構和集合 >

9.5 數據結構和集合

你已經見過一個簡單的Scala數據結構List了。它在任何編程語言中都是一個基本的數據結構，在Scala中也不例外。我們會花點時間探究一下List的細節，然後去研究一下Map。

接著我們會認真研究一下Scala中的泛型，包括與Java泛型的差別及Java泛型所不具備的能力。我們會以一些標準的Scala集合為例展開討論，以便讓你瞭解其原理。

先從Scala集合的幾個一般性原則開始，特別是跟它的不可變性和它與Java集合的交互性相關的原則。

9.5.1　List

Scala中集合的實現方式跟Java很不一樣。你可能會有點吃驚，因為在很多其他領域，Scala都在重用和擴展Java的組件、概念。

我們來看看Scala的理念所帶來的最大差異：

  • Scala集合通常都是不可變的；

  • Scala把跟列表類似的集合的方方面面分解成了不同的概念；

  • Scala構建List核心所涉及的概念非常少；

  • Scala集合的實現方式是不同類型的集合提供的用戶體驗是一致的；

  • Scala鼓勵開發人員構建自己的集合類，並讓它們用起來像內置的集合類一樣。

我們會逐一討論這些差異。

1. 不可變和可變集合

你首先要知道，Scala的集合既有不可變的版本，也有可變的版本，並且不可變版本是默認的（所有Scala源文件都可以隨時訪問）。

我們需要分辨可變集合和可變內容之間的本質區別。請看代碼清單9-8。

代碼清單9-8　可變和不可變 

import scala.collection.mutable.LinkedList
import scala.collection.JavaConversions._
import java.util.ArrayList

object ListExamples {
  def main(args : Array[String]) {
    var list = List(1,2,3)   
    list = list :+ 4  ﹃列表追加方法
    println(list)

    val linklist = LinkedList(1,2,3)    
    linklist.append(LinkedList(4)) ﹄列表追加方法
    println(linklist)

    val jlist = new ArrayList[String]
    jlist.add(\"foo\")
    val slist = jlist.toList
    println(slist)
  }
}

如上所示，list的引用是可變的（是var）。它指向一個不可變列表實例，所以可以通過重新賦值指向新對象。:+方法返回一個新的（不可變）List實例，這個新實例中含有新追加的元素。

相反，linklist是指向一個LinkedList的不可變引用（是val），而LinkedList實例是可變的。linklist的內容可以修改，比如在其上調用append。這種區別如圖9-4所示。

圖9-4　不可變和可變集合

代碼清單9-8中還演示了一組轉換函數：用來對Java集合和相應的Scala集合進行相互轉換的JavaConversions類。

2. List的特質

Scala選擇強調集合的特質和行為，這是它與眾不同的另一個重要之處。我們以Java的ArrayList為例。除了Object，這個類還直接或間接地擴展了：

  • java.util.AbstractList；
  • java.util.AbstractCollection。

還有接口，ArrayList或它的某個父類實現了表9-2中列出的接口。

表9-2　ArrayList實現的Java接口

SerializableCloneableIterable CollectionListRandomAccess

對於Scala，情況要稍微複雜一點。以LinkedList為例，與它提供的功能相關的類或特質多達27個，如表9-3所示。

表9-3　LinkedList實現的Scala接口

SerializableLinkedListLikLinearSeq LinearSeqLikeCloneableSeq SeqLikeGenSeqGenSeqLike PartialFunctionFunction1Iterable IterableLikeEqualsGenIterable CollectionListRandomAccess GenIterableLikeMutableTraversable GenTraversableGenTraversableTemplateTraversableLike GenTraversableLike ParallelizableTraversableOnce

Scala的集合類彼此之間的差異並不像Java那麼明顯。在Java中，List、Map、Set等，根據使用時的具體類型會有不同的處理模式。但在Scala中，由於使用了特質，類型的細化程度要比Java高得多。因此你可以把注意力放在集合的各種性質上，使用更加貼近需求的類型精確表達你的意圖。

因此，Scala的集合處理代碼要比Java的看起來更加整齊。

Scala中的set

如你所料，Scala既支持不可變的set，也支持可變set。set的典型用法跟Java裡的模式一樣：用一個中間對像按順序遍歷集合中的元素。但Java用的是Iterator或Iterable，而Scala用Traversable，它跟Java類型之間不能互操作。

構建列表的兩個基礎是：Nil表示空列表，::操作符能從已有的列表構建新列表。::操作符的發音是cons，它和Clojure的(concat)函數（見第10章）還有關係。這兩者都表明Scala植根於函數式編程——最終可以追溯到Lisp中。

cons操作符有兩個參數：一個類型為T的元素和一個類型為List[T]的對象。它會把兩個參數合到一起創建一個新的List[T]值： 

scala> val x = 2 :: 3 :: Nil
x: List[Int] = List(2, 3)

另外，也可以直接這樣寫： 

scala> val x = List(2, 3)
x: List[Int] = List(2, 3)

scala> 1 :: x
res0: List[Int] = List(1, 2, 3)

cons操作符和括號

按cons操作符的定義，A :: B :: C的含義是沒有歧義的，它的意思是A :: (B :: C)。這是因為::的第一個參數是單個類型為T的值。但A :: B是類型為List[T]的值，所以(A :: B) :: C作為可能的值沒有任何意義。學院派的計算機科學家會說::是右相關性的。

這也解釋了為什麼要寫成2 :: 3 :: Nil，而2 :: 3不行。::的第二個參數需要是List類型的值，而3不是List。

9.5.2　Map

映射也是一種經典的數據結構。Java最常見的就是它的HashMap。在Scala中，不可變的Map類是默認形態，而HashMap是標準的可變形態。

代碼清單9-9中有幾種簡單、標準的映射定義和操作。

代碼清單9-9　Scala中的Map 

import scala.collection.mutable.HashMap

var x = Map(1 -> \"hi\", 2 -> \"There\")
for ((key, vau) <- x) println(key + \": \" + vau)
x = x + (3 -> \"bye\")

val hm = HashMap(1 -> \"hi\", 2 -> \"There\")
hm += (3 -> \"bye\")
println(hm)

看到了吧，Scala定義映射字面值的語法簡潔可愛：Map(1 ->\"hi\", 2 -> \"There\")。用箭頭符號直觀地表明了每個鍵「指向」的值。要從映射中取回值，請用get方法，跟Java一樣。

可變和不可變映射都用+表示向映射中添加元素（-表示移除）。但這個有些微妙，當用在可變映射上時，+修改映射然後返回它。而用在不可變實例上時，返回的是一個包含新的鍵/值對的新映射。這會導致+=操作符出現以下邊界情況： 

scala> val m = Map(1 -> \"hi\", 2 -> \"There\", 3 -> \"bye\", 4 -> \"quux\")
m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> hi, 2 -> There, 3 -> bye, 4 -> quux)

scala> m += (5 -> \"Blah\")
<console>:10: error: reassignment to val
                    m += (5 -> \"Blah\")
                             ^

scala> val hm = HashMap(1 -> \"hi\", 2 -> \"There\", 3 -> \"bye\", 4 -> \"quux\")
hm: scala.collection.mutable.HashMap[Int,java.lang.String] = Map(3 -> bye, 4 -> quux, 1 -> hi, 2 -> There)

scala> hm += (5 -> \"blah\")
res6: hm.type = Map(5 -> blah, 3 -> bye, 4 -> quux, 1 -> hi, 2 -> There)

這是因為+=在不可變和可變映射中的實現是不一樣的。對於可變映射，+=是一個方便修改映射的方法。這就是說在一個val映射上調用這個方法完全合法（就像Java在final HashMap上調用put一樣）。對於不可變映射，+=被分解成=和+的組合，就像在代碼清單9-9里一樣。它不能用在val上，因為val不允許再次賦值。

代碼清單9-9中還有一個不錯的語法：for循環。這用到了列表推導式（見9.3.5節）的思想，但結合了把鍵值對拆分成鍵和值的做法。這稱為對解構，是Scala中另一個繼承自函數式編程的概念。

對於Scala中的映射和它們的能力，我們僅僅觸及了冰山一角，但我們要前往下一個主題了：泛型。

9.5.3　泛型

你已經知道了，Scala用方括號表示參數化類型，而且你也已經見過一些基本的Scala數據結構了。我們繼續深入，看看Scala對泛型的處理方式跟Java有什麼不同。

首先，如果在定義函數的參數類型時忽略掉了泛型，看看會發生什麼： 

scala> def junk(x : List) = println(\"hi\")
<console>:5: error: type List takes type parameters
        def junk(x : List) = println(\"hi\")
                     ^

在Java中，這是完全合法的。編譯器可能會抱怨，但不會報錯。而在Scala中，這是一個編譯時錯誤。列表（和其他泛型）必須參數化——故事講完了，Scala沒有Java「生類型」的概念。

1. 泛型的類型推斷

把泛型賦值給一個變量時，Scala會對類型參數做出恰當的類型推斷。這符合Scala一貫堅持的類型推斷和盡可能去掉套路化代碼的風格： 

scala> val x = List(1, 2, 3)
x: List[Int] = List(1, 2, 3)

Scala泛型中有個特性乍一看可能覺得奇怪，我們用:::操作符演示一下，看到下面兩個列表聯接起來產生了新的列表，你就明白為什麼說它奇怪了： 

scala> val y = List(\"cat\", \"dog\", \"bird\")
y: List[java.lang.String] = List(cat, dog, bird)
scala> x ::: y
res0: List[Any] = List(1, 2, 3, cat, dog, bird)

奇怪吧，這樣居然都不報錯，還產生了新的List。運行時產生了一個Int和String的最小公父類（Any）的列表。

2. 泛型示例：候診的寵物

假設有些寵物在等著看獸醫，而你要建立候診室裡排隊隊列的模型。代碼清單9-10是個不錯的起點，用的是一些你已經熟悉的基礎類和輔助函數。

代碼清單9-10　候診的寵物 

class Pet(name : String)
class Cat(name : String) extends Pet(name : String)
class Dog(name : String) extends Pet(name : String)
class BengalKitten(name : String) extends Cat(name : String)

class Queue[T](elts : T*) {
  var elems = List[T](elts : _* )  //需要類型提示
  def enqueue(elem : T) = elems ::: List(elem)
  def dequeue = {
    val result = elems.head
    elems = elems.tail
    result
  }
}

def examine(q : Queue[Cat]) {
  println(\"Examining: \" + q.dequeue)
}

我們來考慮一下在Scala提示符中怎麼使用這些類。這些是最簡單的例子： 

scala> examine(new Queue(new Cat(\"tiddles\")))
Examining: line5$object$$iw$$iw$Cat@fb0d6fe

scala> examine(new Queue(new Pet(\"george\")))
<console>:10: error: type mismatch;
    found : Pet
    required: Cat
        examine(new Queue(new Pet(\"george\")))
                                    ^

到目前為止都很像Java。我們再多做幾個簡單的例子： 

scala> examine(new Queue(new BengalKitten(\"michael\")))
Examining: line7$object$$iw$$iw$BengalKitten@464a149a

scala> var kitties = new Queue(new BengalKitten(\"michael\"))
kitties: Queue[BengalKitten] = Queue@2976c6e4

scala> examine(kitties)
<console>:12: error: type mismatch;
  found : Queue[BengalKitten]
  required: Queue[Cat]
        examine(kitties)
                 ^

這也相當平常。第一個例子沒有將kitties作為臨時變量，Scala的類型推斷把隊列的類型作為Queue[Cat]，並接受了michael的加入，因為它的類型是Cat的子類BengalKitten。第二個例子中，創建了變量kitties，顯式聲明了其類型。也就是說Scala不能用類型推斷，所以不能接受類型不匹配的參數。

接下來我們去看看如何用類型系統的類型變體解決這些類型問題，特別是協變（類型變體還有其他形態，但協變最常用）。在Java中，這非常靈活，但也有點神秘。Scala和Java的做法我們都會演示一下。

3. 協變

「在Java中，List<String>是List<Object>的子類嗎？」如果你問過類似問題，那這個話題就是為你準備的。

默認情況下，Java對這個問題的回答是「不是」，但你可以讓它變成「是」。要知道怎麼做，請看下面的代碼： 

public class MyList<T> {
  private List<T> theList;
}

MyList<Cat> katzchen = new MyList<Cat>;
MyList<? extends Pet> petExt = petl;

? extends Pet從句表示petExt是一個部分未知的類型參數（Java類型中的?讀作「未知」）。可以確定的是MyList的類型參數必須是Pet或Pet的子類。這樣在將類型參數為其子類的值賦給 petExt時，Java編譯器就不會阻攔。

這就相當於把MyList<Cat>變成了MyList<? extends Pet>的子類。注意，這種子類關係是在使用MyList類型時建立起來的，而不是定義時。類型的這個特性稱為協變。

Scala的做法跟Java不同。它不是在使用類型時定義類型變體，而是在類型聲明時顯式指定協變。這樣做有幾個優勢：

  • 編譯器可以在編譯時檢查不符合協變的使用；

  • 所有概念上的思慮都交給了類型編寫者，而不是拋給類型的使用者；

  • 這樣可以在基礎集合類型間植入直觀的關係。

理論上來說，這樣的確不如Java那樣使用現場的變體更靈活，但在實際應用中，Scala採取的方式所帶來的好處完全可以抵消這種不便。大多數程序員很少會使用Java泛型中那些真正先進的特性。

Scala的標準集合，比如List，都實現了協變。這就是說List[BengalKitten]是List[Cat]的子類，而它又是List[Pet]的子類。我們來實際操練一下，請啟動解釋器： 

scala> val kits = new BengalKitten(\"michael\") :: Nil
kits: List[BengalKitten] = List(BengalKitten@71ed5401)

scala> var katzen : List[Cat] = kits
katzen: List[Cat] = List(BengalKitten@71ed5401)

scala> var haustieren : List[Pet] = katzen
haustieren: List[Pet] = List(BengalKitten@71ed5401)

我們在var上顯式聲明了類型，以免Scala把類型推斷得過窄。

對Scala泛型的簡略探討到這裡就結束了。下一個大主題是Scala在並發實現方式上的創新：放棄了多線程顯式管理的方式，而選用了actor模型。

    Java程序員修煉之道