李羽修 Hash函数的设计优化.pptVIP

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 = 100 k = (1100100)2 k2 = (10011 1000 10000)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 从左到右遍历每一个字符 for each ch in str hash = hash * 65599 + ch 去掉符号位返回 字符串的Hash函数 例子：str = “IOI2005” hash ch 00 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”) = 1988023814 SDBMHash(“NOI2005”) = 626359947 SDBMHash(“IOI2004”) = 1988023813 很遗憾，又出现了扎堆 解决方法：在字符串后面附加一个长度信息(借鉴MD5) 但是使用这种方法要牺牲一点点速度 字符串的Hash函数 重新比较： SDBMHash(“IOI2005”) = 2134682497 SDBMHash(“IOI2004”) = 2134616898 SDBMHash(“NOI2005”) = 781526076 只要M不太接近65599，这个效果基本可以差强人意了 排列的Hash函数 这里的讨论已经不仅仅局限在“hashing”，而是推广到“numerize”，也就