算法合集之Hash函数的设计优化.doc

Hash函数的设计优化 天津南开中学 李羽修 【摘要】 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函数值都相同。（想想看，为什么？）