《浅谈竞赛中哈希表的应用》由会员分享，可在线阅读，更多相关《浅谈竞赛中哈希表的应用（26页珍藏版）》请在金锄头文库上搜索。
1、浅谈竞赛中哈希表的应用第 1 页 共 27 页浅谈竞赛中哈希表的应用哈尔滨市第三中学 刘翀关键词 应用 哈希表 数据结构 摘要 哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈希表的优点，其次介绍了它的基础操作，接着从简单的例子中作了效率对比，指出其适用范围以及特点，然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题，最后总结全文。正文1. 引言哈希表（Hash Table）的应用近两年才在 NOI 中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内
2、存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。哈希表又叫做散列表，分为“开散列” 和“闭散列” 。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列” ，关于其他方面读者可参阅其他书籍。2. 基础操作2.1基本原理我们使用一个下标范围比较大的数组来存储元素。可以设计一个函浅谈竞赛中哈希表的应用第 2 页 共 27 页数（哈希函数， 也叫做散列函数） ，使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类” ，然后将这个元素存储
3、在相应“类”所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突” ，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。总的来说， “直接定址”与“解决冲突”是哈希表的两大特点。2.2函数构造构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：a) 除余法：选择一个适当的正整数 p ，令 h(k ) = k mod p 这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。b) 数字选
4、择法：如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。2.3冲突处理线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3 ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的） 。2.4支持运算哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x)、插入元素(insert)、查找元素(memb
5、er)。设插入的元素的关键字为 x ，A 为存储的数组。初始化比较容易，例如const empty=maxlongint; / 用非常大的整数代表这个位置没有存储元素p=9997; / 表的大小procedure makenull;var i:integer;beginfor i:=0 to p-1 doAi:=empty;End;浅谈竞赛中哈希表的应用第 3 页 共 27 页哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：function h(x:longint):Integer;beginh:= x mod p;end;我们注意到，插入和查找首先都需要对这个元素定位，即如果这个
6、元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate function locate(x:longint):integer;var orig,i:integer;beginorig:=h(x);i:=0;while (ix)and(A(orig+i)mod S 12 ，因为 mod 运算本身与快速排序的比较大小和交换元素运算相比，比较费时间。所以规模小的时候，O(N)（忽略冲突）的算法反而不如 O(NlogN)。这一点在更复杂的哈希函数上会体现的更明显，因为更复杂的函数系数会更大。其次，当规模稍大 （大约为 15%*P 1 ，即有 p=a*d , q=b*d, 则有 q mo
7、d 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 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住“素数是我们的得力助手” 。另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美
8、，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。综上所述，设计一个好的哈希函数是很关键的。而“好”的标准，就是较低的冲突率和易于实现。另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往浅谈竞赛中哈希表的应用第 7 页 共 27 页一些简单的改进就可以带来巨大的方便。这些只是一般原则，真正遇到试题的时候实际情况千变万化，需要具体问题具体分析才行。下面，我们看几个例子
9、，看看这些原则是如何体现的。4.2 有关字符串的例子我们经常会遇到处理字符串的问题，下面我们来看这个例子：=找名字问题描述：给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编写密码，编写的方式是对于 n 位字符串，给定一个 n 位数，大写字母与数字的对应方式按照电话键盘的方式：2: A,B,C 5: J,K,L 8: T,U,V3: D,E,F 6: M,N,O 9: W,X,Y4: G,H,I 7: P,R,S题目给出一个 112 位的数，找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过 8000 。这个是 USACO Training Gate
10、 1.2.4 的一道题。分析： 看懂题目之后，对于给定的编码，只需要一个回溯的过程，所有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在给定的字典中了。所以这个问题需要的还是“某个元素是否在已知集合中？”由于给出的“姓名”都是字符串，因此我们可以利用字符的 ASCII 码。那么，如何设计这个哈希函数呢？注意到题目给出的字典中，最多能有 5000 个不同元素，而一个字符的 ASCII 码只能有 26 种不同的取值，因此至少需要用在 3 个位置上的字符（263 5000，但是 262 1 then begintmp:=tmp*27+ord(s1)-64;for i:=1 downto
11、 0 dotmp:=tmp*27+ord(slength(s)-i)-64; 取第一位和后两位end浅谈竞赛中哈希表的应用第 8 页 共 27 页else for i:=1 to 3 dotmp:=tmp*27+ord(s1)-64;当长度为 1 的时候特殊处理hash:=tmp mod 13883;end;值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似“平均” ，但是对于大多数情况，字符串是有规律的（例如英文单词） ，这个时候用哈希表反而不好（例如英语中有很多以 con 开头的单词） ，通常用检索树解决这样的查找问题。4.3 在广度优先搜索中应用的例子在广度优先搜索中，
12、一个通用而且有效的剪枝就是在拓展节点之前先判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。来看下面的例子：转花盆题意描述:给定两个正 6 边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的 6 盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过 3 种，对于任意两种花，数量多的花的盆数至少是数量少的花的 2 倍 这是 SGOI-8 的一道题分析： 首先确定本题可以用广度优先搜索处理，然后来看问题的规模。正 6 边形共有 19 个格子可以用来放花，而且根据最后一句限定条件，至多只
13、能存在 C(2,19) * C(5,17) = 1058148 种状态，用搜索完全可行。然而操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。那么这个哈希函数如何设计呢？注意到 19 个格子组成 6 边形是有顺序的，而且每一个格子只有 3 种可能情况，那么用 3 进制 19 位数最大 320-1=3486784400 用 Cardinal 完全可以承受。于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。4.4 小结从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法，但是每个字符都有“天生”的 ASCII 码，在设计哈希函数
14、的时候可以直接利用。而其他方法，例如利用检索树的查找，编写代码不如哈希表简洁。至于广度优先搜索中的判重更是直接利用了哈希表的特点。浅谈竞赛中哈希表的应用第 9 页 共 27 页另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面的基本操作就可以了，因此重点应该是在哈希函数的设计上（尽管这两个例子的设计都很简单） ，需要注意题目本身可以利用的条件，以及估计值域的范围。下面我们看两个需要在哈希表基础上作一些变化的例子。4.5 需要微小变化的例子下面，我们来分析一道 NOI 的试题：=方程的解数问题描述已知一个 n 元高次方程：12. 0npppkxkx其中：x 1, x2, ,xn 是未知
15、数，k 1,k2,kn 是系数，p 1,p2,pn 是指数。且方程中的所有数均为整数。假设未知数 1 xi M, i=1,n，求这个方程的整数解的个数。约束条件1n6；1M 150；2 31.2npppkkM方程的整数解的个数小于 231。本题中，指数 Pi(i=1,2,n)均为正整数。这个是 NOI 2001 的第二试中的方程的解数 。分析： 初看此题，题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有 6 个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且注意到解的范围最多 150 个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样时间复杂度是 O(M6) ，无法承受。因此我们需要寻找更好的方法，自然想到能否缩小枚举的范围呢？但是发现这样也有很大的困难。我们再次注意到 M 的范围，若想不超时，似乎算法的复杂度上限应该是 O(M3) 左右，这是因为 1503 0)and(ea,(t+i)mod p,1rc)or(ea,(t+i)mod p,30)and(indextmp=value;repeatde
