专注于c++

 

【摘要】

Hash是一种在信息学竞赛中经常用到的数据结构。一个好的Hash函数可以很大程度上提高程序的整体时间效率和空间效率。本文对面向各种不同标本（关键值）的Hash函数进行讨论，并对多种常用的Hash函数进行了分析和总结。

 

【关键字】

Hash 函数，字符串，整数，实数，排列组合

 

【正文】

对于一个Hash函数，评价其优劣的标准应为随机性，即对任意一组标本，进入Hash表每一个单元（cell）之概率的平均程度，因为这个概率越平均，数据在表中的分布就越平均，表的空间利用率就越高。由于在竞赛中，标本的性质是无法预知的，因此数学推理将受到很大限制。我们用实验的方法研究这个随机性。

 

一、整数的Hash函数

常用的方法有三种：直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下假定我们的关键字是 ，Hash表的容量是 ，Hash函数为 。

 

1．直接取余法

我们用关键字 除以 ，取余数作为在Hash表中的位置。函数表达式可以写成：

。

例如，表容量 ，关键值 ，那么 。该方法的好处是实现容易且速度快，是很常用的一种方法。但是如果 选择的不好而偏偏标本又很特殊，那么数据在Hash中很容易扎堆而影响效率。

对于 的选择，在经验上，我们一般选择不太接近 的一个素数；如果关键字的值域较小，我们一般在此值域1.1~1.6倍范围内选择。例如 的值域为 ，那么 即为一个不错的选择。竞赛的时候可以写一个素数生成器或干脆自己写一个“比较像素数”的数。

我用4000个数插入一个容量为701的Hash表，得到的结果是：

测试数据	随机数据	连续数据
最小单元容量：	0	5
最大单元容量：	15	6
期望容量：	5.70613	5.70613
标准差：	2.4165	0.455531

 

可见对于随机数据，取余法的最大单元容量达到了期望容量的将近3倍。经测试，在我的机器（Pentium III 866MHz，128MB RAM）上，该函数的运行时间大约是39ns，即大约35个时钟周期。

 

2．乘积取整法

我们用关键字 乘以一个在 中的实数 （最好是无理数），得到一个 之间的实数；取出其小数部分，乘以 ，再取整数部分，即得 在Hash表中的位置。函数表达式可以写成：

；

其中 表示 的小数部分，即 。例如，表容量 ，种子 （ 是一个实际效果很好的选择），关键值 ，那么 。

同样用4000个数插入一个容量为701的Hash表（ ），得到的结果是：

测试数据	随机数据	连续数据
最小单元容量：	0	4
最大单元容量：	15	7
期望容量：	5.70613	5.70613
标准差：	2.5069	0.619999

 

从公式中可以看出，这个方法受 的影响是很小的，在 的值比较不适合直接取余法的时候这个方法的表现很好。但是从上面的测试来看，其表现并不是非常理想，且由于浮点运算较多，运行速度较慢。经反复优化，在我的机器上仍需892ns才能完成一次计算，即810个时钟周期，是直接取余法的23倍。

 

3．平方取中法

我们把关键字 平方，然后取中间的 位作为Hash函数值返回。由于 的每一位都会对其平方中间的若干位产生影响，因此这个方法的效果也是不错的。但是对于比较小的 值效果并不是很理想，实现起来也比较繁琐。为了充分利用Hash表的空间， 最好取2的整数次幂。例如，表容量 ，关键值 ，那么 。

用4000个数插入一个容量为512的Hash表（注意这里没有用701，是为了利用Hash表的空间），得到的结果是：

测试数据	随机数据	连续数据
最小单元容量：	0	1
最大单元容量：	17	17
期望容量：	7.8125	7.8125
标准差：	2.95804	2.64501

 

效果比我们想象的要差，尤其是对于连续数据。但由于只有乘法和位运算，该函数的速度是最快的。在我的机器上，一次运算只需要23ns，即19个时钟周期，比直接取余法还要快一些。

 

比较一下这三种方法：

	实现难度	实际效果	运行速度	其他应用
