8.1 数组

对数组的大多数必要的介绍已在第4章的最后一节进行。通过那里的学习,大家已知道自己该如何定义及初始化一个数组。对象的容纳是本章的重点,而数组只是容纳对象的一种方式。但由于还有其他大量方法可容纳数组,所以是哪些地方使数组显得如此特别呢? 有两方面的问题将数组与其他集合类型区分开来:效率和类型。对于Java来说,为保存和访问一系列对象(实际是对象的句柄)数组,最有效的方法莫过于数组。数组实际代表一个简单的线性序列,它使得元素的访问速度非常快,但我们却要为这种速度付出代价:创建一个数组对象时,它的大小是固定的,而且不可在那个数组对象的“存在时间”内发生改变。可创建特定大小的一个数组,然后假如用光了存储空间,就再创建一个新数组,将所有句柄从旧数组移到新数组。这属于“矢量”(Vector)类的行为,本章稍后还会详细讨论它。然而,由于为这种大小的灵活性要付出较大的代价,所以我们认为矢量的效率并没有数组高。

C的矢量类知道自己容纳的是什么类型的对象,但同Java的数组相比,它却有一个明显的缺点:C矢量类的operator[]不能进行范围检查,所以很容易超出边界(然而,它可以查询vector有多大,而且at()方法确实能进行范围检查)。在Java中,无论使用的是数组还是集合,都会进行范围检查——若超过边界,就会获得一个RuntimeException(运行期违例)错误。正如大家在 第9章 违例差错控制 会学到的那样,这类违例指出的是一个程序员错误,所以不需要在代码中检查它。在另一方面,由于C++的vector不进行范围检查,所以访问速度较快——在Java中,由于对数组和集合都要进行范围检查,所以对性能有一定的影响。

本章还要学习另外几种常见的集合类:Vector(矢量)、Stack(堆栈)以及Hashtable(散列表)。这些类都涉及对对象的处理——好象它们没有特定的类型。换言之,它们将其当作Object类型处理(Object类型是Java中所有类的“根”类)。从某个角度看,这种处理方法是非常合理的:我们仅需构建一个集合,然后任何Java对象都可以进入那个集合(除基本数据类型外——可用Java的基本类型封装类将其作为常数置入集合,或者将其封装到自己的类内,作为可以变化的值使用)。这再一次反映了数组优于常规集合:创建一个数组时,可令其容纳一种特定的类型。这意味着可进行编译期类型检查,预防自己设置了错误的类型,或者错误指定了准备提取的类型。当然,在编译期或者运行期,Java会防止我们将不当的消息发给一个对象。所以我们不必考虑自己的哪种做法更加危险,只要编译器能及时地指出错误,同时在运行期间加快速度,目的也就达到了。此外,用户很少会对一次违例事件感到非常惊讶的。

考虑到执行效率和类型检查,应尽可能地采用数组。然而,当我们试图解决一个更常规的问题时,数组的局限也可能显得非常明显。在研究过数组以后,本章剩余的部分将把重点放到Java提供的集合类身上。

8.1.1 数组和第一类对象

无论使用的数组属于什么类型,数组标识符实际都是指向真实对象的一个句柄。那些对象本身是在内存“堆”里创建的。堆对象既可“隐式”创建(即默认产生),亦可“显式”创建(即明确指定,用一个new表达式)。堆对象的一部分(实际是我们能访问的唯一字段或方法)是只读的length(长度)成员,它告诉我们那个数组对象里最多能容纳多少元素。对于数组对象,“[]”语法是我们能采用的唯一另类访问方法。

下面这个例子展示了对数组进行初始化的不同方式,以及如何将数组句柄分配给不同的数组对象。它也揭示出对象数组和基本数据类型数组在使用方法上几乎是完全一致的。唯一的差别在于对象数组容纳的是句柄,而基本数据类型数组容纳的是具体的数值(若在执行此程序时遇到困难,请参考 3.1.2 赋值 小节):

