数据结构-高职计算机-97484-第七章查找幻灯片.ppt

以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系， 一、哈希表是什么？ 查找的过程是把给定值依次与关键字集合中各个关键字进行比较。 查找的效率取决于与给定值进行比较的关键字个数。 用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同。 只有一个办法：预先知道所查关键字在表中的位置， 对于频繁使用的查找表， 希望 ASL = 0。 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。 若以下标为0 ~ 999 的顺序表存储学生信息。 例如：为每年招收的 1000 名新生建立一张查找表（学生信息表），其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份) 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。 但是，对于动态查找表而言， 因此在一般情况下，需在关键字和记录在表中的存储位置之间建立一个函数关系f，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f 为哈希函数。 1) 表长不确定； 2) 在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。 1) 哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的 大小不超出存储允许范围即可; 2) 由于哈希函数通常是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1? key2，而 f(key1) = f(key2)。 3) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地发生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。 哈希表的定义: 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。 二、构造哈希函数的方法 对数字型关键字可有下列构造方法: 1. 直接定址法 3. 平方取中法 5. 除留余数法 4. 折叠法 2. 数字分析法 构造哈希函数的目标： 哈希地址尽可能均匀分布——均匀性好； 哈希地址计算尽量简单。 哈希函数为关键字的线性函数 H(key) = a ? key + b， 其中a,b为常数 1. 直接定址法 此法不会发生冲突，但是仅适合于： 地址集合的大小 等于 关键字集合的大小 例：1949年后出生的人口调查表，关键字是年份 年份 1949 1950 1951 … 人数 … … … … H(key) = key + (-1948) 5. 除留余数法 H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的质数 或是 不含 20 以下的质因子 当关键字key为整数时，用关键字除以一个整数p 所得余数作为哈希地址。 给定一组关键字为: 12, 39, 18, 24, 33,21， 若取 p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3 例如： 为什么要对 p 加限制？ 可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。 三、处理冲突的方法 “处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个哈希地址 1. 开放定址法 2. 链地址法 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤ s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, …, s m为哈希表表长 1. 开放定址法 对增量 di 有两种取法： 1) 线性探测再散列 di = 1，2，3，…, 2) 平方探测再散列 di = 1