汇编Hash函数的设计优化

1、Hash函数的设计优化天津南开中学 李羽修【摘要】Hash是一种在信息学竞赛中经常用到的数据结构。一个好的Hash函数可以很大程度上提高程序的整体时间效率和空间效率。本文对面向各种不同标本关键值的Hash函数进行讨论，并对多种常用的Hash函数进行了分析和总结。【关键字】Hash 函数，字符串，整数，实数，排列组合【正文】对于一个Hash函数，评价其优劣的标准应为随机性，即对任意一组标本，进入Hash表每一个单元cell之概率的平均程度，因为这个概率越平均，数据在表中的分布就越平均，表的空间利用率就越高。由于在竞赛中，标本的性质是无法预知的，因此数学推理将受到很大限制。我们用实验的方法研究这个

2、随机性。一、整数的Hash函数常用的方法有三种：直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下假定我们的关键字是，Hash表的容量是，Hash函数为。1直接取余法我们用关键字除以，取余数作为在Hash表中的位置。函数表达式可以写成：。例如，表容量，关键值，那么。该方法的好处是实现容易且速度快，是很常用的一种方法。但是如果选择的不好而偏偏标本又很特殊，那么数据在Hash中很容易扎堆而影响效率。对于的选择，在经验上，我们一般选择不太接近的一个素数；如果关键字的值域较小，我们一般在此值域1.11.6倍范围内选择。例如的值域为，那么即为一个不错的选择。竞赛的时候可以写一个素

3、数生成器或干脆自己写一个“比拟像素数的数。我用4000个数插入一个容量为701的Hash表，得到的结果是：测试数据随机数据连续数据最小单元容量：05最大单元容量：156期望容量：标准差：可见对于随机数据，取余法的最大单元容量到达了期望容量的将近3倍。经测试，在我的机器Pentium III 866MHz，128MB RAM上，该函数的运行时间大约是39ns，即大约35个时钟周期。2乘积取整法我们用关键字乘以一个在中的实数最好是无理数，得到一个之间的实数；取出其小数局部，乘以，再取整数局部，即得在Hash表中的位置。函数表达式可以写成：；其中表示的小数局部，即。例如，表容量，种子是一个实际效果很

4、好的选择，关键值，那么。同样用4000个数插入一个容量为701的Hash表，得到的结果是：测试数据随机数据连续数据最小单元容量：04最大单元容量：157期望容量：标准差：从公式中可以看出，这个方法受的影响是很小的，在的值比拟不适合直接取余法的时候这个方法的表现很好。但是从上面的测试来看，其表现并不是非常理想，且由于浮点运算较多，运行速度较慢。经反复优化，在我的机器上仍需892ns才能完成一次计算，即810个时钟周期，是直接取余法的23倍。3平方取中法我们把关键字平方，然后取中间的位作为Hash函数值返回。由于的每一位都会对其平方中间的假设干位产生影响，因此这个方法的效果也是不错的。但是对于比拟

5、小的值效果并不是很理想，实现起来也比拟繁琐。为了充分利用Hash表的空间，最好取2的整数次幂。例如，表容量，关键值，那么。用4000个数插入一个容量为512的Hash表注意这里没有用701，是为了利用Hash表的空间，得到的结果是：测试数据随机数据连续数据最小单元容量：01最大单元容量：1717期望容量：标准差：效果比我们想象的要差，尤其是对于连续数据。但由于只有乘法和位运算，该函数的速度是最快的。在我的机器上，一次运算只需要23ns，即19个时钟周期，比直接取余法还要快一些。比拟一下这三种方法：实现难度实际效果运行速度其他应用直接取余法易好较快字符串乘积取整法较易较好慢浮点数平方取中法中较好

6、快无从这个表格中我们很容易看出，直接取余法的性价比是最高的，因此也是我们竞赛中用得最多的一种方法。对于实数的Hash函数，我们可以直接利用乘积取整法；而对于标本为其他类型数据的Hash函数，我们可以先将其转换为整数，然后再将其插入Hash表。下面我们来研究把其他类型数据转换成整数的方法。二、字符串的Hash函数字符串本身就可以看成一个256进制ANSI字符串为128进制的大整数，因此我们可以利用直接取余法，在线性时间内直接算出Hash函数值。为了保证效果，仍然不能选择太接近的数；尤其是当我们把字符串看成一个进制数的时候，选择会使得该字符串的任意一个排列的Hash函数值都相同。想想看，为什么？常

