乘余取整法参数取值的考虑 3.平方取中法 ■若地址空间为p位,就取n=2P 所求出的散列地址正好是计算出来的 A* key %1=A* key-LA* key J 值的小数点后最左p位(bi)值 00110 此方法的优点:对n的选择无关紧要 ■ Knuth认为:A可以取任何值,与待 排序的数据特征有关。一般情况下 6,进8位10可:同倍作为散列 取黄金分割 1)/2最理想 叔新有,盘 张 4.数字分析法 数字分析法(续1) 设有n个d位数,每一位可能有r种不同的 计算各位数字中符号分布的均匀度A2的公 这r种不同的符号在各位上出现的频率不一定 λ=∑(a24-n/r)2 可鲣在某些位上分布均匀些,每种符号出现的几率 其中,a冫表示第i个符号在第k位上出 现的次数, 在某些位上分布不均匀,只有某几种符号经常出现 题想翻警夯霰列 取其中各种符号分布 m/r表示各种符号在个数中均匀出现的 计算出的λ值越小,表明在该位(第k位) 各种符号分布得越均匀 订恤 张铭趣 张帖 数字分析法(续2) 991269 ②位,λ2=57.60 数字分析法(续3) ③位,λ;=1760 991630 ④位,λ,=5.60 ①位,仅9出现8次 9 805 位,λs=5.60 =(8-810)2x1+(08/10)2x9=57.6 ⑥位,λ6=5.60 ②位,仅9出现8次 992047 λ2=(8-8/10)2x1+(0-8/10)2x957.6 990001 ■③位,0和2各出现两次,1出现4次 ①②③④@⑥ λ3=(28/10)2x2+(48/10)2x1+(08/10)2 若散列表地址范国有3位数字,取各关健码的④⑤⑥位做为 ■位,0和4各出现两次,2、3、5、6各出现1次 癥可与合来推假拥加址含素进份用我方 ■⑥位,7和8各出现两次,0、1、5、9各出现1次 -8/10)2x2+〔1-8/10) 学恤息 权新有,种 张帖兽10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 乘余取整法参数取值的考虑 „ 若地址空间为p位，就取n=2p „ 所求出的散列地址正好是计算出来的 A * key % 1 = A * key - ⎣ A * key ⎦ 值的小数点后最左p位（bit）值 „ 此方法的优点:对 n 的选择无关紧要 „ Knuth认为：A可以取任何值，与待 排序的数据特征有关。一般情况下 取黄金分割 最理想 ( 5 −1) 2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 3. 平方取中法 „ 此时可采用平方取中法：先通过求关键码的平 方来扩大差别，再取其中的几位或其组合作为 散列地址 „ 例如， „ 一组二进制关键码：(00000100，00000110， 000001010，000001001，000000111) „ 平方结果为：(00010000，00100100，01100010， 01010001，00110001) „ 若表长为4个二进制位，则可取中间四位作为散列 地址：(0100，1001，1000，0100，1100) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 4. 数字分析法 „ 设有 n 个 d 位数，每一位可能有 r 种不同的 符号 „ 这 r 种不同的符号在各位上出现的频率不一定 相同 „ 可能在某些位上分布均匀些，每种符号出现的几率 均等 „ 在某些位上分布不均匀，只有某几种符号经常出现 „ 可根据散列表的大小，选取其中各种符号分布 均匀的若干位作为散列地址 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 数字分析法（续1） „ 计算各位数字中符号分布的均匀度 λk 的公 式： „ 其中， 表示第 i 个符号在第 k 位上出 现的次数， „ n/r 表示各种符号在 n 个数中均匀出现的 期望值。 „ 计算出的 λk 值越小，表明在该位 (第k 位) 各种符号分布得越均匀 ∑= = − r i k k i n r 1 2 λ (α / ) k αi 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 数字分析法（续2） 9 9 2 1 4 8 ①位， λ 1 = 57.60 9 9 1 2 6 9 ②位， λ 2 = 57.60 9 9 0 5 2 7 ③位， λ 3 = 17.60 9 9 1 6 3 0 ④位， λ 4 = 5.60 9 9 1 8 0 5 ⑤位， λ 5 = 5.60 9 9 1 5 5 8 ⑥位， λ 6 = 5.60 9 9 2 0 4 7 9 9 0 0 0 1 ①②③④⑤⑥ „ 若散列表地址范围有 3 位数字, 取各关键码的④⑤⑥位做为 记录的散列地址 „ 也可以把第①，②，③和第⑤位相加，舍去进位，变成一位 数，与第④，⑥位合起来作为散列地址。还可以用其它方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 数字分析法（续3） „ ①位，仅9出现8次， „ λ 1 =（8-8/10）2×1+（0-8/10） 2 ×9=57.6 „ ②位，仅9出现8次， „ λ 2 =（8-8/10）2×1+（0-8/10） 2 ×9=57.6 „ ③ 位，0和2各出现两次，1出现4次 „ λ 3 =（2-8/10）2×2+（4-8/10） 2 ×1+ （0-8/10） 2 ×7 =17.6 „ ④位，0和5各出现两次，1、2、6、8各出现1次 „ ⑤位，0和4各出现两次，2、3、5、6各出现1次 „ ⑥位，7和8各出现两次，0、1、5、9各出现1次 „ λ 4 = λ 5 = λ 6 = （2-8/10）2×2+（1-8/10） 2 ×4+ （0-8/10） 2 ×4 =5.6