数字分析法(续4) 5.基数转换法 n数字分析法仅适用于事先明确知道 把关键码看成是另一进制上的数后 表中所有关键码每一位数值的分布 再把它转换成原来进制上的数 情况 取其中若干位作为散列地址 ■它完全依赖于关键码集合 ■如果换一个关键码集合,选择哪几 位数据要重新决定 般取大于原来基数的数作为转换 的基数,并且两个基数要互素 叔新有,盘 张 例:基数转换法 6.折叠法 ■例如,给定一个十进制数的关键码是 关键码所含的位数很多,采用平方取中 (2104865)10,把它看成以13为基数的十三 计算太复杂 进制数(210485)13,再把它转换为十进制 (210485)13=2x135+1X134+4x132+8×13+5 ■折叠法 =(771932)10 数相同的几部分(最后 ■假设散列表长度是10000则可取低生位 然后取这几部分的叠加和(舍去进位)作 1932作为散列地址 为散列地址 订恤 张铝 张帖 两种折叠方法 例:折叠法 n两种叠加方法 [例96]如果一本书的编号为0442-205864 移位叠加一把各部分的最后 5864 位对齐相加 4220 0224 分界叠加一各部分不折断,沿 各部分的分界来回折叠,然后对 : 11oo88 齐相加,将相加的结果当做散列 地址 h(key)=0088 hkey)=6092 (a)移位叠加 (b)分界叠加 权新有,种11 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 61 数字分析法（续4） „ 数字分析法仅适用于事先明确知道 表中所有关键码每一位数值的分布 情况 „ 它完全依赖于关键码集合 „ 如果换一个关键码集合，选择哪几 位数据要重新决定 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 62 5. 基数转换法 „ 把关键码看成是另一进制上的数后 „ 再把它转换成原来进制上的数 „ 取其中若干位作为散列地址 „ 一般取大于原来基数的数作为转换 的基数，并且两个基数要互素 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 63 例：基数转换法 „ 例如，给定一个十进制数的关键码是 (210485)10，把它看成以13为基数的十三 进制数(210485)13 ，再把它转换为十进制 (210485)13 = 2×135 + 1×134 + 4×132 + 8×13 + 5 = (771932)10 „ 假设散列表长度是10000，则可取低4位 1932作为散列地址 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 64 6. 折叠法 „ 关键码所含的位数很多，采用平方取中 法计算太复杂 „ 折叠法 „ 将关键码分割成位数相同的几部分（最后 一部分的位数可以不同） „ 然后取这几部分的叠加和（舍去进位）作 为散列地址 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 65 两种折叠方法 „ 两种叠加方法： „ 移位叠加 — 把各部分的最后一 位对齐相加 „ 分界叠加 — 各部分不折断，沿 各部分的分界来回折叠，然后对 齐相加，将相加的结果当做散列 地址 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 66 例：折叠法 „ [例9.6] 如果一本书的编号为04-42-20586-4 „ 5 8 6 4 5 8 6 4 „ 4 2 2 0 0 2 2 4 „ + 0 4 + 0 4 „ [1] 0 0 8 8 6 0 9 2 „ h(key)=0088 h(key)=6092 „ (a)移位叠加 (b)分界叠加