7、用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞MD5前一段时间才刚刚被破解。我从Mark Twain的一篇小说中分别随机抽取了1000个不同的单词和1000个不同的句子，作为短字符串和长字符串的测试数据，然后用不同的Hash函数把它们变成整数，再用直接取余法插入一个容量为1237的Hash表，遇到冲突那么用新字符串覆盖旧字符串。通过观察最后“剩下的字符串的个数，我们可以粗略地得出不同的Hash函数实际效果。短字符串长字符串平均编码

8、难度直接取余数667676易P. J. Weinberger Hash683676难ELF Hash683676较难SDBM Hash694680易BKDR Hash665710较易DJB Hash694683较易AP Hash684698较难RS Hash691693较难JS Hash684708较易把1000个随机数用直接取余法插入容量为1237的Hash表，其覆盖单元数也只到达了694，可见后面的几种方法已经到达了极限，随机性相当优秀。然而我们却很难选择，因为不存在完美的、既简单又实用的解决方案。我一般选择JS Hash或SDBM Hash作为字符串的Hash函数。这两个函数的代码如下：

9、unsigned int JSHash(char *str)unsigned int hash = 1315423911; / nearly a prime - 1315423911 = 3 * 438474637while (*str)hash = (hash 2);return (hash & 0 x7FFFFFFF);unsigned int SDBMHash(char *str)unsigned int hash = 0;while (*str)/ equivalent to: hash = 65599*hash + (*str+);hash = (*str+) + (hash 6)

10、+ (hash 16) - hash;return (hash & 0 x7FFFFFFF);JSHash的运算比拟复杂，如果对效果要求不是特别高的话SDBMHash是一个很好的选择。三、排列的Hash函数准确的说，这里我们的研究不再仅仅局限在“Hashing的工作，而是进化到一个“numerize的过程，也就是说我们可以在排列和1到的自然数之间建立一一对应的关系。这样我们就可以利用这个关系来直接定址，或者用作Hash函数；在基于状态压缩的动态规划算法中也能用上。1背景知识自然数的进制表示法我们已经很熟悉了，即：， 比方便是二进制数，便是十进制数。引理：，。证明：对使用数学归纳法。时，等式显然

11、成立。假设时等式成立，即。那么时，即时等式亦成立。综上所述，成立。把这个式子变形一下：上式和类似。不难证明，从0到的任何自然数可唯一地表示为其中，。甚至在式子后面加上一个也无妨，在后面我们把这一项忽略掉。所以从0到的个自然数与*一一对应。另一方面，不难从算出。我们可以把序列理解为一个“变进制数，也就是第一位二进制，第二位三进制，第位进制，第位进制。这样，我们就可以方便的使用类似“除取余法的方法从一个自然数算出序列。由于这样的序列共有个，我们很自然的想到把这个序列和个元素的全排列建立一一对应。2全排列与自然数之一一对应为了方便起见，不妨设个元素为。对应的规那么如下：设序列*对应的某一排列，其中可

12、以看做是排列中数所在位置右边比小的数的个数。以排列4213为例，它是元素1,2,3,4的一个排列。4的右边比4小的数的数目为3，所以。3右边比3小的数的数目为0，即。同理。所以排列4213对应于变进制的301，也就是十进制的19；反过来也可以从19反推到301，再反推到排列4213。3更一般性的排列受到这个思路启发，我们同样可以把更一般性的排列与自然数之间建立一一对应关系。想一想从个元素中选个的排列数的公式是怎么来的？根据乘法原理，我们有这是由于在排列的第1个位置有种选择，在排列的第2个位置有种选择，在排列的第个位置有种选择。既然这样，我们可以定义一种“m-n变进制数，使其第1位是进制，第2位

