ch10-散列结构解答.ppt

第十章 散列结构;散列 散列函数 开地址散列向量 桶散列;散列 (Hashing);静态散列方法; ;冲突示例：有一组表项，其关键码分别是 12361, 07251, 03309, 30976 采用的散列函数是 hash(x) = x % 73 + 13420 则有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。就是说, 对不同的关键码, 通过散列函数的计算, 得到了同一散列地址。我们称这些产生冲突的散列地址相同的不同关键码为同义词。;由于关键码集合比地址集合大得多, 冲突很难避免。所以对于散列方法, 需要讨论以下两个问题： 对于给定的一个关键码集合, 选择一个计算简单且地址分布比较均匀的散列函数； 避免或尽量减少冲突；;构造散列函数时的几点要求： 散列函数应是简单的，能在较短的时间内 计算出结果。 散列函数的定义域必须包括需要存储的全 部关键码, 如果散列表允许有 m 个地址时, 其值域必须在 0 到 m-1 之间。 ; 直接映射法 此类函数取关键码的某个线性函数值作为散列地址： Hash ( key ) ＝ a * key + b { a, b为常数 } 这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求 ; 示例：有一组关键码如下：{ 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 }。散列函数为 Hash (key) = key - 940000 Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按计算出的地址存放记录。; ; 9 4 2 1 4 8 9 4 1 2 6 9 9 4 0 5 2 7 9 4 1 6 3 0 9 4 1 8 0 5 9 4 1 5 5 8 9 4 2 0 4 7 9 4 0 0 0 1 ① ② ③ ④ ⑤ ⑥ ;数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全 如果换一个关键码集合，选择哪几位要重新决定。;③除留余数法 设散列表中允许地址数为 m, 取一个不大于 m, 但最接近于或等于 m 的质数 p 作为除数, 利用以下函数把关键码转换成散列地址： hash ( key ) = key % p p ? m 其中, “%”是整数除法取余的运算，要求这时的质数 p 不是接近2的幂。;示例: 有一个关键码 key = 962148, 散列表大小 m = 25, 即 HT[25]。取质数 p= 23。 散列函数 hash ( key ) = key % p 散列地址为 hash ( 962148 ) = 962148 % 23 = 12 可以按计算出的地址存放记录。需要注意的是, 使用上面的散列函数计算出来的地址范围是 0到 22, 因此, 从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的, 只可能在处理冲突时达到这些地址。; 平方取中法 此方法在词典处理中使用十分广泛。 它先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为 散列地址。 设标识符可以用一个计算机字长的内码表示。 在平方取中法中, 一般取散列地址为2的某次幂。; ; 折叠法 此方法把关键码自左到右分成位数相等的几部分, 每一部分的位数应与散列表地址位数相同, 只有最后一部分的位数可以短一些。 把这些部分的数据叠加起来, 舍去进位，就可以得到具有该关键码的记录的散列地址。 有两种叠加方法： 移位法 — 把各部分的最后一位对