hash函数的设计优化.pptx

Hash函数的设计优化 Hash的应用字典编译器有哪些信誉好的足球投注网站引擎从Hash表到Hash函数既然Hash的应用如此广泛，一个好的Hash函数则显得尤为重要。在Hash函数的帮助下，Hash表可以处理各种各样的数据整数、实数、字符串、排列组合……Hash函数优劣的评价解决冲突是Hash表的关键冲突越少，Hash表的效率就越高数据分布越均匀，冲突越少Hash函数的随机性越好，数据分布越均匀整数的Hash函数最常见的是直接取余法h(k) = k mod M，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 = 100k = (1100100)2k2 = (10011 1000 10000)2h(k) = (1000)2 = 8整数的Hash函数另一种方法：利用无理数乘积取整法用 k 乘以一个(0,1)中的无理数 A取出小数部分，乘以 M再取出整数部分作为 h(k)例：k = 100, A = 0.61803…, M = 12h(k) = 9整数的Hash函数比较这三种方法：直接取余法：实现容易效果受 M 影响大乘积取整法M 可以任取，效果好速度奇慢平方取中法速度快不容易推广结论：一般的竞赛应用，直接取余法足矣其他类型数据的Hash函数我们可以把其他类型数据转化为整数，然后再利用整数的Hash函数将其转化为Hash函数值实数还需要转化吗？不需要。范围不太离谱的话可以利用乘积取整法；范围离谱的话……必杀技(自创)：用整数指针指向实数内存，读出来！然后……字符串的Hash函数字符串信息量巨大，无法直接定址如果能充分采集利用每个字符，随机性可以非常好以 MD5 和 SHA1 为代表的杂凑函数很难找到碰撞下面主要介绍字符串和排列的Hash函数字符串的Hash函数首先，不管是字符串还是整数，在计算机中的表示都是二进制序列可以把字符串看成 256 进制的大整数，套用直接取余法M 选得好的话，效果还是可以接受的字符串的Hash函数例子：str = “IOI2005”, M = 23str = 0x494F4932303035, M = 0x17h(str) = str % M = 13h(“NOI2005”) = 1h(“IOI2004”) = 12出现了扎堆，这是直接取余法的必然现象字符串的Hash函数常用的函数还有很多，大多是用位运算实现竞赛中要找到一个实现复杂度 vs 运行效果的平衡点SDBMHash是一个很好的选择字符串的Hash函数初始时hash = 0从左到右遍历每一个字符for each ch in str hash = hash * 65599 + ch去掉符号位返回字符串的Hash函数例子：str = “IOI2005”hash ch00 00 00 00‘I’ (49)00 00 00 49‘O’ (4F)00 49 12 46‘I’ (49)24 41 7F 83‘2’ (32)还需要继续往下观察吗？不需要了。Hash函数值已经“面目全非”了字符串的Hash函数比较一下相似字符串之SDBMHash函数值SDBMHash(“IOI2005”) = 1988023814SDBMHash(“NOI2005”) = 626359947SDBMHash(“IOI2004”) = 1988023813很遗憾，又出现了扎堆解决方法：在字符串后面附加一个长度信息(借鉴MD5)但是使用这种方法要牺牲一点点速度字符串的Hash函数重新比较：SDBMHash(“IOI2005”) = 2134682497SDBMHash(“IOI2004”) = 2134616898SDBMHash(“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 =