//: ArraySize.java
// Initialization & re-assignment of arrays
package c08;
class Weeble {} // A small mythical creature
public class ArraySize {
  public static void main(String[] args) {
    // Arrays of objects:
    Weeble[] a; // Null handle
    Weeble[] b = new Weeble[5]; // Null handles
    Weeble[] c = new Weeble[4];
    for(int i = 0; i < c.length; i++)
      c[i] = new Weeble();
    Weeble[] d = {
      new Weeble(), new Weeble(), new Weeble()
    };
    // Compile error: variable a not initialized:
    //!System.out.println("a.length=" + a.length);
    System.out.println("b.length = " + b.length);
    // The handles inside the array are 
    // automatically initialized to null:
    for(int i = 0; i < b.length; i++)
      System.out.println("b[" + i + "]=" + b[i]);
    System.out.println("c.length = " + c.length);
    System.out.println("d.length = " + d.length);
    a = d;
    System.out.println("a.length = " + a.length);
    // Java 1.1 initialization syntax:
    a = new Weeble[] {
      new Weeble(), new Weeble()
    };
    System.out.println("a.length = " + a.length);
    // Arrays of primitives:
    int[] e; // Null handle
    int[] f = new int[5];
    int[] g = new int[4];
    for(int i = 0; i < g.length; i++)
      g[i] = i*i;
    int[] h = { 11, 47, 93 };
    // Compile error: variable e not initialized:
    //!System.out.println("e.length=" + e.length);
    System.out.println("f.length = " + f.length);
    // The primitives inside the array are
    // automatically initialized to zero:
    for(int i = 0; i < f.length; i++)
      System.out.println("f[" + i + "]=" + f[i]);
    System.out.println("g.length = " + g.length);
    System.out.println("h.length = " + h.length);
    e = h;
    System.out.println("e.length = " + e.length);
    // Java 1.1 initialization syntax:
    e = new int[] { 1, 2 };
    System.out.println("e.length = " + e.length);
  }
} ///:~
Here’s the output from the program:
b.length = 5
b[0]=null
b[1]=null
b[2]=null
b[3]=null
b[4]=null
c.length = 4
d.length = 3
a.length = 3
a.length = 2
f.length = 5
f[0]=0
f[1]=0
f[2]=0
f[3]=0
f[4]=0
g.length = 4
h.length = 3
e.length = 3
e.length = 2

其中,数组a只是初始化成一个null句柄。此时,编译器会禁止我们对这个句柄作任何实际操作,除非已正确地初始化了它。数组b被初始化成指向由Weeble句柄构成的一个数组,但那个数组里实际并未放置任何Weeble对象。然而,我们仍然可以查询那个数组的大小,因为b指向的是一个合法对象。这也为我们带来了一个难题:不可知道那个数组里实际包含了多少个元素,因为length只告诉我们可将多少元素置入那个数组。换言之,我们只知道数组对象的大小或容量,不知其实际容纳了多少个元素。尽管如此,由于数组对象在创建之初会自动初始化成null,所以可检查它是否为null,判断一个特定的数组“空位”是否容纳一个对象。类似地,由基本数据类型构成的数组会自动初始化成零(针对数值类型)、null(字符类型)或者false(布尔类型)。

数组c显示出我们首先创建一个数组对象,再将Weeble对象赋给那个数组的所有“空位”。数组d揭示出“集合初始化”语法,从而创建数组对象(用new命令明确进行,类似于数组c),然后用Weeble对象进行初始化,全部工作在一条语句里完成。 下面这个表达式:

a = d;

向我们展示了如何取得同一个数组对象连接的句柄,然后将其赋给另一个数组对象,就象我们针对对象句柄的其他任何类型做的那样。现在,a和d都指向内存堆内同样的数组对象。

Java 1.1加入了一种新的数组初始化语法,可将其想象成“动态集合初始化”。由d采用的Java 1.0集合初始化方法则必须在定义d的同时进行。但若采用Java 1.1的语法,却可以在任何地方创建和初始化一个数组对象。例如,假设hide()方法用于取得一个Weeble对象数组,那么调用它时传统的方法是:

hide(d);

但在Java 1.1中,亦可动态创建想作为参数传递的数组,如下所示:

hide(new Weeble[] {new Weeble(), new Weeble() });

这一新式语法使我们在某些场合下写代码更方便了。

上述例子的第二部分揭示出这样一个问题:对于由基本数据类型构成的数组,它们的运作方式与对象数组极为相似,只是前者直接包容了基本类型的数据值。

基本数据类型集合

集合类只能容纳对象句柄。但对一个数组,却既可令其直接容纳基本类型的数据,亦可容纳指向对象的句柄。利用象Integer、Double之类的“封装器”类,可将基本数据类型的值置入一个集合里。但正如本章后面会在WordCount.java例子中讲到的那样,用于基本数据类型的封装器类只是在某些场合下才能发挥作用。无论将基本类型的数据置入数组,还是将其封装进入位于集合的一个类内,都涉及到执行效率的问题。显然,若能创建和访问一个基本数据类型数组,那么比起访问一个封装数据的集合,前者的效率会高出许多。

当然,假如准备一种基本数据类型,同时又想要集合的灵活性(在需要的时候可自动扩展,腾出更多的空间),就不宜使用数组,必须使用由封装的数据构成的一个集合。大家或许认为针对每种基本数据类型,都应有一种特殊类型的Vector。但Java并未提供这一特性。某些形式的建模机制或许会在某一天帮助Java更好地解决这个问题(注释①)。

