算法合集之《hash函数的设计优化》

《算法合集之《hash函数的设计优化》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Hash函数的设计优化天津南开中学李羽修【摘要】Hash是一种在信息学竞赛中经常用到的数据结构。一个好的Hash函数可以很大程度上提高程序的整体时间效率和空间效率。本文对面向各种不同标本（关键值）的Hash函数进行讨论，并对多种常用的Hash函数进行了分析和总结。【关键字】Hash函数，字符串，整数，实数，排列组合【正文】对于一个Hash函数，评价其优劣的标准应为随机性，即对任意一组标本，进入Hash表每一个单元（cell）之概率的平均程度，因为这个概率越平均，数据在表中的分布就越平均，表的空间利用率就越高。由于在竞赛中，标本的性质是无法预知的，因此数学推理将受到很大限制。

2、我们用实验的方法研究这个随机性。一、整数的Hash函数常用的方法有三种：直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下假定我们的关键字是，Hash表的容量是，Hash函数为。1．直接取余法我们用关键字除以，取余数作为在Hash表中的位置。函数表达式可以写成：。例如，表容量，关键值，那么。该方法的好处是实现容易且速度快，是很常用的一种方法。但是如果选择的不好而偏偏标本又很特殊，那么数据在Hash中很容易扎堆而影响效率。对于的选择，在经验上，我们一般选择不太接近的一个素数；如果关键字的值域较小，我们一般在此值域1.1~1.6倍范围内选择。例如的值域为

3、，那么即为一个不错的选择。竞赛的时候可以写一个素数生成器或干脆自己写一个“比较像素数”的数。我用4000个数插入一个容量为701的Hash表，得到的结果是：测试数据随机数据连续数据最小单元容量：05最大单元容量：156期望容量：5.706135.70613标准差：2.41650.455531可见对于随机数据，取余法的最大单元容量达到了期望容量的将近3倍。经测试，在我的机器（PentiumIII866MHz，128MBRAM）上，该函数的运行时间大约是39ns，即大约35个时钟周期。2．乘积取整法我们用关键字乘以一个在中的实数（最好是无理数），得到一个之间的实数；取出其小数部

4、分，乘以，再取整数部分，即得在Hash表中的位置。函数表达式可以写成：；其中表示的小数部分，即。例如，表容量，种子（是一个实际效果很好的选择），关键值，那么。同样用4000个数插入一个容量为701的Hash表（），得到的结果是：测试数据随机数据连续数据最小单元容量：04最大单元容量：157期望容量：5.706135.70613标准差：2.50690.619999从公式中可以看出，这个方法受的影响是很小的，在的值比较不适合直接取余法的时候这个方法的表现很好。但是从上面的测试来看，其表现并不是非常理想，且由于浮点运算较多，运行速度较慢。经反复优化，在我的机器上仍需892ns才能

5、完成一次计算，即810个时钟周期，是直接取余法的23倍。3．平方取中法我们把关键字平方，然后取中间的位作为Hash函数值返回。由于的每一位都会对其平方中间的若干位产生影响，因此这个方法的效果也是不错的。但是对于比较小的值效果并不是很理想，实现起来也比较繁琐。为了充分利用Hash表的空间，最好取2的整数次幂。例如，表容量，关键值，那么。用4000个数插入一个容量为512的Hash表（注意这里没有用701，是为了利用Hash表的空间），得到的结果是：测试数据随机数据连续数据最小单元容量：01最大单元容量：1717期望容量：7.81257.8125标准差：2.958042.645

6、01效果比我们想象的要差，尤其是对于连续数据。但由于只有乘法和位运算，该函数的速度是最快的。在我的机器上，一次运算只需要23ns，即19个时钟周期，比直接取余法还要快一些。比较一下这三种方法：实现难度实际效果运行速度其他应用直接取余法易好较快字符串乘积取整法较易较好慢浮点数平方取中法中较好快无从这个表格中我们很容易看出，直接取余法的性价比是最高的，因此也是我们竞赛中用得最多的一种方法。对于实数的Hash函数，我们可以直接利用乘积取整法；而对于标本为其他类型数据的Hash函数，我们可以先将其转换为整数，然后再将其插入Hash表。下面我们来研究把其他类型数据转换成整数的方法。二

7、、字符串的Hash函数字符串本身就可以看成一个256进制（ANSI字符串为128进制）的大整数，因此我们可以利用直接取余法，在线性时间内直接算出Hash函数值。为了保证效果，仍然不能选择太接近的数；尤其是当我们把字符串看成一个进制数的时候，选择会使得该字符串的任意一个排列的Hash函数值都相同。（想想看，为什么？）常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可