Question

Vector 允许我们用一个数字从一系列对象中作出选择，所以它实际是将数字同对象关联起来了。但假如我们想根据其他标准选择一系列对象呢？堆栈就是这样的一个例子：它的选择标准是“最后压入堆栈的东西”。这种“从一系列对象中选择”的概念亦可叫作一个“映射”、“字典”或者“关联数组”。从概念上讲，它看起来象一个 Vector，但却不是通过数字来查找对象，而是用另一个对象来查找它们！这通常都属于一个程序中的重要进程。

在 Java 中，这个概念具体反映到抽象类 Dictionary 身上。该类的接口是非常直观的 size() 告诉我们其中包含了多少元素；isEmpty() 判断是否包含了元素（是则为 true）；put(Object key, Object value) 添加一个值（我们希望的东西），并将其同一个键关联起来（想用于搜索它的东西）；get(Object key) 获得与某个键对应的值；而 remove(Object Key) 用于从列表中删除“键－值”对。还可以使用枚举技术：keys() 产生对键的一个枚举（Enumeration）；而 elements() 产生对所有值的一个枚举。这便是一个 Dictionary（字典）的全部。

Dictionary 的实现过程并不麻烦。下面列出一种简单的方法，它使用了两个 Vector，一个用于容纳键，另一个用来容纳值：

//: AssocArray.java
// Simple version of a Dictionary
import java.util.*;

public class AssocArray extends Dictionary {
  private Vector keys = new Vector();
  private Vector values = new Vector();
  public int size() { return keys.size(); }
  public boolean isEmpty() {
    return keys.isEmpty();
  }
  public Object put(Object key, Object value) {
    keys.addElement(key);
    values.addElement(value);
    return key;
  }
  public Object get(Object key) {
    int index = keys.indexOf(key);
    // indexOf() Returns -1 if key not found:
    if(index == -1) return null;
    return values.elementAt(index);
  }
  public Object remove(Object key) {
    int index = keys.indexOf(key);
    if(index == -1) return null;
    keys.removeElementAt(index);
    Object returnval = values.elementAt(index);
    values.removeElementAt(index);
    return returnval;
  }
  public Enumeration keys() {
    return keys.elements();
  }
  public Enumeration elements() {
    return values.elements();
  }
  // Test it:
  public static void main(String[] args) {
    AssocArray aa = new AssocArray();
    for(char c = 'a'; c <= 'z'; c++)
      aa.put(String.valueOf(c),
             String.valueOf(c)
             .toUpperCase());
    char[] ca = { 'a', 'e', 'i', 'o', 'u' };
    for(int i = 0; i < ca.length; i++)
      System.out.println("Uppercase: " +
             aa.get(String.valueOf(ca[i])));
  }
} ///:~

在对 AssocArray 的定义中，我们注意到的第一个问题是它“扩展”了字典。这意味着 AssocArray 属于 Dictionary 的一种类型，所以可对其发出与 Dictionary 一样的请求。如果想生成自己的 Dictionary，而且就在这里进行，那么要做的全部事情只是填充位于 Dictionary 内的所有方法（而且必须覆盖所有方法，因为它们——除构建器外——都是抽象的）。

Vector key 和 value 通过一个标准索引编号链接起来。也就是说，如果用“roof”的一个键以及“blue”的一个值调用 put()——假定我们准备将一个房子的各部分与它们的油漆颜色关联起来，而且 AssocArray 里已有 100 个元素，那么“roof”就会有 101 个键元素，而“blue”有 101 个值元素。而且要注意一下 get()，假如我们作为键传递“roof”，它就会产生与 keys.index.Of() 的索引编号，然后用那个索引编号生成相关的值矢量内的值。

main() 中进行的测试是非常简单的；它只是将小写字符转换成大写字符，这显然可用更有效的方式进行。但它向我们揭示出了 AssocArray 的强大功能。

标准 Java 库只包含 Dictionary 的一个变种，名为 Hashtable（散列表，注释③）。Java 的散列表具有与 AssocArray 相同的接口（因为两者都是从 Dictionary 继承来的）。但有一个方面却反映出了差别：执行效率。若仔细想想必须为一个 get() 做的事情，就会发现在一个 Vector 里搜索键的速度要慢得多。但此时用散列表却可以加快不少速度。不必用冗长的线性搜索技术来查找一个键，而是用一个特殊的值，名为“散列码”。散列码可以获取对象中的信息，然后将其转换成那个对象“相对唯一”的整数（int）。所有对象都有一个散列码，而 hashCode() 是根类 Object 的一个方法。Hashtable 获取对象的 hashCode()，然后用它快速查找键。这样可使性能得到大幅度提升（④）。散列表的具体工作原理已超出了本书的范围（⑤）——大家只需要知道散列表是一种快速的“字典”（Dictionary）即可，而字典是一种非常有用的工具。