13、是进制，第位是进制。这样，0到之间的任意一个自然数都可以唯一地表示成：其中，。注意到证明略，可直接变形结合前面的引理推得，所以从0到的个自然数可以与序列一一对应。类似地，可以用取余法从自然数算出。我们设个元素为，从中取出个。对应关系如下：维护一个首元素下标为0的线性表，初始时。对于某一排列，我们从开始处理。首先在中找到的下标记为，然后删除；接着在中找到的下标记为，然后删除直到被删除为止。以在5个元素1,2,3,4,5中取出2,4,3为例，这时。首先在中取出2，记下，变为1,3,4,5；在中取出4，记下，变为1,3,5；在中取出3，记下，变为1,5。因此排列243对应于“3-5变进制数121，即

14、十进制数19；反过来也可以从十进制数19反推到121，再反推到排列243。各序列及其对应的排列如下表：123000034122030124001134222131125002234522232132010335123033134011435223134135012535423235142020641230036143021741330137145022841530238152030942131039153031104233114015403211425312412131001243132042214101134323214321510214435322442311101545133045234

15、11116452331462351121745333247241120185124004824312119513401492451222051440250251130215214105125313122523411522541322352441253312200245314205431420125532421553152022653442256321210275414305732421128542431583252122954343259【总结】本文对几个常用的Hash函数进行了总结性的介绍和分析，并将其延伸到应用更加广泛的“与自然数建立一一对应的过程。Hash是一种相当有效的数据结构，充分表

16、达了“空间换时间的思想。在如今竞赛中内存限制越来越松的情况下，要做到充分利用内存空间来换取珍贵的时间，Hash能够给我们很大帮助。我们应当根据题目的特点，选择适合题目的数据结构来优化算法。对于组合与自然数的一一对应关系，我还没有想到好的方法，欢送大家讨论。【参考文献】Thomas H Cormen, Charles E Leiserson, Ronald L Riverst, Clifford Stald L Riverst, Clifford Stald L Riverst, Clifford Stald L Riverst, Clifford Stald L Riverst, Cliffo

17、rd Stald L Riverst, Clifford Stein. Introduction to Algorithms. Second Edition. The MIT Press, 2001刘汝佳，黄亮. ald L Riverst, Clifford St信息学竞赛?. 北京：清华大学出版社，2004卢开澄，卢华明. ?组合数学?第3版. 北京：清华大学出版社，2002【附录】常用的字符串Hash函数之源代码：/ RS Hash Functionunsigned int RSHash(char *str)unsigned int b = 378551;unsigned int a =

18、 63689;unsigned int hash = 0;while (*str)hash = hash * a + (*str+);a *= b;return (hash & 0 x7FFFFFFF);/ JS Hash Functionunsigned int JSHash(char *str)unsigned int hash = 1315423911;while (*str)hash = (hash 2);return (hash & 0 x7FFFFFFF);/ P. J. Weinberger Hash Functionunsigned int PJWHash(char *str)

19、unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);unsigned int ThreeQuarters = (unsigned int)(BitsInUnignedInt * 3) / 4);unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);unsigned int HighBits = (unsigned int)(0 xFFFFFFFF) (BitsInUnignedInt - OneEighth);unsigned in

20、t hash = 0;unsigned int test = 0;while (*str)hash = (hash ThreeQuarters) & (HighBits);return (hash & 0 x7FFFFFFF);/ ELF Hash Functionunsigned int ELFHash(char *str)unsigned int hash = 0;unsigned int x = 0;while (*str)hash = (hash 24);hash &= x;return (hash & 0 x7FFFFFFF);/ BKDR Hash Functionunsigned

21、 int BKDRHash(char *str)unsigned int seed = 131; / 31 131 1313 13131 131313 etc.unsigned int hash = 0;while (*str)hash = hash * seed + (*str+);return (hash & 0 x7FFFFFFF);/ SDBM Hash Functionunsigned int SDBMHash(char *str)unsigned int hash = 0;while (*str)hash = (*str+) + (hash 6) + (hash 16) - has