直接取余法	易	好	较快	字符串
乘积取整法	较易	较好	慢	浮点数
平方取中法	中	较好	快	无

 

从这个表格中我们很容易看出，直接取余法的性价比是最高的，因此也是我们竞赛中用得最多的一种方法。

 

对于实数的Hash函数，我们可以直接利用乘积取整法；而对于标本为其他类型数据的Hash函数，我们可以先将其转换为整数，然后再将其插入Hash表。下面我们来研究把其他类型数据转换成整数的方法。

二、字符串的Hash函数

字符串本身就可以看成一个256进制（ANSI字符串为128进制）的大整数，因此我们可以利用直接取余法，在线性时间内直接算出Hash函数值。为了保证效果， 仍然不能选择太接近 的数；尤其是当我们把字符串看成一个 进制数的时候，选择 会使得该字符串的任意一个排列的Hash函数值都相同。（想想看，为什么？）

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞（MD5前一段时间才刚刚被破解）。

我从Mark Twain的一篇小说中分别随机抽取了1000个不同的单词和1000个不同的句子，作为短字符串和长字符串的测试数据，然后用不同的Hash函数把它们变成整数，再用直接取余法插入一个容量为1237的Hash表，遇到冲突则用新字符串覆盖旧字符串。通过观察最后“剩下”的字符串的个数，我们可以粗略地得出不同的Hash函数实际效果。

	短字符串	长字符串	平均	编码难度
直接取余数	667	676	671.5	易
P. J. Weinberger Hash	683	676	679.5	难
ELF Hash	683	676	679.5	较难
SDBM Hash	694	680	687.0	易
BKDR Hash	665	710	687.5	较易
DJB Hash	694	683	688.5	较易
AP Hash	684	698	691.0	较难
RS Hash	691	693	692.0	较难
JS Hash	684	708	696.0	较易

 

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

unsigned int JSHash(char *str) { unsigned int hash = 1315423911; // nearly a prime - 1315423911 = 3 * 438474637 while (*str) { hash ^= ((hash << 5) + (*str++) + (hash >> 2)); } return (hash & 0x7FFFFFFF); }   unsigned int SDBMHash(char *str) { unsigned int hash = 0; while (*str) { // equivalent to: hash = 65599*hash + (*str++); hash = (*str++) + (hash << 6) + (hash << 16) - hash; } return (hash & 0x7FFFFFFF); }

 

JSHash的运算比较复杂，如果对效果要求不是特别高的话SDBMHash是一个很好的选择。

 

三、排列的Hash函数

准确的说，这里我们的研究不再仅仅局限在“Hashing”的工作，而是进化到一个“numerize”的过程，也就是说我们可以在排列和1到 的自然数之间建立一一对应的关系。这样我们就可以利用这个关系来直接定址，或者用作Hash函数；在基于状态压缩的动态规划算法中也能用上。

 

1．背景知识

自然数的 进制表示法我们已经很熟悉了，即：

，

比如 便是二进制数， 便是十进制数。

引理： ， 。

证明：对 使用数学归纳法。

1)              时，等式显然成立。

2)假设 时等式成立，即 。
则 时，

即 时等式亦成立。

3)综上所述， ， 成立。

把这个式子变形一下：

上式和 类似。不难证明，从0到 的任何自然数 可唯一地表示为

其中 ， 。甚至在式子后面加上一个 也无妨，在后面我们把这一项忽略掉。所以从0到 的 个自然数与

（*）

一一对应。另一方面，不难从 算出 。

我们可以把序列 理解为一个“变进制数”，也就是第一位二进制，第二位三进制，……，第 位 进制，……，第 位 进制。这样，我们就可以方便的使用类似“除 取余法”的方法从一个自然数 算出序列 。由于这样的序列共有 个，我们很自然的想到把这 个序列和 个元素的全排列建立一一对应。

 

2．全排列与自然数之一一对应

