哈希表是什么课件.ppt

《哈希表是什么课件.ppt》由会员分享，可在线阅读，更多相关《哈希表是什么课件.ppt（27页珍藏版）》请在三一办公上搜索。

1、一、哈希表是什么？,二、哈希函数的构造方法,三、处理冲突的方法,四、哈希表的查找,9.3 哈 希 表,以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，,一、哈希表是什么？,查找的过程为给定值依次和关键字集合中各个关键字进行比较，,查找的效率取决于和给定值进行比较的关键字个数。,只有一个办法：预先知道所查关键字在表中的位置，,对于频繁使用的查找表，希望 ASL=0。,即要求：记录在表中位置和其关键字之间存在一种确定的关系。,若以下标为000 999 的顺序表表示之。,例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围

2、为 xx000 xx999(前两位为年份)。,则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key)为哈希函数。,Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei,例如：对于如下 9 个关键字,设 哈希函数 f(key)=(Ord(第一个字母)-Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,问题:若添加关键字 Zhou,怎

3、么办？,能否找到另一个哈希函数？,1)哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可；,从这个例子可见：,2)由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1 key2，而 f(key1)=f(key2)。,3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。,因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。,哈希表的定义：,根据设定的哈希函数 H(key)和所选中

4、的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”或“散列表”。这一映象过程称为“哈希造表”或“散列”。所得存储地址称为“哈希地址”或“散列地址”。,二、构造哈希函数的方法,对数字的关键字可有下列构造方法：,若是非数字关键字，则需先对其进行数字化处理。,1.直接定址法,3.平方取中法,5.除留余数法,4.折叠法,6.随机数法,2.数字分析法,哈希函数为关键字的线性函数 H(key)=key 或者 H(key)=a key+b,1.直接定址法,此法仅适合于：地址集合的大小=关键

5、字集合的大小,2.除留余数法,设定哈希函数为:H(key)=key MOD p 其中，pm(表长)并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子,给定一组关键字为：12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为：3,3,0,6,6,3,例如：,为什么要对 p 加限制？,可见，若 p 中含质因子 3，则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。,三、处理冲突的方法,“处

6、理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。,1.开放定址法,2.再哈希法,3.链地址法（不讲）,为产生冲突的地址 H(key)求得一个地址序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s,1.开放定址法,对增量 di 有三种取法：,1)线性探测再散列 di=c i 最简单的情况 c=12)平方探测再散列 di=12,-12,22,-22,3)随机探测再散列 di 是一组伪随机数列,注意：增量 di 应具有“完备性”,例如:关键字集合 19,01,23,14,55,68,11,82,36,设定哈希函数 H(k

7、ey)=key MOD 11(表长=11),19,01,23,14,55,68,19,01,23,14,68,若采用线性探测再散列处理冲突,若采用二次探测再散列处理冲突,11,82,36,55,11,82,36,1 1 2 1 3 6 2 5 1,1 1 2 1 2 1 4 1 3,两种方法的平均查找长度：,线性探测再散列：ASL(9)=1/9(14+22+3+5+6)=22/9二次探测再散列：ASL(9)=1/9(15+22+3+4)=16/9,1)选用的哈希函数；2)选用的处理冲突的方法；3)哈希表饱和的程度，装载因子=n/m 值的大小（n记录数，m表的长度）,决定哈希表查找的ASL的因素

8、：,哈希表查找的分析:,从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。,哈希表的平均查找长度,利用装填因子所计算的平均查找长度是近似值！线性探测再散列哈希表：二次探测再散列、随即探测再散列哈希表：,2.再哈希法,Hi=RHi(key)i=1,2,.k RHi是不同的哈希函数，当产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算时间。,课堂习题,设有一个按各元素的值排好序的线性表且长度大于2，对给定的值K，分别用顺序查找法和折半查找法查找一个与K相等的元素，比较次数分别是s和b；在查找不成功的情况下，正确的s和b的数量关系是（）。总有s=b

9、总有sb总有sb与K值大小有关,答案：B,对有18个元素的有序表A作二分（折半）查找，则查找A3的比较序列的下标为（）1,2,39,5,2,39,5,39,4,2,3,答案：D,设散列表长m=14，散列函数为h(k)=k%11,表中已有4个记录，如果用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是（）。8359,15,38,61,84,答案：D,在采用线性探测法处理冲突时，假定装填因子值为0.5，则查找任一元素的平均查找长度为（）。11.522.5,答案：B,设散列函数为H(k)=k%7,一组关键字为23，14，9，6，30，12和18。散列表的地址空间为06，分别用线性探测法和二次探测法解决冲突，依次将这组关键字插入表中，则得到的散列表为（），平均查找长度分别为（）。,