Hash 函数的设计优化
一、整数的 Hash 函数
常用的方法有三种:直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下
假定我们的关键字是 ,Hash 表的容量是 ,Hash 函数为 。
1.直接取余法
我们用关键字 除以 ,取余数作为在 Hash 表中的位置。函数表达式可以写成:
。
例如,表容量 ,关键值 ,那么 。该方法的好处是实现容易且速度快,是很常用的一
种方法。但是如果 选择的不好而偏偏标本又很特殊,那么数据在 Hash 中很容易扎堆而影响效率。
对于 的选择,在经验上,我们一般选择不太接近 的一个素数;如果关键字的值域较小,我们一般在
此值域 1.1~1.6 倍范围内选择。例如 的值域为 ,那么 即为一个不错的选择。竞赛的时候可
以写一个素数生成器或干脆自己写一个“比较像素数”的数。
2.乘积取整法
我们用关键字 乘以一个在 中的实数 (最好是无理数),得到一个 之间的实数;取出其小
数部分,乘以 ,再取整数部分,即得 在 Hash 表中的位置。函数表达式可以写成:
;
其中 表示 的小数部分,即 。例如,表容量 ,种子 (
是一个实际效果很好的选择),关键值 ,那么 。
3.平方取中法
我们把关键字 平方,然后取中间的 位作为 Hash 函数值返回。由于 的每一位都会对其平方中
间的若干位产生影响,因此这个方法的效果也是不错的。但是对于比较小的 值效果并不是很理想,实现起来
也比较繁琐。为了充分利用 Hash 表的空间, 最好取 2 的整数次幂。例如,表容量 ,关键值
,那么 。
比较一下这三种方法:
实现难度 实际效果 运行速度 其他应用
直接取余法 易 好 较快 字符串
乘积取整法 较易 较好 慢 浮点数
平方取中法 中 较好 快 无
从这个表格中我们很容易看出,直接取余法的性价比是最高的,因此也是我们竞赛中用得最多的一种方法。
对于实数的 Hash 函数,我们可以直接利用乘积取整法;而对于标本为其他类型数据的 Hash 函数,我们可
以先将其转换为整数,然后再将其插入 Hash 表。下面我们来研究把其他类型数据转换成整数的方法。
二、字符串的 Hash 函数
字符串本身就可以看成一个 256 进制(ANSI 字符串为 128 进制)的大整数,因此我们可以利用直接取余法,
在线性时间内直接算出 Hash 函数值。为了保证效果, 仍然不能选择太接近 的数;尤其是当我们把字符
串看成一个 进制数的时候,选择 会使得该字符串的任意一个排列的 Hash 函数值都相同。(想想
看,为什么?)