22、h;return (hash & 0 x7FFFFFFF);/ DJB Hash Functionunsigned int DJBHash(char *str)unsigned int hash = 5381;while (*str)hash += (hash 5) + (*str+);return (hash & 0 x7FFFFFFF);/ AP Hash Functionunsigned int APHash(char *str)unsigned int hash = 0;int i;for (i=0; *str; i+)if (i & 1) = 0)hash = (hash 3);el

23、sehash = (hash 5);return (hash & 0 x7FFFFFFF); while ilen do begin i:=nexti; write(linei.way); end; end;begin propare; init; bfs; print;我们经常使用的数的进制为“常数进制，即始终逢p进1。例如，p进制数K可表示为K = a0*p0 + a1*p1 + a2*p2 + . + an*pn 其中0 = ai = p-1，它可以表示任何一个自然数。对于这种常数进制表示法，以及各种进制之间的转换大家应该是很熟悉的了，但大家可能很少听说变进制数。这里我要介绍一种特殊的变

24、进制数，它能够被用来实现 全排列的Hash函数，并且该Hash函数能够实现完美的防碰撞和空间利用不会发生碰撞，且所有空间被完全使用，不多不少。这种全排列Hash函数也 被称为全排列数化技术。下面，我们就来看看这种变进制数。我们考查这样一种变进制数：第1位逢2进1，第2位逢3进1，第n位逢n+1进1。它的表示形式为K = a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i，也可以扩展为如下形式因为按定义a0始终为0，以与p进制表示相对应：K = a0*0! + a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i。

25、后面的变进制数均指这种变进制数，且采用前一种表示法先让我们来考查一下该变进制数的进位是否正确。假设变进制数K的第i位ai为i+1，需要进位，而ai*i!=(i+1)*i!=1*(i+1)!，即正确的向高位进1。这说明该变进制数能够正确进位，从而是一种合法的计数方式。接下来我们考查n位变进制数K的性质：1当所有位ai均为i时，此时K有最大值MAXK = 1*1! + 2*2! + 3*3! + . + n*n! = 1! + 1*1! + 2*2! + 3*3! + . + n*n! - 1 = (1+1)*1! + 2*2! + 3*3! + . + n*n! - 1 = 2! + 2*2!

26、+ 3*3! + . + n*n! - 1 = . = (n+1)!-1因此，n位K进制数的最大值为(n+1)!-1。2当所有位ai均为0时，此时K有最小值0。因此，n位变进制数能够表示0到(n+1)!-1的范围内的所有自然数，共(n+1)!个。在一些状态空间搜索算法中，我们需要快速判断某个状态是否已经出现，此时常常使用Hash函数来实现。其中，有一类特殊的状态空间，它们是由全排列产生 的，比方N数码问题。对于n个元素的全排列，共产生n!个不同的排列或状态。下面将讨论如何使用这里的变进制数来实现一个针对全排列的Hash函数。从数的角度来看，全排列和变进制数都用到了阶乘。如果我们能够用0到n!-

27、1这n!个连续的变进制数来表示n个元素的所有排列，那么就能够把全排列完全地 数化，建立起全排列和自然数之间一一对应的关系，也就实现了一个完美的Hash函数。那么，我们的想法能否实现呢？答案是肯定的，下面将进行讨论。假设我们有b0,b1,b2,b3,.,bn共n+1个不同的元素，并假设各元素之间有一种次序关系 b0b1b2.bn。对它们进行全排列，共产生(n+1)!种不同的排列。对于产生的任一排列 c0,c1,c2,.,cn，其中第i个元素ci1 = i = n与它前面的i个元素构成的逆序对的个数为di0 = di = i，那么我们得到一个逆序数序列d1,d2,.,dn0 = di = i。这不

