数据结构课件第9章查找幻灯片.ppt

2. 数字分析法（数字选择法） 构造：取关键字的若干位或其组合作哈希地址。 适于关键字位数比哈希地址位数大，且可能出现的关键字事 先知道的情况。 例：有 80 个记录，关键字为 8 位十进制数，哈希表长为 100。 则哈希地址可取 2 位十进制数。 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 … … ? ? ? ? ? ? ? ? 分析： ?只取 8 ?只取 1 ?只取 3、4 ?只取 2、7、5 ???? 数字分布近乎随机 所以：取 ???? 任意两位或两位 与另两位的叠加作哈希地址 构造：以关键字的平方值的中间几位作为哈希地址。 求“关键字的平方值”的目的是“扩大差别”，同时平方值的中 间各位又能受到整个关键字中各位的影响。 3. 平方取中法（较常用） 此方法适合于：关键字中的每一位都有某些数字重复出现频 度很高的现象。 4. 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分 的叠加和（舍去进位）做哈希地址。 移位叠加：将分割后的几部分低位对齐相加。 间界叠加：从一端沿分割界来回折叠，然后对齐相加。 适于关键字位数很多，且每一位上数字分布大致均匀情况。 例：关键字为：0442205864，哈希地址位数为 4。 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位叠加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 间界叠加 5. 除留余数法（最常用） 构造：取关键字被某个不大于哈希表表长 m 的数 p 除后所得 余数作哈希地址，即 H(key) = key MOD p， p ? m。 特点：简单，可与上述几种方法结合使用。 p 的选取很重要；p 选得不好，容易产生同义词。 p 应为不大于 m 的素数或不含 20 以下的质因子的合数。 给定一组关键字：12, 39, 18, 24, 33, 21，若取 p = 9, 则他们 对应的哈希函数值将为： 3, 3, 0, 6, 6, 3 例如： 为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均 映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。 6. 随机数法 构造：取关键字的随机函数值作哈希地址，即： H(key) = Random(key) 其中，Random 为伪随机函数。 适于关键字长度不等的情况。 实际造表时，采用何种构造哈希函数的方法取决于建表的关 键字集合的情况（包括关键字的范围和形态），总的原则是使产 生冲突的可能性降到尽可能地小。 选取哈希函数，考虑以下因素： 1）计算哈希函数所需时间 2）关键字长度 3）哈希表长度（哈希地址范围） 4）关键字分布情况 5）记录的查找频率 “处理冲突”的实际含义是：为产生冲突的地址寻找另一个 哈希地址。 9.3.3 处理冲突的方法 1. 开放定址法 当发生冲突时，在冲突位置的前后附近寻找可以存放记录 的空闲单元。用此法解决冲突，要产生一个探测序列，沿着此 序列去寻找可以存放记录的空闲单元。最简单的探测序列产生 方法是进行线性探测，即当发生冲突时，从发生冲突的存储位 置的下一个存储位置开始依次顺序探测空闲单元。 为产生冲突的地址 H(key) 求得一个探查地址序列：