现在的位置: 首页 > 综合 > 正文

整数的Hash函数

2013年09月10日 ⁄ 综合 ⁄ 共 2603字 ⁄ 字号 评论关闭

一、整数的Hash函数

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

1.直接取余法

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

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

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

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

测试数据

随机数据

连续数据

最小单元容量:

0

5

最大单元容量:

15

6

期望容量:

5.70613

5.70613

标准差:

2.4165

0.455531

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

2.乘积取整法

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

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

同样用4000个数插入一个容量为701Hash表(),得到的结果是:

测试数据

随机数据

连续数据

最小单元容量:

0

4

最大单元容量:

15

7

期望容量:

5.70613

5.70613

标准差:

2.5069

0.619999

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

3.平方取中法

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

4000个数插入一个容量为512Hash表(注意这里没有用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函数还有ELFHashAPHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞(MD5前一段时间才刚刚被破解)。

我从Mark Twain的一篇小说中分别随机抽取了1000不同的单词和1000不同的句子,作为短字符串和长字符串的测试数据,然后用不同的Hash函数把它们变成整数,再用直接取余法插入一个容量为1237Hash表,遇到冲突则用新字符串覆盖旧字符串。通过观察最后“剩下”的字符串的个数,我们可以粗略地得出不同的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个随机数用直接取余法插入容量为1237Hash表,其覆盖单元数也只达到了694,可见后面的几种方法已经达到了极限,随机性相当优秀。然而我们却很难选择,因为不存在完美的、既简单又实用的解决方案。我一般选择JS HashSDBM
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是一个很好的选择。

抱歉!评论已关闭.