数据结构严蔚敏 查找表4.ppt

* * 一、哈希表是什么？ 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 9.3 哈 希 表 五. 可扩充散列 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系， 一、哈希表是什么？ 查找的过程为给定值依次和关键字集合中各个关键字进行比较， 查找的效率取决于和给定值进行比较的关键字个数。 准 考 证 号 姓名 各科成绩 总分 政治 语文 外语 数学 物理 化学 生物 . . . 179321 179322 179333 . . 145321 . . . 陈红 陆华 张平. . . 张平 . . . 84 76 85 . . . 76 . . . 76 84 88 . . 64. . . . 74 65 73. . . 75 . . . 93 87 79 . . . 88 . . . 87 69 62 . . . 66 . . . 76 57 63 . . . 67 . . . 87 71 78 . .. 81 . . . 63 54 55 . . 73 准 考 证 号 姓名 政治 语文 外语 数学 物理 化学 生物 总分 物理地址 8010 8230 8240 8250 8700 关键字 存放位置 用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同。 只有一个办法：预先知道所查关键字在表中的物理存储位置， 对于频繁使用的查找表， 希望 ASL = 0。 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。 哈希查找的基本思想： 以查找表中的每个元素的关键字key为自变量，通过一种函数H(key)计算出函数值，把这个值 解释为一块连线存储空间的地址单元，并将该元素存储到这个地址单元中。这种函数H(key)就称为哈希函数。 在哈希表上进行查找时，首先根据给定值的关键字key，用哈希函数H(key)计算出存储地址，然后按此地址取出对应的元素。 如果以学号的后三位000 ~ 999作为每个元素存储地址, 建立顺序查找表。 例1：为某校每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份)。 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。 此时的哈希函数 H(key) = key {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Deng} 例2：对于如下 9 个关键字 设 哈希函数 f(key) = ? Ord(关键字的第一个字母的序号) / 2 ? Chen Zhao Qian Sun Li Wu Han Ye Deng 问题: 若添加关键字 Zhou , 冲突，怎么办？ 能否找到另一个哈希函数？ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 条件是这个映射的地址集合的大小不超出某个允许的范围; 从前面两个例子可见， 2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1? key2，而 f(key1) = f(key2)。 3) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到 一种“处理冲突” 的方法。 哈希表的定义: 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、连续的地址空间 (区间)上，并以关键字在地址空间中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。 二、构造哈希函数的方法 对数字的关键字有下列构造方法: 1. 直接定址法 3. 平方取中法 5.