3.5 Java

我们在Java里做第二个马尔可夫链算法的实现。Java是面向对象的语言，这种语言将促使人们对程序里各组件之间的界面给予特别关注。在这里，具有独立性的数据项和与之相关的函数(称为方法)被封装一起，形成称为对象或类的程序部件。

Java的库比C语言丰富得多，其中包含了一组能以各种方式把已有数据汇集起来的容器类。Vector是容器类的一个例子，它提供一种动态增长的数组，可以存储任何Object类型的东西。另一个例子是Hashtable类，它允许以任何类型的对象作为关键码，存储或提取某种类型的值。

在这个应用里，字符串的Vector是保存前缀和后缀的自然选择。用一个散列表，以前缀向量作为关键码，后缀向量作为值。按照术语，这种结构是从前缀到后缀的一个映射。在Java 语言里不需要显式定义的State类型，因为Hashtable结构能将前缀隐含地连接(映射)到后缀。这种设计与前面C版本的情况不同，那里建立了State结构，其中包含前缀和后缀链表，通过对前缀的散列计算得到的是一个完整的State。

Hashtable类提供了一个put方法，用于存储关键码和值的对；另外还提供了一个get方法，通过它可以从关键码出发得到对应的值：

我们的实现总共使用了三个类。第一个类Prefix保存前缀向量的词：

第二个类是Chain，它读取输入、构造散列表并产生输出。下面是它的类定义：

第三个类是公共界面，其中包含一个main函数和一个Chain实例：

Chain类实例在创建时构造起一个散列表，其中的前缀数组用NPREF个NONWORD设置了初始值。函数build利用库函数StreamTokenizer进行输入剖析，将输入分解为空白符分隔的一系列单词。进入循环前有三个函数调用，这是为了对完成单词分解的库函数做一些设置，使它的工作方式能符合我们关于“词”的定义。

函数add根据给定的前缀参数从散列表里提取对应的后缀向量，找不到(向量为空)时就创建一个新向量，并把这个新向量和新前缀一起存入散列表。在任何情况下，它都向后缀向量里加入一个新词，然后更新前缀，丢掉第一个词并在最后加一个新词。

Prefix有两个建构函数，它们根据由参数提供的数据创建新实例。第一个建构函数复制已有的Prefix，第二个函数建立一个新前缀，其中存放某字符串的n个拷贝。在程序初始化时，我们要用第二个建构函数建立包含NPREF个NONWORD的前缀：

Prefix类里也有两个方法，hashCode和equals，它们在Hashtable的实现中隐含地

被调用，产生下标和对表进行检索。Hashtable类要求必须为这两个方法专门建立一个类，

这迫使我们把Prefix建成一个完整的新类，而不是像后缀那样只建立一个Vector。

hashCode对向量各元素使用hashCode方法，将得到的值组合成一个散列值：

函数equals对两个前缀做比较，采用逐个比较元素的方式。

这个Java程序比前面的C程序小了不少，并照顾到更多的细节，Vector和Hashtable是其中最明显的例子。一般地说，这里的存储管理比较简单，因为向量本身能够自动增长，废料收集将管理回收那些不再引用的存储。但是，为了能使用Hashtable类，我们还必须自己写函数hashCode和equals。可见Java并没有照顾好一切细节。

对C和Java程序里针对相同基本数据结构的表示和操作做一个比较，可以看到，在Java程序里的功能划分做得更好。例如，在这里想把Vector换成数组是非常简单的。在C程序里就不同，每个东西都知道其他东西在做什么。例如：散列表在数组上进行操作，因此，在许多地方它都要做数组的维护工作；lookup知道State和Suffix的内部结构；任何东西都知道前缀数组的大小。