第七章 哈希表PPT讲稿.ppt

第七章第七章 哈希表哈希表第1页，共41页，编辑于2022年，星期一哈希表哈希表哈希表 第七章第七章第2页，共41页，编辑于2022年，星期一预习检查预习检查v哈希表的定义v处理冲突的方法有那些第3页，共41页，编辑于2022年，星期一本章目标本章目标v了解什么是哈希表了解什么是哈希表v掌握如何构造哈希函数掌握如何构造哈希函数v处理冲突的方式处理冲突的方式v哈希表的查找及分析哈希表的查找及分析第4页，共41页，编辑于2022年，星期一本章结构本章结构处理冲突的方法哈希表哈希表哈希函数的构造方法什么是哈希表第5页，共41页，编辑于2022年，星期一7-17-1 哈希表哈希表哈希表哈希表 哈希表又称哈希表又称哈希表又称哈希表又称散列表散列表散列表散列表。哈哈哈哈希希希希表表表表存存存存储储储储的的的的基基基基本本本本思思思思想想想想是是是是：以以以以数数数数据据据据表表表表中中中中的的的的每每每每个个个个记记记记录录录录的的的的关关关关键键键键字字字字 k k k k为为为为自自自自变变变变量量量量，通通通通过过过过一一一一种种种种函函函函数数数数H(k)H(k)H(k)H(k)计计计计算算算算出出出出函函函函数数数数值值值值。把把把把这这这这个个个个值值值值解解解解释释释释为为为为一一一一块块块块连连连连续续续续存存存存储储储储空空空空间间间间（即即即即数数数数组组组组空空空空间间间间）的的的的单单单单元元元元地地地地址址址址（即即即即下下下下标标标标），将将将将该该该该记记记记录录录录存存存存储储储储到到到到这这这这个个个个单单单单元元元元中中中中。在在在在此此此此称称称称该该该该函函函函数数数数H H H H为为为为哈哈哈哈希希希希函函函函数数数数或或或或散散散散列列列列函函函函数数数数。按按按按这这这这种种种种方方方方法建立的表称为法建立的表称为法建立的表称为法建立的表称为哈希表哈希表哈希表哈希表或或或或散列表散列表散列表散列表。第6页，共41页，编辑于2022年，星期一 例例如如，要要将将关关键键字字值值序序列列（3 3，1515，2222，2424），存存储储到到编编号号为为0 0到到4 4的的表表长长为为5 5的哈希表中。的哈希表中。计计算算存存储储地地址址的的哈哈希希函函数数可可取取除除5 5的的取取余余数数算算法法H(k)=k H(k)=k%5 5。则则构构造造好好的的哈哈希希表如图所示。表如图所示。7-17-1 哈希表哈希表哈希表哈希表第7页，共41页，编辑于2022年，星期一7-17-1 哈希表哈希表哈希表哈希表 理理想想情情况况下下，哈哈希希函函数数在在关关键键字字和和地地址址之之间间建建立立了了一一个个一一一一对对应应关关系系，从从而而使使得得查查找找只只需需一一次次计计算算即即可可完完成成。由由于于关关键键字字值值的的某某种种随随机机性性，使使得得这这种种一一一一对对应应关关系系难难以以发发现现或或构构造造。因因而而可可能能会会出出现现不不同同的的关关键键字字对对应应一一个个存储地址。即存储地址。即k1k2k1k2，但，但H(k1)=H(k2H(k1)=H(k2)，这种现象称为这种现象称为冲突冲突。把这种具有不同关键字值而具有相同哈希地址的对象称把这种具有不同关键字值而具有相同哈希地址的对象称“同义词同义词”。在在大大多多数数情情况况下下，冲冲突突是是不不能能完完全全避避免免的的。这这是是因因为为所所有有可可能能的的关关键键字字的的集集合合可可能能比较大，而对应的地址数则可能比较少。比较大，而对应的地址数则可能比较少。对于哈希技术，主要研究两个问题：对于哈希技术，主要研究两个问题：（1 1）如何设计哈希函数以使冲突尽可能少地发生。如何设计哈希函数以使冲突尽可能少地发生。（2 2）发生冲突后如何解决。发生冲突后如何解决。第8页，共41页，编辑于2022年，星期一 构造好的构造好的哈希函数哈希函数的方法，应能使冲突尽可能地少，因而应具有较的方法，应能使冲突尽可能地少，因而应具有较好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。1直接定址法直接定址法 直直接接定定址址法法是是以以关关键键字字k k本本身身或或关关键键字字加加上上某某个个数数值值常常量量c c作作为为哈哈希地址的方法。该哈希函数希地址的方法。该哈希函数H(k)H(k)为：为：H(k)=k+c (c0)H(k)=k+c (c0)这这种种哈哈希希函函数数计计算算简简单单，并并且且不不可可能能有有冲冲突突发发生生。当当关关键键字字的的分分布布基基本本连连续续时时，可可使使用用直直接接定定址址法法的的哈哈希希函函数数。否否则则，若若关关键键字分布不连续将造成内存单元的大量浪费。字分布不连续将造成内存单元的大量浪费。7-1-1 哈希函数的构造方法哈希函数的构造方法第9页，共41页，编辑于2022年，星期一例例：统统计计某某地地区区从从19491949年年到到19951995年年每每年年出出生生的的人人数数，列列在在一一张张表表中中。年年份份为为关关键字，因共有键字，因共有4747年，所以表中位置范围是年，所以表中位置范围是1 14747。设置设置H(k)=k-1948H(k)=k-1948即可，其中即可，其中k k为年份数。为年份数。这样的哈希表示意如下：这样的哈希表示意如下：若要查若要查19701970年的出生人数，则根据（年的出生人数，则根据（1970-1948=221970-1948=22）计算，在表的第计算，在表的第2222个位置即可找到。个位置即可找到。7-1-1 哈希函数的构造方法哈希函数的构造方法第10页，共41页，编辑于2022年，星期一2除留余数法除留余数法 取关键字取关键字k k除以哈希表长度除以哈希表长度m m所得余数作为哈希函数地址的方法。即：所得余数作为哈希函数地址的方法。即：H(k)=kH(k)=km m 这这是是一一种种较较简简单单、也也是是较较常常见见的的构构造造方方法法。这这种种方方法法的的关关键键是是选选择择好好哈哈希希表表的的长长度度m m。使使得得数数据据集集合合中中的的每每一一个个关关键键字字通通过过该该函函数数转转化化后后映映射射到到哈哈希希表表的的任任意意地地址址上上的的概概率率相相等等。理理论论研研究究表表明明，在在m m取取值值为为素数素数（质数）时，冲突可能性相对较少。（质数）时，冲突可能性相对较少。7-1-1 哈希函数的构造方法哈希函数的构造方法第11页，共41页，编辑于2022年，星期一3平方取中法平方取中法 取取关关键键字字平平方方后后的的中中间间几几位位作作为为哈哈希希函函数数地地址址（若若超超出出范范围围时时，可再取模）。可再取模）。设设有有一一组组关关键键字字ABCABC，BCD,CDEBCD,CDE，DEFDEF，其其对对应应的的机机内内码码如如表表所所示示。假假定定地地址址空空间间的的大大小小为为10001000，编编号号为为0-9990-999。现现按按平平方方取取中中法法构构造造哈哈希希函函数数，则则可可取取关关键键字字机机内内码码平平方方后后的的中中间间三三位位作作为为存存储储位置。计算过程如下表所示：位置。计算过程如下表所示：7-1-1 哈希函数的构造方法哈希函数的构造方法第12页，共41页，编辑于2022年，星期一4折叠法折叠法 这种方法适合这种方法适合在关键字的位数较多，而地址区间较小的情况在关键字的位数较多，而地址区间较小的情况。将将关关键键字字分分隔隔成成位位数数相相同同的的几几部部分分。然然后后将将这这几几部部分分的的叠叠加加和和作为哈希地址（若超出范围，可再取模）。作为哈希地址（若超出范围，可再取模）。例例如如，假假设设关关键键字字为为某某人人身身份份证证号号码码430104681015355430104681015355，则则可可以以用用4 4位位为为一一组组进进行行叠叠加加。即即有有5355+8101+1046+430=149325355+8101+1046+430=14932，舍去高位。，舍去高位。则有则有H(430104681015355)=4932H(430104681015355)=4932为该身份证关键字的哈希函数地址。为该身份证关键字的哈希函数地址。7-1-1 哈希函数的构造方法哈希函数的构造方法第13页，共41页，编辑于2022年，星期一5数值分析法数值分析法 若事先知道所有可能的关键字的取值时，可通过对这若事先知道所有可能的关键字的取值时，可通过对这些关键字进行分析，发现其变化规律，构造出相应的哈希些关键字进行分析，发现其变化规律，构造出相应的哈希函数函数。例例：对对如如下下一一组组关关键键字字通通过过分分析析可可知知：每每个个关关键键字字从从左左到右的第到右的第l l，2 2，3 3位和第位和第6 6位取值较集中，不宜作哈希地址。位取值较集中，不宜作哈希地址。剩剩余余的的第第4 4，5 5，7 7和和8 8位位取取值值较较分分散散，可可根根据据实实际际需需要要取其中的若干位作为哈希地址。取其中的若干位作为哈希地址。7-1-1 哈希函数的构造方法哈希函数的构造方法第14页，共41页，编辑于2022年，星期一 若取最后两位作为哈希地址，则哈希地址的集合为若取最后两位作为哈希地址，则哈希地址的集合为下表所示：下表所示：7-1-1 哈希函数的构造方法哈希函数的构造方法第15页，共41页，编辑于2022年，星期一7-1-2 冲突的解决方法冲突的解决方法 假设哈希表的地址范围为假设哈希表的地址范围为0 0m-lm-l，当对给定的关键字当对给定的关键字k k，由哈由哈希函数希函数H(k)H(k)算出的哈希地址为算出的哈希地址为i i（0im-10im-1）的位置上已存的位置上已存有记录，这种情况就是有记录，这种情况就是冲突现象冲突现象。处处理理冲冲突突就就是是为为该该关关键键字字的的记记录录找找到到另另一一个个“空空”的的哈哈希希地地址址。即即通通过过一一个个新新的的哈哈希希函函数数得得到到一一个个新新的的哈哈希希地地址址。如如果果仍仍然然发发生生冲冲突突，则则再再求求下下一一个个，依依次次类类推推。直直至至新新的的哈哈希希地地址址不不再再发生冲突为止。发生冲突为止。常用的处理冲突的方法有常用的处理冲突的方法有开放地址法开放地址法、链地址法链地址法两大类两大类 第16页，共41页，编辑于2022年，星期一1 1开放定址法开放定址法 用用开开放放定定址址法法处处理理冲冲突突就就是是当当冲冲突突发发生生时时，形形成成一一个个地地址址序序列列。沿沿着着这这个个序序列列逐逐个个探探测测，直直到到找找出出一一个个“空空”的的开开放放地地址址。将发生冲突的关键字值存放到该地址中去。将发生冲突的关键字值存放到该地址中去。如如 H Hi i=(H(k)+d=(H(k)+d（i i）)%m,i=1)%m,i=1，2 2，k k (km-1)(km-1)其其中中H(k)H(k)为为哈哈希希函函数数，m m为为哈哈希希表表长长，d d为为增增量量函函数数，d(i)=dd(i)=dl l，d d2 2d dn-ln-l。增增量量序序列列的的取取法法不不同同，可可得得到到不不同同的的开开放放地地址址处处理理冲冲突突探探测测方方法。法。7-1-2 冲突的解决方法冲突的解决方法第17页，共41页，编辑于2022年，星期一（1 1）线性探测法）线性探测法 线线性性探探测测法法是是从从发发生生冲冲突突的的地地址址（设设为为d d）开开始始，依依次次探探查查d+ld+l，d+2d+2，m-1m-1（当当达达到到表表尾尾m-1m-1时时，又又从从0 0开开始始探探查查）等等地地址址，直直到到找找到一个空闲位置来存放冲突处的关键字。到一个空闲位置来存放冲突处的关键字。若整个地址都找遍仍无空地址，则产生溢出。若整个地址都找遍仍无空地址，则产生溢出。线性探查法的数学递推描述公式为：线性探查法的数学递推描述公式为：d d0 0=H(k)=H(k)d di i=(d=(di-1i-1+1)%m+1)%m (1im-1)(1im-1)7-1-2 冲突的解决方法冲突的解决方法第18页，共41页，编辑于2022年，星期一7-1-2 冲突的解决方法冲突的解决方法【例例】已已知知哈哈希希表表地地址址区区间间为为0 01010，给给定定关关键键字字序序列列（2020，3030，7070，1515，8 8，1212，1818，6363，1919）。哈哈希希函函数数为为H(k)=kH(k)=kllll，采采用用线线性性探探测测法法处处理理冲冲突突，则则将将以以上上关关键键字字依依次存储到哈希表中。试构造出该哈希表，并求出等概率情况下的平均查找长度。次存储到哈希表中。试构造出该哈希表，并求出等概率情况下的平均查找长度。假设数组为假设数组为A,A,本题中各元素的存放过程如下：本题中各元素的存放过程如下：H(20)=9 H(20)=9，可直接存放到，可直接存放到A9A9中去。中去。H(30)=8 H(30)=8，可直接存放到，可直接存放到A8A8中去。中去。H(70)=4 H(70)=4，可直接存放到，可直接存放到A4A4中去。中去。H(15)=4 H(15)=4，冲突；，冲突；d0=4d0=4 d1=(4+1)%11=5 d1=(4+1)%11=5，将，将1515放入到放入到A5A5中。中。H(8)=8 H(8)=8，冲突；，冲突；d0=8 d0=8 d1=(8+1)%11=9 d1=(8+1)%11=9，仍冲突；，仍冲突；d2=(8+2)%11=10 d2=(8+2)%11=10，将，将8 8放入到放入到A10A10中中。第19页，共41页，编辑于2022年，星期一7-1-2 冲突的解决方法冲突的解决方法H(12)=lH(12)=l，可直接存放到，可直接存放到A1A1中去。中去。H(18)=7H(18)=7，可直接存放到，可直接存放到A7A7中去。中去。H(63)=8H(63)=8，冲突；，冲突；d0=8d0=8 d1=(8+1)%11=9 d1=(8+1)%11=9，仍冲突，仍冲突;d2=(8+2)%11=10 d2=(8+2)%11=10，仍冲突，仍冲突;d3=(8+3)%11=0 d3=(8+3)%11=0，将，将6363放入到放入到A0A0中。中。H(19)=8H(19)=8，冲突；，冲突；d0=8 d0=8 d1=(8+1)%11=9 d1=(8+1)%11=9，仍冲突，仍冲突;d2=(8+2)%11=10 d2=(8+2)%11=10，仍冲突，仍冲突;d3=(8+3)%11=0 d3=(8+3)%11=0，仍冲突，仍冲突;d4=(8+4)%11=1 d4=(8+4)%11=1，仍冲突，仍冲突;d5=(8+5)%11=2 d5=(8+5)%11=2，将，将1919放入到放入到A2A2中。中。第20页，共41页，编辑于2022年，星期一由此得哈希表如图所示由此得哈希表如图所示 在等概率情况下成功的平均查找长度为：在等概率情况下成功的平均查找长度为：（1*5+2+3+4+61*5+2+3+4+6）/9=20/9/9=20/9 利用线性探查法处理冲突容易造成关键字的利用线性探查法处理冲突容易造成关键字的“堆积堆积”问题。这是因为当连续问题。这是因为当连续n n个单元被占用后，再散列到这些单元上的关键字和直接散列到后面一个空闲单个单元被占用后，再散列到这些单元上的关键字和直接散列到后面一个空闲单元上的关键字都要占用这个空闲单元，致使该空闲单元很容易被占用，从而发元上的关键字都要占用这个空闲单元，致使该空闲单元很容易被占用，从而发生非同义冲突。造成平均查找长度的增加。生非同义冲突。造成平均查找长度的增加。为了克服堆积现象的发生，可以用下面的方法替代线性探查法。为了克服堆积现象的发生，可以用下面的方法替代线性探查法。7-1-2 冲突的解决方法冲突的解决方法第21页，共41页，编辑于2022年，星期一（2 2）平方探查法）平方探查法 设设发发生生冲冲突突的的地地址址为为d d，则则平平方方探探查查法法的的探探查查序序列列为为：d+1d+12 2，d+2d+22 2，直到找到一个空闲位置为止。直到找到一个空闲位置为止。平方探查法的数学描述公式为：平方探查法的数学描述公式为：d d0 0=H(k)=H(k)d di i=(d=(d0 0+i+i2 2)%m)%m (1im-1)(1im-1)7-1-2 冲突的解决方法冲突的解决方法第22页，共41页，编辑于2022年，星期一7-1-2 冲突的解决方法冲突的解决方法 【例】已知哈希表地址区间为【例】已知哈希表地址区间为0 01010，给定关键字序列（，给定关键字序列（2020，3030，7070，1515，8 8，1212，1818，6363，1919）。哈希函数为）。哈希函数为H(k)=kH(k)=kllll，采用平方探查法处理冲突。采用平方探查法处理冲突。【解】【解】H(20)=9 H(20)=9，可直接存放到可直接存放到A9A9中去。中去。H(30)=8H(30)=8，可直接存放到可直接存放到A8A8中去。中去。H(70)=4H(70)=4，可直接存放到可直接存放到A4A4中去。中去。H(15)=4H(15)=4，冲突；冲突；d d0 0=4=4 d1=(4+12)%11=5d1=(4+12)%11=5，放到放到A5A5中。中。第23页，共41页，编辑于2022年，星期一H(8)=8H(8)=8，冲突；冲突；d d0 0=8=8 d1=(8+12)%11=9d1=(8+12)%11=9，仍冲突仍冲突 d2=(8+22)%11=1d2=(8+22)%11=1 放到放到A1A1中。中。H(12)=lH(12)=l，冲突；冲突；d0=1d0=1 d1=(1+12)%11=2d1=(1+12)%11=2，放到放到A2A2中。中。H(18)=7H(18)=7，可直接存放到可直接存放到A7A7中去。中去。7-1-2 冲突的解决方法冲突的解决方法第24页，共41页，编辑于2022年，星期一H(63)=8H(63)=8，冲突；冲突；d d0 0=8=8 d1=(8+12)%11=9d1=(8+12)%11=9，仍冲突仍冲突 d2=(8+22)%11=1d2=(8+22)%11=1，仍冲突仍冲突 d3=(8+32)%11=6d3=(8+32)%11=6，放到放到A6A6中。中。H(19)=8H(19)=8，冲突；冲突；d0=8d0=8 d1=(8+12)%11=9d1=(8+12)%11=9，仍冲突仍冲突 d2=(8+22)%11=1d2=(8+22)%11=1，仍冲突仍冲突 d3=(8+32)%11=6d3=(8+32)%11=6，仍冲突仍冲突 d4=(8+42)%11=2d4=(8+42)%11=2，仍冲突仍冲突 d5=(8+52)%11=0d5=(8+52)%11=0，放到放到A0A0中中 7-1-2 冲突的解决方法冲突的解决方法第25页，共41页，编辑于2022年，星期一建立的哈希表如图所示建立的哈希表如图所示：在等概率情况下成功的平均查找长度为：在等概率情况下成功的平均查找长度为：（1*4+2*2+3+4+61*4+2*2+3+4+6）/9=21/9/9=21/9 平方探查法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺平方探查法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。例如，若表长例如，若表长m=13，假设在第假设在第3个位置发生冲突，则后面探查的位置依个位置发生冲突，则后面探查的位置依次为次为4、7、12、6、2、0，即可以探查到一半单元。，即可以探查到一半单元。若解决冲突时，探查到一半单元仍找不到一个空闲单元。则表明此哈若解决冲突时，探查到一半单元仍找不到一个空闲单元。则表明此哈希表太满，需重新建立哈希表。希表太满，需重新建立哈希表。7-1-2 冲突的解决方法冲突的解决方法第26页，共41页，编辑于2022年，星期一2 2链地址法链地址法 用链地址法解决冲突的方法是：把所有关键字为同义词的记用链地址法解决冲突的方法是：把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中（下标从链表的表头指针放在数组中（下标从0到到m-1）。）。这类似于图中这类似于图中的邻接表和树中孩子链表的结构。的邻接表和树中孩子链表的结构。7-1-2 冲突的解决方法冲突的解决方法第27页，共41页，编辑于2022年，星期一链地址法查找分析 由由于于在在各各链链表表中中的的第第一一个个元元素素的的查查找找长长度度为为l l，第第二二个个元元素素的的查查找找长长度度为为2 2，依此类推。因此，在等概率情况下成功的平均查找长度为：，依此类推。因此，在等概率情况下成功的平均查找长度为：(1*5+2*2+3*(1*5+2*2+3*l+4*1)l+4*1)9=169=169 9 虽然链地址法要多费一些存储空间，但是彻底解决了虽然链地址法要多费一些存储空间，但是彻底解决了“堆积堆积”问问题，大大提高了查找效率。题，大大提高了查找效率。7-1-2 冲突的解决方法冲突的解决方法第28页，共41页，编辑于2022年，星期一 哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址分布时，不需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免分布时，不需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免冲突，因此查找时还需要进行探测比较。冲突，因此查找时还需要进行探测比较。在在哈哈希希表表中中，虽虽然然冲冲突突很很难难避避免免，但但发发生生冲冲突突的的可可能能性性却却有有大大有有小小。这这主主要要与与三三个因素有关。个因素有关。第一第一:与装填因子有关与装填因子有关 所谓装填因子是指哈希表中己存入的元素个数所谓装填因子是指哈希表中己存入的元素个数n n与哈希表的大小与哈希表的大小m m的比值，即的比值，即 =n/mn/m。当当 越越小小时时，发发生生冲冲突突的的可可能能性性越越小小，越越大大（最最大大为为1 1）时时，发发生生冲冲突突的的可可能能性性就就越越大。大。7-1-3 哈希表的查找及性能分析哈希表的查找及性能分析第29页，共41页，编辑于2022年，星期一第二第二:与所构造的哈希函数有关与所构造的哈希函数有关 若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生。否则，若哈希函数选择哈希地址空间上，从而减少冲突的发生。否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。第三第三:与解决冲突的哈希冲突函数有关与解决冲突的哈希冲突函数有关 哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。7-1-3 哈希表的查找及性能分析哈希表的查找及性能分析第30页，共41页，编辑于2022年，星期一有关哈希表的算法有关哈希表的算法 1 1基于开放地址法的哈希表的建立基于开放地址法的哈希表的建立#define NIL-1#define M 997 /表长度表长度typedef int KeyType;typedef struct node /哈希表结点类型哈希表结点类型KeyType key;/其他数据域其他数据域HashType;用除余法求用除余法求K K的哈希地址的函数的哈希地址的函数h h int h(KeyType K)return K%M;第31页，共41页，编辑于2022年，星期一IncrementIncrement是求增量序列的函数是求增量序列的函数,它依赖于解决冲突的方法它依赖于解决冲突的方法int Increment(int i)/用线性探查法求第用线性探查法求第i个增量个增量di return i;求在哈希表求在哈希表T0.M-1T0.M-1中第中第i i次探查的哈希地址次探查的哈希地址hihi，0iM-10iM-1int Hash(KeyType k,int i)return(h(k)+Increment(i)%M;在哈希表在哈希表T0.M-1T0.M-1中查找中查找K,K,成功时返回成功时返回1 1。失败有两种情况：找到一个开放址时返回。失败有两种情况：找到一个开放址时返回0;0;表满未找到时返回表满未找到时返回-1-1int HashSearch(HashType T,KeyType K,int*pos)int i=0;/记录探查次数记录探查次数 do*pos=Hash(K,i);/求探查地址求探查地址hi if(T*pos.key=K)return 1;if(T*pos.key=NIL)return 0;/查找到空结点返回查找到空结点返回 while(+i0)printf(重复的关键字重复的关键字!);else printf(“表满错误表满错误,终止程序执行终止程序执行!”);exit(0);第33页，共41页，编辑于2022年，星期一根据根据A0.n-1A0.n-1中结点建立哈希表中结点建立哈希表T0.M-1T0.M-1void CreateHashTable(HashType T,HashType A,int n)if(nM)/用开放定址法处理冲突时，装填因子用开放定址法处理冲突时，装填因子须不大于须不大于1 printf(装填因子装填因子须不大于须不大于1);exit(0);for(i=0;iM;i+)Ti.key=NIL;/将各关键字清空，使地址将各关键字清空，使地址i i为开放地址为开放地址for(i=0;ikey!=K)/while(cur!=NULL&cur-key!=K)/查找查找pre=cur;cur=cur-next;pre=cur;cur=cur-next;*end=pre;*end=pre;if(cur=NULL)return NULL;/if(cur=NULL)return NULL;/查找不到时，返回空值查找不到时，返回空值 else return cur;/else return cur;/查找到时，返回该记录地址查找到时，返回该记录地址 第36页，共41页，编辑于2022年，星期一在链地址的哈希表在链地址的哈希表T T中若找不到关键字为中若找不到关键字为K K的记录，则插入该记录的记录，则插入该记录int HashInsert(ChainType*T,KeyType K)ChainType*pre,*cur;i=h(K);cur=HashSearch(Ti,K,&pre);if(cur=NULL)/未找到时，在链表尾插入该记录未找到时，在链表尾插入该记录 cur=(ChainType*)malloc(sizeof(ChainType);cur=(ChainType*)malloc(sizeof(ChainType);cur-key=K;cur-next=NULL;if(pre=NULL)/在该链插入第一条记录在该链插入第一条记录 Ti=cur;else /在该链插入后续记录在该链插入后续记录 pre-next=cur;return l;return 0;第37页，共41页，编辑于2022年，星期一根据根据A0.n-1A0.n-1中结点建立哈希表中结点建立哈希表T0.m-1T0.m-1void CreateHashTable(ChainType*T,ChainType A,int n)void CreateHashTable(ChainType*T,ChainType A,int n)int i;for(i=0;in;i+)HashInsert(T,Ai);第38页，共41页，编辑于2022年，星期一阶段总结阶段总结哈希算法的基本思想是什么哈希算法的存储效率主要取决于什么哈希算法解决冲突的方式有哪些第39页，共41页，编辑于2022年，星期一本章总结本章总结讲解哈希函数的几种构造方式讲解哈希函数的几种构造方式如何处理哈希表的冲突如何处理哈希表的冲突了解哈希表的定义了解哈希表的定义处理冲突的方法哈希表哈希表哈希函数的构造方法什么是哈希表第40页，共41页，编辑于2022年，星期一实验实验1v实验内容实验内容题目：创建一个哈希表用于存放随机数。v实验目的实验目的 掌握哈希函数的构造方法掌握哈表表处理冲突的方法v实验分析实验分析创建一个哈希表随即生成1000个随机数字存入哈希表中第41页，共41页，编辑于2022年，星期一