《Java程序员修炼之道》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.LinkedListimport scala.collection.JavaConversions._import java.util.ArrayListobject 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接口

对于Scala，情况要稍微复杂一点。以LinkedList为例，与它提供的功能相关的类或特质多达27个，如表9-3所示。

表9-3　LinkedList实现的Scala接口

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 :: Nilx: List[Int] = List(2, 3)  

另外，也可以直接这样写：

scala> val x = List(2, 3)x: List[Int] = List(2, 3)scala> 1 :: xres0: 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.HashMapvar 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 ::: yres0: 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: [email protected]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: [email protected]scala> var kitties = new Queue(new BengalKitten(/"michael/"))kitties: Queue[BengalKitten] = [email protected]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/") :: Nilkits: List[BengalKitten] = List([email protected])scala> var katzen : List[Cat] = kitskatzen: List[Cat] = List([email protected])scala> var haustieren : List[Pet] = katzenhaustieren: List[Pet] = List([email protected])  

我们在var上显式声明了类型，以免Scala把类型推断得过窄。

对Scala泛型的简略探讨到这里就结束了。下一个大主题是Scala在并发实现方式上的创新：放弃了多线程显式管理的方式，而选用了actor模型。