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

Hash函数的设计优化天津南开中学李羽修Hash的应用字典编译器搜索引擎从Hash表到Hash函数既然Hash的应用如此广泛，一个好的Hash函数则显得尤为重要。在Hash函数的帮助下，Hash表可以处理各种各样的数据整数、实数、字符串、排列组合……Hash函数优劣的评价解决冲突是Hash表的关键冲突越少，Hash表的效率就越高数据分布越均匀，冲突越少Hash函数的随机性越好，数据分布越均匀NodeHeadNodeNodeHeadHeadNodeHeadNodeHeadRootHeadNodeHeadHeadNodeNodeNodeNodeHeadHeadRoot整数的Hash函数最常见的是直接取余法h(k)=kmodM，M为Hash表的容量为了保证随机性，应该尽量使k的每一位都对h(k)产生影响M应选取不太接近2的幂的素数例如k=100,M=12,那么h(k)=4整数的Hash函数把关键字k平方，中间几位受k的每一位影响最大由此想到平方取中法把关键字k平方，取出中间的r位作为h(k)的值此时M=2r整数的Hash函数例子：r=4,k=100k=(1100100)2k2=(10011100010000)2h(k)=(1000)2=8整数的Hash函数另一种方法：利用无理数乘积取整法用k乘以一个(0,1)中的无理数A取出小数部分，乘以M再取出整数部分作为h(k)例：k=100,A=0.61803…,M=12h(k)=9整数的Hash函数比较这三种方法：直接取余法：•实现容易•效果受M影响大乘积取整法•M可以任取，效果好•速度奇慢平方取中法•速度快•不容易推广结论：一般的竞赛应用，直接取余法足矣其他类型数据的Hash函数我们可以把其他类型数据转化为整数，然后再利用整数的Hash函数将其转化为Hash函数值实数还需要转化吗？不需要。范围不太离谱的话可以利用乘积取整法；范围离谱的话……必杀技(自创)：用整数指针指向实数内存，读出来！然后……字符串的Hash函数字符串信息量巨大，无法直接定址如果能充分采集利用每个字符，随机性可以非常好以MD5和SHA1为代表的杂凑函数很难找到碰撞下面主要介绍字符串和排列的Hash函数字符串的Hash函数首先，不管是字符串还是整数，在计算机中的表示都是二进制序列可以把字符串看成256进制的大整数，套用直接取余法M选得好的话，效果还是可以接受的字符串的Hash函数例子：str=“IOI2005”,M=23str=0x494F4932303035,M=0x17h(str)=str%M=13h(“NOI2005”)=1h(“IOI2004”)=12出现了扎堆，这是直接取余法的必然现象字符串的Hash函数常用的函数还有很多，大多是用位运算实现竞赛中要找到一个实现复杂度vs运行效果的平衡点SDBMHash是一个很好的选择字符串的Hash函数初始时hash=0从左到右遍历每一个字符foreachchinstrhash=hash*65599+ch去掉符号位返回字符串的Hash函数例子：str=“IOI2005”hashch00000000‘I’(49)00000049‘O’(4F)00491246‘I’(49)24417F83‘2’(32)还需要继续往下观察吗？不需要了。Hash函数值已经“面目全非”了字符串的Hash函数比较一下相似字符串之SDBMHash函数值SDBMHash(“IOI2005”)=1988023814SDBMHash(“NOI2005”)=626359947SDBMHash(“IOI2004”)=1988023813很遗憾，又出现了扎堆解决方法：在字符串后面附加一个长度信息(借鉴MD5)但是使用这种方法要牺牲一点点速度字符串的Hash函数重新比较：SDBMHash(“IOI2005”)=2134682497SDBMHash(“IOI2004”)=2134616898SDBMHash(“NOI2005”)=781526076只要M不太接近65599，这个效果基本可以差强人意了排列的Hash函数这里的讨论已经不仅仅局限在“hashing”，而是推广到“numerize”，也就是和自然数建立一一对应关系direct-address,状态压缩DP…下面我们研究如何把n个元素的n!个全排列与1~n!之间的自然数建立一一对应Episode:关于进位制(1)数的p进制我们已经很熟悉了每一位逢p进一m=a0p0+a1p1+a2p2+…0≤ai≤p-1可不可以第一位逢2进一，第二位逢3进一，第三位逢4进一……？当然可以Episode:关于进位制(1)我们知道：n!-1=(n-1)(n-1)!+(n-2)(n-2)!+…+1*1!+0*0!pn-1=(p-1)pn-1+(p-1)pn-2+(p-1)pn-3+…+(p-1)p1+(p-1)p0何等的相似！由此我们可以定义“变进制数”：m=a00!+a11!+a22!+…,其中0≤ai≤ia00!多余，可以省略排列的Hash函数回到主题为了方便起见，n个元素我们设为1,2,…,n对于一个排列，我们数一下元素i的右边比i小的元素有几个，记为ai-1显然满足0≤ai≤i，因为“个数”不会是负数；同时比i+1小的元素不会超过i个ai的序列不就是一个“变进制数”嘛！排列的Hash函数“变进制数”的本质就是自然数，我们习惯于把它转化为十进制或二进制表示(使用定义式)同样，我们可以用类似“除p取余法”的方法把十进制数转化成“变进制数”(第一位除2取余，第二位除3取余……)然后再把“变进制数”转化成全排列也很容易于是全排列和自然数的一一对应关系已经完整的建立起来了排列的Hash函数更一般的排列怎么处理？回想一下A(n,m)的公式是怎么来的？根据乘法原理，第一次有n个元素可选，第二次有n-1个元素可选……第m次有n-m+1个元素可选A(n,m)=n(n-1)(n-2)…(n-m+1)第i次选取的时候有n-i+1种可能把这个序号记为am-i+1，可以知道0≤am-i+1≤n-i即0≤ai≤n-m+i-1，其中i=1,2,…,mEpisode:关于进位制(2)既然这样，如果让数的第一位是n-m+1进制，第二位是n-m+2进制，……，第m位是n进制的话可不可以？当然可以注意到A(n,m)-1=(n-m)A(n-m,0)+(n-m+1)A(n-m+1,1)+(n-m+2)A(n-m+2,2)+…+(n-1)A(n-1,m-1)Episode:关于进位制(2)由此我们可以定义“m-n变进制数”：k=amA(n-1,m-1)+am-1A(n-2,m-2)+am-2A(n-3,m-3)+…+a2A(n-m+1,1)+a1A(n-m,0)其中0≤ai≤n-m+i-1，i=1,2,…,m排列的Hash函数再次回到主题我们在生成排列的过程中很自然的生成了一个“m-n变进制数”：只要在生成的过程中维护一个线性表，记下每次的选择就可以了；亦可以相同的方式进行逆向转换同时，“m-n变进制数”与自然数之间的互换也很容易一般性的排列与自然数之间的一一对应也已经建立起来了总结应用：Hash的用处很广泛，不仅仅局限在处理整数方法：对现有方法的推广(256进制数，变进制数等)启示：有时候仅仅关心时间复杂度是不够的，O(1)的算法速度差距也会很大问题：关于组合的Hash函数，我还没有想到好的方法，欢迎大家讨论谢谢大家！Thankyou.