数据结构 第九章 动态查找

《数据结构 第九章 动态查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、哈希表是什么？二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找五、哈希表的删除操作六、哈希表也可用来构造静态查找表9.3哈希表以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，一、哈希表是什么？查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。只有一个办法：预先知道所查关键字在表中的位置，对于频繁使用的查找表，希望ASL=0

2、。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为000~999的顺序表表示之。例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。但是，对于动态查找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。1)表长不确定；2)在设计查找表时，只知道关键字所

3、属范围，而不知道确切的关键字。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dai}例如：对于如下9个关键字设哈希函数f(key)=(Ord(第一个字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDai问题:若添加关键字Zhou,怎么办？能否找到另一个哈希函数？1)哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；从这个例子可见：2)由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1ke

4、y2，而f(key1)=f(key2)。3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。哈希表的定义：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。二、构造哈希函数的方法对数字的关键字可有下列构造方法：若是非数字

5、关键字，则需先对其进行数字化处理。1.直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b1.直接定址法此法仅适合于：地址集合的大小==关键字集合的大小此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。2.数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差

6、别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。4.折叠法此方法适合于:关键字的数字位数特别多。5.除留余数法设定哈希函数为:H(key)=keyMODp其中，p≤m(表长)并且p应为不大于m的素数或是不含20以下的质因子给定一组关键字为：12,39,18,24,33,21，若取p=9,则他们对应的哈希函数值将为：3,3,0,6,6,3例如：为什么要对p加限制？可

7、见，若p中含质因子3，则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。6.随机数法设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数通常，此方法用于对长度不等的关键字构造哈希函数。实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。三、处理冲突的方法“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开放定址法2.链地址法为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,

8、…,Hs1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di)MODmi=1,2,…,s1.开放定址法对增量di有三种取法：