数据结构精品课件-哈希函数的构造方法.pptVIP

第八章 查找 8.1 查找的基本概念 8.3 基于树的查找法 8.5 总结与提高 8.2 基于线性表的查找法 8.4 计算式查找---哈希法 8.4 计算式查找---哈希法 一、哈希表的定义 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希法性能分析 8.4.1 哈希表的定义 以上讨论的各种查找表的共同特点为： 记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程是“基于” 比较。查找的效率取决于和给定值进行比较的次数, 这类方法的平均查找长度为O(logn)---O(n)。 对频繁使用的查找表,希望 ASL---〉0。 能否做到？ 能！ 若以下标为000 ~ 999 的顺序表表示之。 如：为招收的 1000 名新生建立一张查找表, 其关键字为学号,其值的范围为xx000~xx999 (前两位为年份)。 则查找过程可以简单进行：取给定学号的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。 另例：1、各年龄人口信息统计表； 2、解放后各年国民经济信息统计表。 上述几例的特点为： 记录在表中的位置与其关键字之间存在一种确定的对应关系, 按此对应关系可根据关键字的值寻址，从而获得待查纪录。这种查找表称为哈希表，关键字与记录地址间的对应关系称为哈希函数f(key) 。 {Zi, Qi, Su, Li, Wu, Ci, He, Ye, Du} 又例：对于如下 9 个关键字 设 哈希函数 f(key) = ?(Ord(第一个字母) -Ord(A)+1)/2? Ci Zi Qi Su Li Wu He Ye Du 问题: 若需添加关键字 Zh , 怎么办？ 此类问题称为“冲突”，如何解决？ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 从上述例子可见： 哈希表的构造、使用中有两个问题有待研究： 1、如何根据关键字集合的特点，选择合适的哈希函数，使关键字均匀的散列到表中？ 2、当不同的关键字所得的哈希函数值相同时，即f(k1)=f(k2), 如何有效的处理这类“冲突”现象（碰撞），使建表、查找均能有效地进行？ 根据选定的函数 H(key) 和处理冲突的方法, 将一组关键字映象到一个有限的、连续的地址集 (区间) 上，并以每个关键字在地址集中的 “映象”作为相应记录在表中的存储位置，由此构造所得的查找表称为“哈希表” (散列表、杂凑表) , 所选择的函数H (key)称为哈希函数。 哈希表的定义： 返回 若是非数字关键字，则需先对其进行 数字化处理。 1. 直接定址法 3. 平方取中法 5. 除留余数法 4. 分段叠加法 6. 随机数法 2. 数字分析法 “好的”哈希函数应该是“均匀”的，对数字型关键字，一般有下列哈希函数的构造方法： 二、构造哈希函数的方法 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a ? key + b 其中a和b为常数(此哈希函数称为自身函数) 所得的地址集合的大小等于关键字集合的大小,这种哈希函数不会发生冲突。 1. 直接定址法 例1：有一个从1岁到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。 H(key)=key 例2：有一个解放后出生的人口调查表，关键字是年份，哈希函数取关键字加一常数： H(key)=key+(-1948) 此方法仅适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度。 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体,去掉数字重复出现频度很高的位, 提取数字均匀分布的若干位或它们的组合作为地址。 2. 数字分析法 例3：有80个记录，其关键字为8位十进制数。假设哈希表的表长为100，则可取两位关键字组成哈希地址。 假设这80个关键字中的一部分如下所示： 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 5 4 1 5 7 8 1 3 6 8 5 3 7 8 1 4