Java中的Hashtable

　　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.
　　

查看本文来源