③：如计划使用 RMI（在第 15 章详述），应注意将远程对象置入散列表时会遇到一个问题（参阅《Core Java》，作者 Conrell 和 Horstmann，Prentice-Hall 1997 年出版）

④：如这种速度的提升仍然不能满足你对性能的要求，甚至可以编写自己的散列表例程，从而进一步加快表格的检索过程。这样做可避免在与 Object 之间进行造型的时间延误，也可以避开由 Java 类库散列表例程内建的同步过程。

⑤：我的知道的最佳参考读物是《Practical Algorithms for Programmers》，作者为 Andrew Binstock 和 John Rex，Addison-Wesley 1995 年出版。

作为应用散列表的一个例子，可考虑用一个程序来检验 Java 的 Math.random() 方法的随机性到底如何。在理想情况下，它应该产生一系列完美的随机分布数字。但为了验证这一点，我们需要生成数量众多的随机数字，然后计算落在不同范围内的数字多少。散列表可以极大简化这一工作，因为它能将对象同对象关联起来（此时是将 Math.random() 生成的值同那些值出现的次数关联起来）。如下所示：

//: Statistics.java
// Simple demonstration of Hashtable
import java.util.*;

class Counter { 
  int i = 1; 
  public String toString() { 
    return Integer.toString(i); 
  }
}

class Statistics {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10000; i++) {
      // Produce a number between 0 and 20:
      Integer r = 
        new Integer((int)(Math.random() * 20));
      if(ht.containsKey(r))
        ((Counter)ht.get(r)).i++;
      else
        ht.put(r, new Counter());
    }
    System.out.println(ht);
  }
} ///:~

在 main() 中，每次产生一个随机数字，它都会封装到一个 Integer 对象里，使句柄能够随同散列表一起使用（不可对一个集合使用基本数据类型，只能使用对象句柄）。containKey() 方法检查这个键是否已经在集合里（也就是说，那个数字以前发现过吗？）若已在集合里，则 get() 方法获得那个键关联的值，此时是一个 Counter（计数器）对象。计数器内的值 i 随后会增加 1，表明这个特定的随机数字又出现了一次。

假如键以前尚未发现过，那么方法 put() 仍然会在散列表内置入一个新的“键－值”对。在创建之初，Counter 会自己的变量 i 自动初始化为 1，它标志着该随机数字的第一次出现。

为显示散列表，只需把它简单地打印出来即可。Hashtable toString() 方法能遍历所有键－值对，并为每一对都调用 toString()。Integer toString() 是事先定义好的，可看到计数器使用的 toString。一次运行的结果（添加了一些换行）如下：

{19=526, 18=533, 17=460, 16=513, 15=521, 14=495,
 13=512, 12=483, 11=488, 10=487, 9=514, 8=523,
 7=497, 6=487, 5=480, 4=489, 3=509, 2=503, 1=475,
 0=505}

大家或许会对 Counter 类是否必要感到疑惑，它看起来似乎根本没有封装类 Integer 的功能。为什么不用 int 或 Integer 呢？事实上，由于所有集合能容纳的仅有对象句柄，所以根本不可以使用整数。学过集合后，封装类的概念对大家来说就可能更容易理解了，因为不可以将任何基本数据类型置入集合里。然而，我们对 Java 封装器能做的唯一事情就是将其初始化成一个特定的值，然后读取那个值。也就是说，一旦封装器对象已经创建，就没有办法改变一个值。这使得 Integer 封装器对解决我们的问题毫无意义，所以不得不创建一个新类，用它来满足自己的要求。

1. 创建“关键”类

在前面的例子里，我们用一个标准库的类（Integer）作为 Hashtable 的一个键使用。作为一个键，它能很好地工作，因为它已经具备正确运行的所有条件。但在使用散列表的时候，一旦我们创建自己的类作为键使用，就会遇到一个很常见的问题。例如，假设一套天气预报系统将 Groundhog（土拔鼠）对象匹配成 Prediction（预报）。这看起来非常直观：我们创建两个类，然后将 Groundhog 作为键使用，而将 Prediction 作为值使用。如下所示：

//: SpringDetector.java
// Looks plausible, but doesn't work right.
import java.util.*;

class Groundhog {
  int ghNumber;
  Groundhog(int n) { ghNumber = n; }
}

