哈尔滨市第三中学 刘翀

4. 应用举例

　　4.1 应用的简单原则

　　什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问："某个元素是否在已知集合中？"，也就是需要高效的数据存储和查找，则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意的是什么呢？

　　哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标就是尽力避免冲突。前面提到，在使用"除余法"的时候，h(k)=k mod p ，p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢？假设 p=1000 ，则哈希函数分类的标准实际上就变成了按照末三位数分类，这样最多1000类，冲突会很多。一般地说，如果 p 的约数越多，那么冲突的几率就越大。

　　简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 则有 q mod p= q - p* [q div p] =q - p*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0，b] 的正整数。也就是说， [b div a] 的值只有 b+1 种可能，而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样，虽然mod 运算之后的余数仍然在 [0，p-1] 内，但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住"素数是我们的得力助手"。

　　另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。

　　综上所述，设计一个好的哈希函数是很关键的。而"好"的标准，就是较低的冲突率和易于实现。

　　另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。

　　这些只是一般原则，真正遇到试题的时候实际情况千变万化，需要具体问题具体分析才行。下面，我们看几个例子，看看这些原则是如何体现的。

4.2 有关字符串的例子

　　我们经常会遇到处理字符串的问题，下面我们来看这个例子：

　　　　　　　　　　　　　　　　找名字

问题描述：

　　给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编写密码，编写的方式是对于 n 位字符串，给定一个 n 位数，大写字母与数字的对应方式按照电话键盘的方式：

　　　　　　2: A,B,C　　 5: J,K,L　　 8: T,U,V
　　　　　　3: D,E,F 　　6: M,N,O 　　9: W,X,Y
　　　　　　4: G,H,I 　　7: P,R,S

　　题目给出一个 1--12 位的数，找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过 8000 。（这个是 USACO Training Gate 1.2.4 的一道题。）

　　分析：看懂题目之后，对于给定的编码，只需要一个回溯的过程，所有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在给定的字典中了。所以这个问题需要的还是"某个元素是否在已知集合中？"由于给出的"姓名"都是字符串，因此我们可以利用字符的 ASCII 码。那么，如何设计这个哈希函数呢？注意到题目给出的字典中，最多能有5000 个不同元素，而一个字符的 ASCII 码只能有26 种不同的取值，因此至少需要用在3个位置上的字符（26^3 > 5000，但是 26^2 < 5000 ），于是我们就选取3个位置上的字符。由于给定的字符串的长度从 1--12 都有可能，为了容易实现，选取最开始的1个字符，和最末尾的2个字符。让这3个字符组成27进制的3位数，则这个数的值就是这个字符串的编码。这样哈希函数就设计出来了！

　　不过，由于可能出现只有1位的字符串，在写函数代码的时候需要特殊考虑；大素数选取 13883 。

　　这个函数是这样的：
　　function hash(s:string):integer;
　　　　var i,tmp:longint;
　　　　begin
　　　　　tmp:=0; {用来记录27进制数的值}
　　　　　if length(s)>1 then begin
　　　　　tmp:=tmp*27+ord(s[1])-64;
　　　　　for i:=1 downto 0 do
　　　　　　tmp:=tmp*27+ord(s[length(s)-i])-64; {取第一位和后两位}
　　　　　　　　　　　　　end
　　　　　　　　　　　　else for i:=1 to 3 do
　　　　　　　　　　　　　tmp:=tmp*27+ord(s[1])-64;{当长度为1的时候特殊处理}
　　　　　hash:=tmp mod 13883;
　　　　end;

　　值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似"平均"，但是对于大多数情况，字符串是有规律的（例如英文单词），这个时候用哈希表反而不好（例如英语中有很多以 con 开头的单词），通常用检索树解决这样的查找问题。

4.3 在广度优先搜索中应用的例子

　　在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。来看下面的例子：

　　　　　　　　　　　　　　　　　转花盆

题意描述: 

　　　　给定两个正6边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的6盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过3种，对于任意两种花，数量多的花的盆数至少是数量少的花的2倍 。（这是 SGOI-8 的一道题）

　　分析：首先确定本题可以用广度优先搜索处理，然后来看问题的规模。正6边形共有19个格子可以用来放花，而且根据最后一句限定条件，至多只能存在 C(2,19) * C(5,17) = 1058148 种状态，用搜索完全可行。然而操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。那么这个哈希函数如何设计呢？注意到19个格子组成6边形是有顺序的，而且每一个格子只有3种可能情况，那么用3进制19位数最大 3^20-1=3486784400 用 Cardinal 完全可以承受。于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。

4.4 小结

　　从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法，但是每个字符都有"天生"的 ASCII 码，在设计哈希函数的时候可以直接利用。而其他方法，例如利用检索树的查找，编写代码不如哈希表简洁。至于广度优先搜索中的判重更是直接利用了哈希表的特点。

　　另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面的基本操作就可以了，因此重点应该是在哈希函数的设计上（尽管这两个例子的设计都很简单），需要注意题目本身可以利用的条件，以及估计值域的范围。下面我们看两个需要在哈希表基础上作一些变化的例子。

　　　　　　　　　　　　　　　　　　　　　　相关链接：浅谈竞赛中哈希表的应用（一）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（二）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（三）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（四）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（五）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（六）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（七）