①:这儿是C比Java做得好的一个地方,因为C通过template关键字提供了对“参数化类型”的支持。

8.1.2 数组的返回

假定我们现在想写一个方法,同时不希望它仅仅返回一样东西,而是想返回一系列东西。此时,象C和C++这样的语言会使问题复杂化,因为我们不能返回一个数组,只能返回指向数组的一个指针。这样就非常麻烦,因为很难控制数组的“存在时间”,它很容易造成内存“漏洞”的出现。

Java采用的是类似的方法,但我们能“返回一个数组”。当然,此时返回的实际仍是指向数组的指针。但在Java里,我们永远不必担心那个数组的是否可用——只要需要,它就会自动存在。而且垃圾收集器会在我们完成后自动将其清除。 作为一个例子,请思考如何返回一个字串数组:

//: IceCream.java
// Returning arrays from methods
public class IceCream {
  static String[] flav = {
    "Chocolate", "Strawberry",
    "Vanilla Fudge Swirl", "Mint Chip",
    "Mocha Almond Fudge", "Rum Raisin",
    "Praline Cream", "Mud Pie" 
  };
  static String[] flavorSet(int n) {
    // Force it to be positive & within bounds:
    n = Math.abs(n) % (flav.length + 1);
    String[] results = new String[n];
    int[] picks = new int[n];
    for(int i = 0; i < picks.length; i++)
      picks[i] = -1;
    for(int i = 0; i < picks.length; i++) {
      retry:
      while(true) {
        int t =
          (int)(Math.random() * flav.length);
        for(int j = 0; j < i; j++)
          if(picks[j] == t) continue retry;
        picks[i] = t;
        results[i] = flav[t];
        break;
      }
    }
    return results;
  }
  public static void main(String[] args) {
    for(int i = 0; i < 20; i++) {
      System.out.println(
        "flavorSet(" + i + ") = ");
      String[] fl = flavorSet(flav.length);
      for(int j = 0; j < fl.length; j++)
        System.out.println("\t" + fl[j]);
    }
  }
} ///:~

flavorSet()方法创建了一个名为results的String数组。该数组的大小为n——具体数值取决于我们传递给方法的自变量。随后,它从数组flav里随机挑选一些“香料”(Flavor),并将它们置入results里,并最终返回results。返回数组与返回其他任何对象没什么区别——最终返回的都是一个句柄。至于数组到底是在flavorSet()里创建的,还是在其他什么地方创建的,这个问题并不重要,因为反正返回的仅是一个句柄。一旦我们的操作完成,垃圾收集器会自动关照数组的清除工作。而且只要我们需要数组,它就会乖乖地听候调遣。

另一方面,注意当flavorSet()随机挑选香料的时候,它需要保证以前出现过的一次随机选择不会再次出现。为达到这个目的,它使用了一个无限while循环,不断地作出随机选择,直到发现未在picks数组里出现过的一个元素为止(当然,也可以进行字串比较,检查随机选择是否在results数组里出现过,但字串比较的效率比较低)。若成功,就添加这个元素,并中断循环(break),再查找下一个(i值会递增)。但假若t是一个已在picks里出现过的数组,就用标签式的continue往回跳两级,强制选择一个新t。用一个调试程序可以很清楚地看到这个过程。

main()能显示出20个完整的香料集合,所以我们看到flavorSet()每次都用一个随机顺序选择香料。为体会这一点,最简单的方法就是将输出重导向进入一个文件,然后直接观看这个文件的内容。

下一节:现在总结一下我们前面学过的东西:为容纳一组对象,最适宜的选择应当是数组。而且假如容纳的是一系列基本数据类型,更是必须采用数组。在本章剩下的部分,大家将接触到一些更常规的情况。当我们编写程序时,通常并不能确切地知道最终需要多少个对象。有些时候甚至想用更复杂的方式来保存对象。为解决这个问题,Java提供了四种类型的“集合类”:Vector(矢量)、BitSet(位集)、Stack(堆栈)以及Hashtable(散列表)。与拥有集合功能的其他语言相比,尽管这儿的数量显得相当少,但仍然能用它们解决数量惊人的实际问题。

这些集合类具有形形色色的特征。例如,Stack实现了一个LIFO(先入先出)序列,而Hashtable是一种“关联数组”,允许我们将任何对象关联起来。除此以外,所有Java集合类都能自动改变自身的大小。所以,我们在编程时可使用数量众多的对象,同时不必担心会将集合弄得有多大。