1.除余法 M为什么不用偶数 若把M设置为偶数 x是偶数,h(Xx)也是偶数 h(x= x mod M x是奇数,h(Xx)也是奇数 ■通常选择一个质数作为M值 函数值依赖于自变量x的所有位,而不仅仅 是最右边k个低位 缺点:分布不均匀 增大了均匀分布的可能性 卖哭级釜嵌态考现的概率 例如,4093 反之亦然 叔新有,盘 张 M不用幂 mdy选择最右边8位 除余法面临的问题 0110010111000011010 若把M设置为2的幂 除余法的潜在缺点 那么,h(x)=xmod2k仅仅是x(用二进制 连续的关键码映射成连续的散列值 表示)最右边的k个位(bt 若把M设置为10的幂 ■虽然能保证连续的关键码不发生冲突 那么,h(x)=xmod10仅仅是x(用十进 但也意味着要占据连续的数组单元 制表示)最右边的k个十进制位( digita) 可能导致散列性能的降低 ■缺点:散列值不依赖于x的全部比特位 订恤 张铭趣 张帖 2.乘余取整法 乘余取整法示例 统让美最积的要放都分 上一个常数A(0<A< 设关键码key=123456,n=10000 然后,哥用警数n乘以这个值,对结果 且取A=(√5-1)/2=06180339, 因此有 ■散列函数为 ah(123456)= hash(key)=Ln*(A* key%1)J =L10000(0.6180339*123456 “A*key%1”表示取A*key小数部分: A*key %1=A*key-LA*key J =L1000(76300.004151 为助 =L10000*0.04151.J=41 学恤息 权新有,种9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 1. 除余法 „ 除余法：用关键码x除以M(往往取散列表长 度)，并取余数作为散列地址。散列函数为： h(x) ＝ x mod M „ 通常选择一个质数作为M值 „ 函数值依赖于自变量x的所有位，而不仅仅 是最右边k个低位 „ 增大了均匀分布的可能性 „ 例如，4093 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 M为什么不用偶数 „ 若把M设置为偶数 „ x是偶数，h(x)也是偶数 „ x是奇数，h(x)也是奇数 „ 缺点：分布不均匀 „ 如果偶数关键码比奇数关键码出现的概率 大，那么函数值就不能均匀分布 „ 反之亦然 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 M不用幂 „ 若把M设置为2的幂 „ 那么，h(x)＝x mod 2k 仅仅是x(用二进制 表示)最右边的k个位(bit) „ 若把M设置为10的幂 „ 那么，h(x)＝x mod 10k 仅仅是x(用十进 制表示)最右边的k个十进制位(digital) „ 缺点：散列值不依赖于x的全部比特位 0110010111000011010 x mod 28 选择最右边8位 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 除余法面临的问题 „ 除余法的潜在缺点 „ 连续的关键码映射成连续的散列值 „ 虽然能保证连续的关键码不发生冲突 „ 但也意味着要占据连续的数组单元 „ 可能导致散列性能的降低 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 2. 乘余取整法 „ 先让关键码 key 乘上一个常数A (0<A < 1)，提取乘积的小数部分 „ 然后，再用整数 n 乘以这个值，对结果 向下取整，把它作为散列地址 „ 散列函数为： hash ( key ) = ⎣ n * ( A * key % 1 ) ⎦ „ “A * key % 1”表示取 A * key 小数部分: A * key % 1 = A * key - ⎣ A * key ⎦ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 乘余取整法示例 „ 设关键码 key = 123456, n = 10000 且取 A = = 0.6180339， „ 因此有 hash(123456) = = ⎣10000*(0.6180339*123456 % 1)⎦ = = ⎣10000 * (76300.0041151… % 1)⎦ = = ⎣10000 * 0.0041151…⎦ = 41 ( 5 1) / 2 −