算法合集之《Hash函数的设计优化》

Hash函数的设计优化天津南开中学李羽修【摘要】Hash是一种在信息学竞赛中经常用到的数据结构。一个好的Hash函数可以很大程度上提高程序的整体时间效率和空间效率。本文对面向各种不同标本（关键值）的Hash函数进行讨论，并对多种常用的Hash函数进行了分析和总结。【关键字】Hash函数，字符串，整数，实数，排列组合【正文】对于一个Hash函数，评价其优劣的标准应为随机性，即对任意一组标本，进入Hash表每一个单元（cell）之概率的平均程度，因为这个概率越平均，数据在表中的分布就越平均，表的空间利用率就越高。由于在竞赛中，标本的性质是无法预知的，因此数学推理将受到很大限制。我们用实验的方法研究这个随机性。一、整数的Hash函数常用的方法有三种：直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下假定我们的关键字是k，Hash表的容量是M，Hash函数为kh。1．直接取余法我们用关键字k除以M，取余数作为在Hash表中的位置。函数表达式可以写成：Mkkhmod。例如，表容量12M，关键值100k，那么4kh。该方法的好处是实现容易且速度快，是很常用的一种方法。但是如果M选择的不好而偏偏标本又很特殊，那么数据在Hash中很容易扎堆而影响效率。对于M的选择，在经验上，我们一般选择不太接近n2的一个素数；如果关键字的值域较小，我们一般在此值域1.1~1.6倍范围内选择。例如k的值域为600,0，那么701M即为一个不错的选择。竞赛的时候可以写一个素数生成器或干脆自己写一个“比较像素数”的数。我用4000个数插入一个容量为701的Hash表，得到的结果是：测试数据随机数据连续数据最小单元容量：05最大单元容量：156期望容量：5.706135.70613标准差：2.41650.455531可见对于随机数据，取余法的最大单元容量达到了期望容量的将近3倍。经测试，在我的机器（PentiumIII866MHz，128MBRAM）上，该函数的运行时间大约是39ns，即大约35个时钟周期。2．乘积取整法我们用关键字k乘以一个在1,0中的实数A（最好是无理数），得到一个k,0之间的实数；取出其小数部分，乘以M，再取整数部分，即得k在Hash表中的位置。函数表达式可以写成：1mod)(kAMkh；其中1modkA表示kA的小数部分，即kAkA。例如，表容量12M，种子215A（215A是一个实际效果很好的选择），关键值100k，那么9kh。同样用4000个数插入一个容量为701的Hash表（215A），得到的结果是：测试数据随机数据连续数据最小单元容量：04最大单元容量：157期望容量：5.706135.70613标准差：2.50690.619999从公式中可以看出，这个方法受M的影响是很小的，在M的值比较不适合直接取余法的时候这个方法的表现很好。但是从上面的测试来看，其表现并不是非常理想，且由于浮点运算较多，运行速度较慢。经反复优化，在我的机器上仍需892ns才能完成一次计算，即810个时钟周期，是直接取余法的23倍。3．平方取中法我们把关键字k平方，然后取中间的M2log位作为Hash函数值返回。由于k的每一位都会对其平方中间的若干位产生影响，因此这个方法的效果也是不错的。但是对于比较小的k值效果并不是很理想，实现起来也比较繁琐。为了充分利用Hash表的空间，M最好取2的整数次幂。例如，表容量1624M，关键值100k，那么8kh。用4000个数插入一个容量为512的Hash表（注意这里没有用701，是为了利用Hash表的空间），得到的结果是：测试数据随机数据连续数据最小单元容量：01最大单元容量：1717期望容量：7.81257.8125标准差：2.958042.64501效果比我们想象的要差，尤其是对于连续数据。但由于只有乘法和位运算，该函数的速度是最快的。在我的机器上，一次运算只需要23ns，即19个时钟周期，比直接取余法还要快一些。比较一下这三种方法：实现难度实际效果运行速度其他应用直接取余法易好较快字符串乘积取整法较易较好慢浮点数平方取中法中较好快无从这个表格中我们很容易看出，直接取余法的性价比是最高的，因此也是我们竞赛中用得最多的一种方法。对于实数的Hash函数，我们可以直接利用乘积取整法；而对于标本为其他类型数据的Hash函数，我们可以先将其转换为整数，然后再将其插入Hash表。下面我们来研究把其他类型数据转换成整数的方法。二、字符串的Hash函数字符串本身就可以看成一个256进制（ANSI字符串为128进制）的大整数，因此我们可以利用直接取余法，在线性时间内直接算出Hash函数值。为了保证效果，M仍然不能选择太接近n2的数；尤其是当我们把字符串看成一个p2进制数的时候，选择12pM会使得该字符串的任意一个排列的Hash函数值都相同。（想想看，为什么？）常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞（MD5前一段时间才刚刚被破解）。我从MarkTwain的一篇小说中分别随机抽取了1000个不同的单词和1000个不同的句子，作为短字符串和长字符串的测试数据，然后用不同的Hash函数把它们变成整数，再用直接取余法插入一个容量为1237的Hash表，遇到冲突则用新字符串覆盖旧字符串。通过观察最后“剩下”的字符串的个数，我们可以粗略地得出不同的Hash函数实际效果。短字符串长字符串平均编码难度直接取余数667676671.5易P.J.WeinbergerHash683676679.5难ELFHash683676679.5较难SDBMHash694680687.0易BKDRHash665710687.5较易DJBHash694683688.5较易APHash684698691.0较难RSHash691693692.0较难JSHash684708696.0较易把1000个随机数用直接取余法插入容量为1237的Hash表，其覆盖单元数也只达到了694，可见后面的几种方法已经达到了极限，随机性相当优秀。然而我们却很难选择，因为不存在完美的、既简单又实用的解决方案。我一般选择JSHash或SDBMHash作为字符串的Hash函数。这两个函数的代码如下：unsignedintJSHash(char*str){unsignedinthash=1315423911;//nearlyaprime-1315423911=3*438474637while(*str){hash^=((hash5)+(*str++)+(hash2));}return(hash&0x7FFFFFFF);}unsignedintSDBMHash(char*str){unsignedinthash=0;while(*str){//equivalentto:hash=65599*hash+(*str++);hash=(*str++)+(hash6)+(hash16)-hash;}return(hash&0x7FFFFFFF);}JSHash的运算比较复杂，如果对效果要求不是特别高的话SDBMHash是一个很好的选择。三、排列的Hash函数准确的说，这里我们的研究不再仅仅局限在“Hashing”的工作，而是进化到一个“numerize”的过程，也就是说我们可以在排列和1到mnA的自然数之间建立一一对应．．．．的关系。这样我们就可以利用这个关系来直接定址，或者用作Hash函数；在基于状态压缩的动态规划算法中也能用上。1．背景知识自然数的p进制表示法我们已经很熟悉了，即：mkkkpan0，pak0比如2p便是二进制数，10p便是十进制数。引理：Nn，11!1!nkkkn。证明：对n使用数学归纳法。1)1n时，等式显然成立。2)假设mn时等式成立，即11!1!mkkkm。则1mn时，mkmkkkkkmmmmmmmmn111!1!1!!!!1!1!即1mn时等式亦成立。3)综上所述，Nn，11!1!nkkkn成立。把这个式子变形一下：!11!22!22!111!nnnnn上式和111121ppppppnnn类似。不难证明，从0到1!n的任何自然数m可唯一地表示为!1!2!1121ananamnn其中iai0，1,,2,1ni。甚至在式子后面加上一个!00a也无妨，在后面我们把这一项忽略掉。所以从0到1!n的!n个自然数与12321,,,,,aaaaannn（*）一一对应。另一方面，不难从m算出12321,,,,,aaaaannn。我们可以把序列12321,,,,,aaaaannn理解为一个“变进制数”，也就是第一位二进制，第二位三进制，……，第i位1i进制，……，第1n位n进制。这样，我们就可以方便的使用类似“除p取余法”的方法从一个自然数m算出序列12321,,,,,aaaaannn。由于这样的序列共有!n个，我们很自然的想到把这!n个序列和n个元素的全排列建立一一对应。2．全排列与自然数之一一对应为了方便起见，不妨设n个元素为n,,2,1。对应的规则如下：设序列（*）对应的某一排列npppp21，其中ia可以看做是排列p中数1i所在位置右边比1i小的数的个数。以排列4213为例，它是元素1,2,3,4的一个排列。4的右边比4小的数的数目为3，所以33a。3右边比3小的数的数目为0，即02a。同理11a。所以排列4213对应于变进制的301，也就是十进制的19；反过来也可以从19反推到301，再反推到排列4213。3．更一般性的排列受到这个思路启发，我们同样可以把更一般性的排列与自然数之间建立一一对应关系。想一想从n个元素中选m个的排列数mnA的公式是怎么来的？根据乘法原理，我们有121mnnnnAmn这是由于在排列的第1个位置有n种选择，在排列的第2个位置有1n种选择，……，在排列的第m个位置有1mn种选择。既然这样，我们可以定义一种“m-n变进制数”，使其第1位是1mn进制，第2位是2mn进制，……，第m位是n进制。这样，0到1mnA之间的任意一个自然数k都可以唯一地表示成：111222111aAaAaAakmnmnmmnm其中10imnai，mi1。注意到mkkkmnmnAkmnA11111（证明略，可直接变形结合前面的引理推得），所以从0到1mnA的mnA个自然数可以与序列1221,,,,,aaaaammm一一对应。类似地，可以用取余法从自然数k算出1221,,,,,aaaaammm。我们设n个元素为n,,2,1，从中取出m个。对应关系如下：维护一个首元素下标为．．．．．．0．的线性表L，初始时nL,,2,1。对于某一排列mpppp21，我们从1p开始处理。首先在L中找到1p的下标记为ma，然后删除maL；接着在L中找到2p的下标记为1ma，然后删除1maL……直到1aL被删除为止。以在5个元素1,2,3,4,5中取出2,4,3为例，这时3,5mn。首先在L中取出2，记下13a，L变为1,3,4,5；在L中取出4，记下22a，L变为1,3,5；在L中取出3，记下11a，L变为1,5。因此排列243对应于“3-5变进制数”121，即十进制数19；反过来也可以从十进制数19反推到121，再反推到排列243。各序列及其对应的排列