《算法技术手册》使用环境

假设我们创建了一个文本编辑器，并且希望能检查用户输入单词的拼写。有一些免费的单词表可以从网上下载（http://www.wordlist.com）。性能对于这个应用程序来说非常重要。我们必须快速地查找这个单词表，否则即使是最慢的打字员，程序也都是不可用的。我们也许需要一个单独的线程，这个线程用来获得文档或者文件的最新修改，并且能够检查单词的拼写[1]。

我们必须将这些单词保存在内存中，因为磁盘操作将会导致性能退化太多。一个典型的英语单词列表包含超过200 000个单词，而且能够以数组的形式存储在内存中，占用大约2.5MB的内存（如图5-4所示，这个包含了单词本身的空间以及指向单词的指针的空间）。我们使用指针是因为单词的长度是改变的，而且我们希望能够使用最少的内存。

在“二分查找”一节中我们得知，如果使用二分查找需要进行大约18次字符串比较[2]。字符串比较是非常昂贵的，即使我们优化代码，也需要循环比较字节。有时候我们使用汇编语言手动编写这些循环确保能够在特定架构上进行优化，例如确保我们不会在大部分的情况下停顿在流水线上以及在可能时展开循环来填充流水线。目标是最小化字符串比较的次数。

我们首先需要定义一个函数来计算字符串s的键值。这个键值函数的一个目标是产生足够多的不同值，不过并不要求这些值都是唯一的。根据初始字符串的每一块信息来产生值的一个流行的方法是：

s[i]是第i个字符（值在0～255之间），len就是字符串s的长度。计算这个函数的值非常简单，例5-6就是这个函数的实现（根据Open JDK源代码改写），chars是字符数组，即一个字符串[3]。根据我们的定义，java.lang.String的hashCode方法是key函数。

例5-6：Java hashCode样例

因为hashCode方法尽量尝试优化，它缓存了已经计算过的散列值，避免重复计算（例如，当且仅当散列是0时的计算值）。

下一步，我们构造散列表。我们有n个字符串，那么散列表A的大小应该是多少呢？在最理想的情况下，A有b=n个桶，散列函数是一个从字符串集合到整数[0,n)的一一映射函数。这是在正常情况下不可能发生的，所以我们尝试着构造一个空桶尽可能少的散列表。如果我们的散列函数平均分配键值，我们就能够获得一个比较理想的情况，数组的大小和集合的大小差不多。我们定义hash(s)=key(s)%b，%是取模运算符，返回key(s)除以b的余数。

高水平读者此时就会问基本的散列函数和散列表在这里会起什么作用。因为单词表是静态的，所以我们能够通过构建一个完美的散列函数来做得更好。一个完美的散列函数能够保证在一个特定的键值集合中没有冲突产生。在这种情况下，一个完美的散列函数就能投入使用，在接下来的“变种”一节中将讨论这个问题。让我们先在没有这个完美散列函数的情况下尝试解决这个问题。

在我们第一次尝试解决这个问题时，我们选择了一个数组A，有着217个桶，以及262 143个元素。我们的单词表包含213 557个单词。如果我们的散列函数能够使字符串完美地分布，那么就会没有冲突产生并且需要大约40 000个槽。但是情况并非如此。表5-4给出了我们单词表中字符串的散列值[4]分布情况，散列表有着262 143个槽。正如你所见，没有一个槽会存储超过7个字符串,对于非空槽来说，每个槽的平均字符串数量大约是1.46。表5-4的每一行表明了使用的槽的数量以及有多少字符串被映射到这些槽中。散列表中几乎一半的槽（116 186个）没有字符串映射到。所以，这个散列函数浪费了大概500K的内存空间——假设每个指针的大小是4个字节，我们不会使用在空条目上使用冲突处理策略。你也许会非常惊讶这是一个非常优秀的散列函数，如果需要寻找到一个比这个更好的，那么需要一个更加复杂的结构。对于这个数据集来说，只有五对字符串有着相同的键值（例如，hypoplankton和unheavenly有着相同的键值427 589 249）！

最后，我们需要决定采取什么策略来处理冲突。一个可行的办法是在主散列表存储指向一系列条目的指针，而不是存储一个对象。这个方法，如图5-6所示，叫做链式。

这个方法的总开销取决于你在每个槽中是元素列表还是nil值（表示没有列表）。当一个槽只有一个元素时，它可以使用列表来存取。作为我们的第一个近似的解决方案，我们将会使用这种方法并且在性能成为瓶颈时改进它。