class Prediction {
  boolean shadow = Math.random() > 0.5;
  public String toString() {
    if(shadow)
      return "Six more weeks of Winter!";
    else
      return "Early Spring!";
  }
}

public class SpringDetector {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10; i++)
      ht.put(new Groundhog(i), new Prediction());
    System.out.println("ht = " + ht + "\n");
    System.out.println(
      "Looking up prediction for groundhog #3:");
    Groundhog gh = new Groundhog(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~

每个 Groundhog 都具有一个标识号码，所以赤了在散列表中查找一个 Prediction，只需指示它“告诉我与 Groundhog 号码 3 相关的 Prediction”。Prediction 类包含了一个布尔值，用 Math.random() 进行初始化，以及一个 toString() 为我们解释结果。在 main() 中，用 Groundhog 以及与它们相关的 Prediction 填充一个散列表。散列表被打印出来，以便我们看到它们确实已被填充。随后，用标识号码为 3 的一个 Groundhog 查找与 Groundhog #3 对应的预报。

看起来似乎非常简单，但实际是不可行的。问题在于 Groundhog 是从通用的 Object 根类继承的（若当初未指定基础类，则所有类最终都是从 Object 继承的）。事实上是用 Object 的 hashCode() 方法生成每个对象的散列码，而且默认情况下只使用它的对象的地址。所以，Groundhog(3) 的第一个实例并不会产生与 Groundhog(3) 第二个实例相等的散列码，而我们用第二个实例进行检索。

大家或许认为此时要做的全部事情就是正确地覆盖 hashCode()。但这样做依然行不能，除非再做另一件事情：覆盖也属于 Object 一部分的 equals()。当散列表试图判断我们的键是否等于表内的某个键时，就会用到这个方法。同样地，默认的 Object.equals() 只是简单地比较对象地址，所以一个 Groundhog(3) 并不等于另一个 Groundhog(3)。

因此，为了在散列表中将自己的类作为键使用，必须同时覆盖 hashCode() 和 equals()，就象下面展示的那样：

//: SpringDetector2.java
// If you create a class that's used as a key in
// a Hashtable, you must override hashCode()
// and equals().
import java.util.*;

class Groundhog2 {
  int ghNumber;
  Groundhog2(int n) { ghNumber = n; }
  public int hashCode() { return ghNumber; }
  public boolean equals(Object o) {
    return (o instanceof Groundhog2)
      && (ghNumber == ((Groundhog2)o).ghNumber);
  }
}

public class SpringDetector2 {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10; i++)
      ht.put(new Groundhog2(i),new Prediction());
    System.out.println("ht = " + ht + "\n");
    System.out.println(
      "Looking up prediction for groundhog #3:");
    Groundhog2 gh = new Groundhog2(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~

注意这段代码使用了来自前一个例子的 Prediction，所以 SpringDetector.java 必须首先编译，否则就会在试图编译 SpringDetector2.java 时得到一个编译期错误。

Groundhog2.hashCode() 将土拔鼠号码作为一个标识符返回（在这个例子中，程序员需要保证没有两个土拔鼠用同样的 ID 号码并存）。为了返回一个独一无二的标识符，并不需要 hashCode()，equals() 方法必须能够严格判断两个对象是否相等。

equals() 方法要进行两种检查：检查对象是否为 null；若不为 null，则继续检查是否为 Groundhog2 的一个实例（要用到 instanceof 关键字，第 11 章会详加论述）。即使为了继续执行 equals()，它也应该是一个 Groundhog2。正如大家看到的那样，这种比较建立在实际 ghNumber 的基础上。这一次一旦我们运行程序，就会看到它终于产生了正确的输出（许多 Java 库的类都覆盖了 hashcode() 和 equals() 方法，以便与自己提供的内容适应）。

2. 属性：Hashtable 的一种类型

在本书的第一个例子中，我们使用了一个名为 Properties（属性）的 Hashtable 类型。在那个例子中，下述程序行：

Properties p = System.getProperties();

p.list(System.out);

调用了一个名为 getProperties() 的 static 方法，用于获得一个特殊的 Properties 对象，对系统的某些特征进行描述。list() 属于 Properties 的一个方法，可将内容发给我们选择的任何流式输出。也有一个 save() 方法，可用它将属性列表写入一个文件，以便日后用 load() 方法读取。

尽管 Properties 类是从 Hashtable 继承的，但它也包含了一个散列表，用于容纳“默认”属性的列表。所以假如没有在主列表里找到一个属性，就会自动搜索默认属性。

Properties 类亦可在我们的程序中使用（第 17 章的 ClassScanner.java 便是一例）。在 Java 库的用户文档中，往往可以找到更多、更详细的说明。