【摘要】
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。各序列及其对应的排列如下表:
|
|
|
|
|
|
123
|
000
|
0
|
341
|
220
|
30
|
124
|
001
|
1
|
342
|
221
|
31
|
125
|
002
|
2
|
345
|
222
|
32
|
132
|
010
|
3
|
351
|
230
|
33
|
134
|
011
|
4
|
352
|
231
|
34
|
135
|
012
|
5
|
354
|
232
|
35
|
142
|
020
|
6
|
412
|
300
|
36
|
143
|
021
|
7
|
413
|
301
|
37
|
145
|
022
|
8
|
415
|
302
|
38
|
152
|
030
|
9
|
421
|
310
|
39
|
153
|
031
|
10
|
423
|
311
|
40
|
154
|
032
|
11
|
425
|
312
|
41
|
213
|
100
|
12
|
431
|
320
|
42
|
214
|
101
|
13
|
432
|
321
|
43
|
215
|
102
|
14
|
435
|
322
|
44
|
231
|
110
|
15
|
451
|
330
|
45
|
234
|
111
|
16
|
452
|
331
|
46
|
235
|
112
|
17
|
453
|
332
|
47
|
241
|
120
|
18
|
512
|
400
|
48
|
243
|
121
|
19
|
513
|
401
|
49
|
245
|
122
|
20
|
514
|
402
|
50
|
251
|
130
|
21
|
521
|
410
|
51
|
253
|
131
|
22
|
523
|
411
|
52
|
254
|
132
|
23
|
524
|
412
|
53
|
312
|
200
|
24
|
531
|
420
|
54
|
314
|
201
|
25
|
532
|
421
|
55
|
315
|
202
|
26
|
534
|
422
|
56
|
321
|
210
|
27
|
541
|
430
|
57
|
324
|
211
|
28
|
542
|
431
|
58
|
325
|
212
|
29
|
543
|
432
|
59
|
【总结】
本文对几个常用的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);
}
|