28、就是前面的n位变进制数的各个位么？于是，我们用n位变进制数M来表示该排列：M = d1*1! + d2*2! + . + dn*n!因此，每个排列都可以按这种方式表示成一个n位变进制数。下面，我们来考查n位变进制数能否与n+1个元素的全排列建立起一一对应的关系。由于n位变进制数能表示(n+1)!个不同的数，而n+1个元素的全排列刚好有(n+1)!个不同的排列，且每一个排列都已经能表示成一个n位变进制数。如果我们能够证明任意两个不同的排列产生两个不同的变进制数，那么我们就可以得出结论： 定理1 n+1个元素的全排列的每一个排列对应着一个不同的n位变进制数。/*补充： 什么是逆序数：跟标准列相反序

29、数的总和 比方说 标准列是1 2 3 4 5 那么 5 4 3 2 1 的逆序数算法： 看第二个，4之前有一个5，在标准列中5在4的后面，所以记1个 类似的，第三个 3 之前有 4 5 都是在标准列中3的后面，所以记2个 同样的，2 之前有3个，1之前有4个 将这些数加起来就是逆序数=1+2+3+4=10 再举一个 2 4 3 1 5 4 之前有0个 3 之前有1个 1 之前有3个 5 之前有0个 所以逆序数就是1+3=4 */对于全排列的任意两个不同的排列p0,p1,p2,.,pn排列P和q0,q1,q2,.,qn排列Q，从后往前查找第一个不相同的元素，分别记为pi和qi0 i pi，那么,

30、如果在排列Q中qi之前的元素x与qi构成逆序对，即有x qi，那么在排列P中pi之前也有相同元素x pi因为x qi且qi pi，即在排列P中pi之前的元素x也与pi构成逆序对，所以pi的逆序数大于等于qi的逆序数。又qi与pi在排列P中构成pi的逆序对，所以pi的 逆序数大于qi的逆序数。2同理，如果pi qi，那么qi的逆序数大于pi的逆序数。因此，由1和2知，排列P和排列Q对应的变进制数至少有第i位不相同，即全排列的任意两个不同的排列具有不同的变进制数。至此，定理1得证。计算n个元素的一个排列的变进制数的算法大致如下时间复杂度为O(n2)：template size_t Permutat

31、ionToNumber(const T permutation, int n)/ n不能太大，否那么会溢出如果size_t为32位，那么n = 12size_t result = 0;for (int j = 1; j n; +j) int count = 0; for (int k = 0; k permutationj) +count; / factorialsj保存着j! result += count * factorialsj;return result;总结：/实际上，如果只是求逆序数 可以做到O(n logn)，时间消耗在求逆序数上，求逆序数相当于求排列的次数，所以是O(n lo

32、gn)的据说还可以用树状数组优化。举例：例如三个元素的排列排列 逆序 Hash123 000 0132 001 2213 010 1231 002 4312 011 3321 012 5说明：1由于n!是一个很大的数，因此一般只能用于较小的n。2有了计算排列的变进制数的算法，我们就可以使用一个大小为n!的数组来保存每一个排列的状态，使用排列的变进制数作为数组下标，从而实现状态的快速检索。如果只是标记状态是否出现，那么可以用一位来标记状态。end很简单的思想是用for一遍以前搜过的状态。但是，八数码问题的状态共9！，显然for在时间上无法承受。另外一种思想是把这9位数排成一列，转化成一个10进制

33、的数进行hash，但空间上的问题有无法解决了。 显然，我们需要的是一个能够全排列的hash，而下面得这篇文章也就介绍了对于一个n12的全排列状态，我们应该怎样完成hash判重 我们经常使用的数的进制为“常数进制，即始终逢p进1。例如，p进制数K可表示为 K = a0*p0 + a1*p1 + a2*p2 + . + an*pn 其中0 = ai = p-1，它可以表示任何一个自然数。对于这种常数进制表示法，以及各种进制之间的转换大家应该是很熟悉的了，但大家可能很少听说变进制数。这里我要介绍一种特殊的变进制数，它能够被用来实现全排列的Hash函数，并且该Hash函数能够实现完美的防碰撞和空间利用

34、不会发生碰撞，且所有空间被完全使用，不多不少。这种全排列Hash函数也被称为全排列数化技术。下面，我们就来看看这种变进制数。我们考查这样一种变进制数：第1位逢2进1，第2位逢3进1，第n位逢n+1进1。它的表示形式为 K = a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i，也可以扩展为如下形式因为按定义a0始终为0，以与p进制表示相对应： K = a0*0! + a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i。后面的变进制数均指这种变进制数，且采用前一种表示法先让我们来考查一下该变进制数的进位是否正确。

