7.0 哈希表
哈希表是一种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多的难以让人置信。不论哈希表中有多少数据，插入和删除(有时包括删除)只需要接近常量的时间：即O(1)的时间级。
哈希表的速度明显比树快，正如前面几章看到的，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
哈希表也有一些缺点：
1、它是基于数组的，数组创建后难于扩展。某些哈希表被基本填满时，性能下降的非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期的把数据迁移到更大的哈希表中，这是一个费时的过程）。
2、而且也没有一种方法可以以任何一种顺序（例如从小到大）遍历表中的数据项，如果需要这种能力，就只能选择其他的数据结构。然而，如果不需要有序遍历数据，并可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。
哈希化简介
本节将介绍哈希表的哈希化。其中一个重要的概念是如何把关键字转换成数组下标。在哈希表中，这个转换是通过哈希函数来完成的。然而对于特定的关键字，并不需要哈希函数：关键字的值可以直接用于数组的下标。先来看一个简单的例子：然后再逐步展示，若关键字值不能恰好用于数组的下标时，如何使用哈希函数进行转换。
案例1：雇员号码作为关键字
假设现在要写一个程序，存取一个公司的雇员记录，这个小公司大约有1000个员工。每个雇员记录需要1000个字节的存储空间。因此，整个数据库的大小约1MB，一般的计算机内存都可以满足。
计算机部门的领导已经强调必须要尽可能快地存取每个雇员记录。而且，每个雇员有 一个特定的号码，从1到1000。这个雇员号码作为存取记录的关键字；事实上，用其他关键字进行存取完全没有必要。雇员很少被解雇，但是即使当他们不在公 司了，他们的记录也要保存在数据库中以供参考。在这种情况下需要使用什么数据结构呢？
关键字作为索引
一种可能是用数组。每个雇员号码占数组的一个单元。单元的数组下标是当前记录的雇员号码。如下图所示：
众所周知，如果知道数组下标，要访问特定的数组数据项非常方便。操作员要查找Herman Alcazar，他知道Alcazar的雇员号码是72，所以他键入这个号码，程序直接检索数组下标为72的单元。总共只需要一条语句：
empRecord rec=databaseArray[72];
增加一个新项也非常快。只需要把它插到最后一个数据项的后面。下一个记录将被放在第1001个单元。插入新记录也只需要一条语句：
databaseArray[totalEmployees++]=newRecord;
数组大概需要比当前的雇员数量多少大一些，为了扩展留出空间，但不能指望可以大量扩展数组容量。
存在的问题：不总是如此有序
使用基于数组的数据库，使得存取数据速度快且非常简单，这很吸引人。然而这个例子之所以能运行，仅仅是因为关键字组织得异乎寻常的好。关键字从1到一个已 知的最大值，这个最大值对数组来说是合理的。没有删除，所以序列中不存在浪费内在的断裂带。新数据可以添加在数组的尾端，并且数组容量不需要比当前数据项 的数量大很多。
案例2：字典
前面描述的雇员信息数据库的关键字“表现”的很好，而在许多应用中，情况并非如此。经典的例子是字典。 如果想要把一本英文字典的每个单词，从a到zyzzyva（这当然是一个单词），都写入计算机内存，以便快速读写，那么哈希表是一个不错的选择。
哈希表还在另一个类似的领域得到广泛应用，这就是高级计算机语言的编译器，它们通常用哈希表保留符号表。符号表记录了程序员声明的所有变量和函数名，以及它们在内存中的地址。程序需要快速地访问这些名字，所以哈希表是理想的数据结构。
例如，想在内存中存储50000个英文单词。起初可能考虑每个单词占据一个数组单元，那么数组的大小是50000，同时可以使用数组下标存取单词。这样，存取确实很快。但是数组下标和单词有什么关系呢？例如给出一个单词morphosis，怎么能找到它的数组下标呢？
把单词转换成数组下标的含义
现在需要的是把单词转化成适当下标的系统。现在已经知道，计算机应用不同的编码方案，用数字代表单个的字符。其中一种是ASCII编码，其中a是97，b是98，依此类推，直到122代表z。
然而，ASCII码从0到255，可以容纳字母、标点等字符。英文单词中只有26个字母，所以可以设计出一种自己的编码方案，它可以潜在地存储内存空间。其中a是1，b是2，c是3，依此类推，直到26代表z。还要把空格用0代表，所以有27个字符（这个数组中不存在大写字母）。
如何把代表单个字母的数字组合成代表整个单词的数字呢？这有许多方法。下面看两种有代表性的方法，以及它们的优点和缺点。
方案一：把数字相加
一个转换单词的简单方法是把单词每个字符的代码求和。例如把单词cats转换成数字。首先，用前面创造的编码方案转换单词：
c=3 a=1 t=20 s=19
然后把它们相加：
3+1+20+19=43
那么，在字典中，单词cats存储在数组下标为43的单元中。所有的英文单词都可以用这个方法转换成数组下标。假设约定单词有十个字母。那么（记住空位是0）字典的第一个单词a的编码是 0+0+0+0+00+0+0+0+1=1。字典最后一个可能的单词是zzzzzzzzzz(10个z)。所有的字符编码的和是
26+26+26+26+26+26+26+26+26+26=260
因此，单词编码的范围是从1到260。不幸的是，词典中有50000个单词，所以没有足够的数组下标数来索引那么多的单词。每个数组数据项大概要存储192个单词(50000/260)。
很显然，用一个单词占用一个数组单元的方案会发生问题。也许可以考虑每个数组数据项包含一个子数组或链表。不幸的是，这个办法严重降低了存取速度。存取数据项确实很快，但是要在192个单词中找到其中一个，速度就很慢。
所以，第一次把单词转化成数字的尝试还留下一些问题要解决，比如有太多的单词需要用同一个数组下标（例如，was、tin 、give, tend, moan, tick,bails, dredge和其他一百多个单词用编码方案求得和都是43，和cats一样）。那么就得到这样的结论，这个方法没有把单词分得足够开，所以结果数组能表达的元素太少。需要扩展数组表达下标的空间。
方案二：幂的连乘
我们尝试一下用另外一种方法把单词映射成数字。如果数组容量太小，就确保它有足够的空间。如果创建一个数组，使得每个单词，实际上是每个潜在单词，从a到zzzzzzzzzz，都可以占据数组中一个单元的话，那么将会发生什么？
如果要这么做，首先要确定单词中的每个字符可以通过一种独一无二的方法得到最终的数字。下面考虑一种用数字替换单词的类似方法。在一个大于10的数字中，每一数位代表用数字乘以从当前位到个位的位数那么多个10。那么7654的意思是：
7*1000 + 5*100 + 4*10 + 6*1
或者写成10的幂的连乘
7*103 + 5*102 + 4*101 + 6*100
类似的方法，可以把单词分解成字母组合，把字母转换成它们的数字代码，乘以适当的27的幂（因为有27个可能的字符，包括空格），然后将结果相加。这就给出了每个单词对应的独一无二的数字。
例如要把单词cats转换为数字。首先像前面一样把数转换为数列，每个数字乘以相应的27的幂，然后将结果相加：
3*273 + 1*272 + 20*271 + 19*270
计算幂的值，得到：
3*19,683 + 1*729 + 20*27 + 19*1
字母代码与幂的值相乘，得到：
59,049 + 729 + 540 + 19
和为：60337.
这个过程确实可以为每个可能的单词创建一个独一无二的整数，刚刚只是计算了一个4个字母的单词。较长的单词会法发生什么？不幸的是，整数的范围会变得非常大。最长的10个字母的单词，zzzzzzzzzz，将转换为：
26*279 + 26*278 + 26*277 + 26*276 + 26*275 + 26*274 + 26*273 + 26*272 + 26*271 +26*270
仅279就超过 7,000,000,000,000，所以看到结果非常巨大。在内存中的数组根本不可能有这么多单元。这个问题出现的原因是这个方案为每个可能的单词都分配了一个数组单元，而不管这个单词是不是真正的英语单词。因此数组单元就是从 aaaaaaaaaa,aaaaaaaaab, aaaaaaaaac,一直到zzzzzzzzzz。这些单元中只有一小部分存放了存在的英语单词，这是必须的，而大多数单元都是空的。如下图所示：
第一种方案（把数字相加求和）产生的下标太少，第二种方案（与27的幂相乘并求和），产生的数组下标又太多。
哈希化
现在需要一种压缩方法，把数位幂的边乘系统中得到的巨大的整数范围压缩到可接受的数组范围中。对于英语词典，多大的数组才合适？如果只有50000个单词，可能会假设这个数组大概就有这么多空间。但实际上，需要多一倍的空间容纳这些单词。（后面就知道为什么这么说）。所以，最终需要容量为100000的数组。
现在，就找一种方法，把0到超过70000000000000的范围，压缩为0到100000。
有一种简单的方法是使用取余操作符，它的作用是得到一个数被另外一个数整除后的余数。 为了看到这个方法如何工作，首先来看在一个较小的，较易理解的数组范围如何运作。假设把从0到199的数字，压缩为从0到9的数字。后者有10个数，所以 说变量smallRange值为10。而变量largeNumber的值是多少并不重要。这个转换的Java表达式为
smallNumber=largeNumber%smallRange;
当一个数被10整除时，余数一定是0到9之间：例如，13%10为3，157%10为7。这样就把0～199的范围压缩到0～9的范围，压缩率为20：1。
也可以用类似的方法把表示单词的惟一的数字压缩成数组的下标：
arrayIndex=hugeNumber%arraySize;
这就是一种哈希函数。它把一个大范围的数字哈希成一个小范围的数字。这个小的范围对应着数组的下标。使用哈希函数向数组插入数据后，这个数组就称为哈希表。
回忆一下：通过把单词每个字母乘以27的适当次幂，使单词成为了一个巨大的数字：
hugeNumber = ch0*279 + ch1*278 + ch2*277 + ch3*276 + ch4*275 + ch5*274 + ch6*273 + ch7*272 + ch8*271 + ch9*270
然后，使用取余操作符，把得到的巨大整数范围转换成两倍于要存储内容的数组下标范围。下面是哈希函数的例子：
arraySize=numberWords*2; arrayIndex=hugeNumber%arraySize;
在原始的范围中，每个数字代表一个潜在的数据项，但是它们中间只有很少一部分代表真实数据。哈希函数把这个巨大的整数范围转换成小的多的数组的下标范围。期望的数组应该有这样的特点，平均起来，每两个数组单元，就有一个单词。有些单元没有单词；而有些有多个单词。
这个方案的实际实现会遇到问题，因为hugeNumber可能会超出变量范围，即使变量类型是long。后面会看如何处理这个问题。
冲突
把巨大的数字空间压缩成较小的数字空间，必然要付出代价，即不能保证，每个单词都映射到数组的空白单元。这个情况和把字符代码相加时的情况类似，但是现在更麻烦。当把字符代码相加时，只有约260种可能(对于最多只有10个字符的单词)。现在，把这个可能性扩展到了50000种。
虽然如此，不可能避免把几个不同的单词哈希化到同一个数组单元，至少偶尔会这样。当然希望每个数组下标对应一个数据项，但是通常这不可能。只能寄希望于没有太多的单词有同样的数组下标。
假设要在数组中插入单词melioration。通过哈希函数得到了它的数组下标后，发现那个单元已经有一个单词了，因为这个单词哈希化后得到的数组下标与melioration相同。如下图所示，这种情况称之为冲突：
冲突的可能性会导致哈希化方案无法实施，实际上，可以通过另外的方式解决这个问题。记住，前面已经说过，指定的数组大小两倍于需要存储的数据量。因此，可 能一半的单元是空的。
当冲突发生时，一个方法是通过系统的方法找到数组的一个空位，并把这个单词填入，而不是用哈希函数得到的数组下标。这个方法叫做开放地址法。例如，如果cats哈希化的结果是5421，但它的位置已经被parsnip占用，那么可能会考虑把cats放在5422的位置上。
第二种方法是创建一个存放单词链表的数组，数组内不直接存储单词。这样，当发生冲突时，新的数据项直接到这个数组下标所指的链表中。这种方法叫做链地址法。
本章的剩余部分将讨论开放地址法和链地址法，最后回到哈希函数的问题。
到目前为止，一直都在关注如何哈希化字符串。这是很现实的，因为许多哈希表用来存储字符串。然后，也有不少哈希表是存储数字的，例如前面提到的雇员编码的例子。在之后的讨论中，都使用数字作为关键字。这样事情会变得容易理解，编程也会变得容易。然而应该记得，在许多情况中，这些数字是从字符串中得到的。