为了方便起见，不妨设 个元素为 。对应的规则如下：设序列（*）对应的某一排列 ，其中 可以看做是排列 中数 所在位置右边比 小的数的个数。以排列4213为例，它是元素1,2,3,4的一个排列。4的右边比4小的数的数目为3，所以 。3右边比3小的数的数目为0，即 。同理 。所以排列4213对应于变进制的301，也就是十进制的19；反过来也可以从19反推到301，再反推到排列4213。

 

3．更一般性的排列

受到这个思路启发，我们同样可以把更一般性的排列与自然数之间建立一一对应关系。想一想从 个元素中选 个的排列数 的公式是怎么来的？根据乘法原理，我们有

这是由于在排列的第1个位置有 种选择，在排列的第2个位置有 种选择，……，在排列的第 个位置有 种选择。既然这样，我们可以定义一种“m-n变进制数”，使其第1位是 进制，第2位是 进制，……，第 位是 进制。这样，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，即十进制数19；反过来也可以从十进制数19反推到121，再反推到排列243。各序列及其对应的排列如下表：

 

【总结】

本文对几个常用的Hash函数进行了总结性的介绍和分析，并将其延伸到应用更加广泛的“与自然数建立一一对应”的过程。Hash是一种相当有效的数据结构，充分体现了“空间换时间”的思想。在如今竞赛中内存限制越来越松的情况下，要做到充分利用内存空间来换取宝贵的时间，Hash能够给我们很大帮助。我们应当根据题目的特点，选择适合题目的数据结构来优化算法。对于组合与自然数的一一对应关系，我还没有想到好的方法，欢迎大家讨论。

 

【参考文献】

[1]    Thomas H Cormen, Charles E Leiserson, Ronald L Riverst, Clifford Stein. Introduction to Algorithms. Second Edition. The MIT Press, 2001

[2]    刘汝佳，黄亮. 《算法艺术与信息学竞赛》. 北京：清华大学出版社，2004

[3]    卢开澄，卢华明. 《组合数学》（第3版）. 北京：清华大学出版社，2002

 

【附录】

常用的字符串Hash函数之源代码：

// RS Hash Function unsigned int RSHash(char *str) {     unsigned int b = 378551;     unsigned int a = 63689;     unsigned int hash = 0;       while (*str)     {        hash = hash * a + (*str++);        a *= b;     }       return (hash & 0x7FFFFFFF); }   // JS Hash Function unsigned int JSHash(char *str) {     unsigned int hash = 1315423911;       while (*str)     {        hash ^= ((hash << 5) + (*str++) + (hash >> 2));     }         return (hash & 0x7FFFFFFF); }   // P. J. Weinberger Hash Function unsigned int PJWHash(char *str) {     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)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);     unsigned int hash             = 0;     unsigned int test             = 0;       while (*str)     {        hash = (hash << OneEighth) + (*str++);        if ((test = hash & HighBits) != 0)        {            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));        }     }       return (hash & 0x7FFFFFFF); }   // ELF Hash Function unsigned int ELFHash(char *str) {     unsigned int hash = 0;     unsigned int x    = 0;       while (*str)     {        hash = (hash << 4) + (*str++);        if ((x = hash & 0xF0000000L) != 0)        {            hash ^= (x >> 24);            hash &= ~x;        }     }       return (hash & 0x7FFFFFFF); }   // BKDR Hash Function unsigned 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 & 0x7FFFFFFF); }   // SDBM Hash Function unsigned int SDBMHash(char *str) {     unsigned int hash = 0;       while (*str)     {        hash = (*str++) + (hash << 6) + (hash << 16) - hash;     }       return (hash & 0x7FFFFFFF); }   // DJB Hash Function unsigned int DJBHash(char *str) {     unsigned int hash = 5381;       while (*str)     {        hash += (hash << 5) + (*str++);     }       return (hash & 0x7FFFFFFF); }   // AP Hash Function unsigned int APHash(char *str) {     unsigned int hash = 0;     int i;       for (i=0; *str; i++)     {        if ((i & 1) == 0)        {            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));        }        else        {            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));        }     }       return (hash & 0x7FFFFFFF); }