35、假设变进制数K的第i位ai为i+1，需要进位，而ai*i!=(i+1)*i!=1*(i+1)!，即正确的向高位进1。这说明该变进制数能够正确进位，从而是一种合法的计数方式。接下来我们考查n位变进制数K的性质：1当所有位ai均为i时，此时K有最大值 MAXK = 1*1! + 2*2! + 3*3! + . + n*n! = 1! + 1*1! + 2*2! + 3*3! + . + n*n! - 1 = (1+1)*1! + 2*2! + 3*3! + . + n*n! - 1 = 2! + 2*2! + 3*3! + . + n*n! - 1 = . = (n+1)!-1 因此，n位K进制数

36、的最大值为(n+1)!-1。2当所有位ai均为0时，此时K有最小值0。因此，n位变进制数能够表示0到(n+1)!-1的范围内的所有自然数，共(n+1)!个。在一些状态空间搜索算法中，我们需要快速判断某个状态是否已经出现，此时常常使用Hash函数来实现。其中，有一类特殊的状态空间，它们是由全排列产生的，比方N数码问题。对于n个元素的全排列，共产生n!个不同的排列或状态。下面将讨论如何使用这里的变进制数来实现一个针对全排列的Hash函数。从数的角度来看，全排列和变进制数都用到了阶乘。如果我们能够用0到n!-1这n!个连续的变进制数来表示n个元素的所有排列，那么就能够把全排列完全地数化，建立起全排列

37、和自然数之间一一对应的关系，也就实现了一个完美的Hash函数。那么，我们的想法能否实现呢？答案是肯定的，下面将进行讨论。假设我们有b0,b1,b2,b3,.,bn共n+1个不同的元素，并假设各元素之间有一种次序关系 b0b1b2.bn。对它们进行全排列，共产生(n+1)!种不同的排列。对于产生的任一排列 c0,c1,c2,.,cn，其中第i个元素ci1 = i = n与它前面的i个元素构成的逆序对的个数为di0 = di = i，那么我们得到一个逆序数序列d1,d2,.,dn0 = di = i。这不就是前面的n位变进制数的各个位么？于是，我们用n位变进制数M来表示该排列： M = d1*1!

38、 + d2*2! + . + dn*n!因此，每个排列都可以按这种方式表示成一个n位变进制数。下面，我们来考查n位变进制数能否与n+1个元素的全排列建立起一一对应的关系。由于n位变进制数能表示(n+1)!个不同的数，而n+1个元素的全排列刚好有(n+1)!个不同的排列，且每一个排列都已经能表示成一个n位变进制数。如果我们能够证明任意两个不同的排列产生两个不同的变进制数，那么我们就可以得出结论： 定理1 n+1个元素的全排列的每一个排列对应着一个不同的n位变进制数。对于全排列的任意两个不同的排列p0,p1,p2,.,pn排列P和q0,q1,q2,.,qn排列Q，从后往前查找第一个不相同的元素，分

39、别记为pi和qi0 i pi，那么,如果在排列Q中qi之前的元素x与qi构成逆序对，即有x qi，那么在排列P中pi之前也有相同元素x pi因为x qi且qi pi，即在排列P中pi之前的元素x也与pi构成逆序对，所以pi的逆序数大于等于qi的逆序数。又qi与pi在排列P中构成pi的逆序对，所以pi的逆序数大于qi的逆序数。2同理，如果pi qi，那么qi的逆序数大于pi的逆序数。因此，由1和2知，排列P和排列Q对应的变进制数至少有第i位不相同，即全排列的任意两个不同的排列具有不同的变进制数。至此，定理1得证。 我把上面的定理总结简化了一下，具体的内容是这样的1、 计算出阶乘factorial1n-1的数值，存放在数组factorial中2、 对于一个随机得到的全排列a。从第二位开始设为ai，计算在i之前有多少个比ai大的数也就是ai和aj构成逆序对ji，设为count个3、 让hash值+count*factoriali-1； 以下的伪代码给出了hash函数对一个全排列的过程function gethash(全排列a):longint; begin gethash:=0; for i:=2 to n do /注意，一定是第二位，因为从第二位开始才可能出