数据结构与算法课件：DS10_查找23

12022/9/6第第2323讲讲 散列检索散列检索本讲主要内容本讲主要内容w10.3.0散列中的基本问题散列中的基本问题w10.3.1散列函数散列函数w10.3.2开散列方法开散列方法w10.3.3闭散列方法闭散列方法w10.3.4闭散列表的算法实现闭散列表的算法实现w10.3.5散列方法的效率分析散列方法的效率分析碰撞的处理碰撞的处理22022/9/610.3.0 散列中的基本问题w基于关键码比较的检索基于关键码比较的检索 n顺序检索，顺序检索，=,!=,!=n二分法、树型二分法、树型 ,=,=,w检索是直接面向用户的操作检索是直接面向用户的操作w当问题规模当问题规模n很大时，上述检索的时间效率可能很大时，上述检索的时间效率可能使得用户无法忍受使得用户无法忍受w最理想的情况最理想的情况n根据关键码值，直接找到记录的存储地址根据关键码值，直接找到记录的存储地址n不需要把待查关键码与候选记录集合的某些不需要把待查关键码与候选记录集合的某些记录进行逐个比较记录进行逐个比较32022/9/6由数组的直接寻址想到的w例如，读取指定下标的数组元素例如，读取指定下标的数组元素n根据数组的起始存储地址、以及根据数组的起始存储地址、以及数组下标值而直接计算出来的，数组下标值而直接计算出来的，所花费的时间是所花费的时间是O(1)n与数组元素个数的规模与数组元素个数的规模n无关无关w受此启发，计算机科学家发明了受此启发，计算机科学家发明了散列方法（散列方法（Hash,有人称有人称“哈希哈希”，还有称，还有称“杂凑杂凑”）散列是一散列是一种重要的种重要的存储方法存储方法n也是一种常见的也是一种常见的检索方法检索方法42022/9/6散列基本思想w一个确定的函数关系一个确定的函数关系hw以结点的以结点的关键码关键码K为自变量为自变量w函数值函数值h(K)作为结点的存储地址作为结点的存储地址w检索时也是根据这个函数计算其存储位置检索时也是根据这个函数计算其存储位置n通常散列表的存储空间是一个一维数组通常散列表的存储空间是一个一维数组n散列地址是数组的下标散列地址是数组的下标52022/9/6例子1已知线性表关键码集合为：已知线性表关键码集合为：S=and,array,begin,do,else,end,for,go,if,repeat,then,until,while,with可设散列表为：可设散列表为：charHT2268;散列函数散列函数H(key)的值，取为关键码的值，取为关键码key中的第一个字母中的第一个字母在字母表在字母表a,b,c,.,z中的序号，即：中的序号，即：H(key)=key0a62022/9/6例子1（续）72022/9/6例子2w修改散列函数：散列函数的值为修改散列函数：散列函数的值为key中首尾字母中首尾字母在字母表中序号的平均值，即：在字母表中序号的平均值，即：intH3(charkey)inti=0;while(i8)&(keyi!=0)i+;return(key0+key(i-1)2*a)/2)82022/9/6例子2（续）92022/9/6几个重要概念w负载因子负载因子=n/mn散列表的空间大小为散列表的空间大小为mn填入表中的结点数为填入表中的结点数为nw冲突冲突n某个散列函数对于不相等的关键码计算出了某个散列函数对于不相等的关键码计算出了相同的散列地址相同的散列地址n在实际应用中，不产生冲突的散列函数极少在实际应用中，不产生冲突的散列函数极少存在存在w同义词同义词n发生冲突的两个关键码发生冲突的两个关键码102022/9/62022/9/610“生日悖论”w1939年，年，H.Davenport提出提出“生日悖论生日悖论”断言：断言：w房间内有房间内有23人，其两人生日不同的概率为人，其两人生日不同的概率为:w0.4927w若增加若增加17人，则两人生日不同的概率降低人，则两人生日不同的概率降低:w10倍（降低为原先的倍（降低为原先的1/10）112022/9/62022/9/611“生日悖论”当n=23发生的概率大约是0.507。其他数字的概率见下表：122022/9/6w要选定要选定“好好”的散列函数的散列函数1.能将关键字均匀影射到哈希空间上能将关键字均匀影射到哈希空间上2.计算哈希函数简单高效计算哈希函数简单高效3.有好的解决冲突的方法有好的解决冲突的方法w要设定处理冲突的方法要设定处理冲突的方法132022/9/6构造散列函数的方法 w直接定址法直接定址法 w数值分析法数值分析法 w平方取中法平方取中法 w折叠法折叠法 w基数转换法基数转换法w除留余数法除留余数法 142022/9/6直接定址法直接定址法取关键字或关键字的某个取关键字或关键字的某个线性函数线性函数值为散列地址。值为散列地址。wH(key)key或或H(key)akey+bw其中，其中，a和和b为常数，为常数，调整调整 a a与与b b的值可以使哈希地址取值范围与存的值可以使哈希地址取值范围与存储空间范围一致。储空间范围一致。地址地址0151年份年份194919502000人数人数关键字是年份，散列函数取关键字的线性函数：关键字是年份，散列函数取关键字的线性函数：H(key)=key+(-1949)H(key)=key+(-1949)优点：以关键码优点：以关键码key的某个线性函数值为哈希地址，不会产的某个线性函数值为哈希地址，不会产生冲突生冲突.缺点：要占用连续地址空间，空间效率低缺点：要占用连续地址空间，空间效率低152022/9/6特征位抽取法（数值分析法）特征位抽取法（数值分析法）w构造：对关键字进行分析，取构造：对关键字进行分析，取关键字的若干位或其组合作哈希关键字的若干位或其组合作哈希地址地址w适于关键字位数比哈希地址位数大，且可能出现的关键字事先适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况知道的情况例例 有有8080个记录，关键字为个记录，关键字为8 8位十进制数，哈希地址为位十进制数，哈希地址为2 2位十进制数位十进制数8134653281372242813874228130136781322817813389678136853781419355.分析：分析：只取只取8只取只取1只取只取3、4只取只取2、7、5数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位与另两位的叠加作哈希地址与另两位的叠加作哈希地址假设表长为假设表长为l00，则可取两位十，则可取两位十进制数进制数(0099)组成散列地址，组成散列地址，取哪两位取哪两位?原则是使得到的散列原则是使得到的散列地址地址尽量避免产生冲突尽量避免产生冲突162022/9/6数字分析法（续1）w计算各位数字中符号分布的均匀度计算各位数字中符号分布的均匀度 k的公式的公式n其中，其中，表示第表示第i 个符号在第个符号在第k 位上出现的次数位上出现的次数nn/r 表示各种符号在表示各种符号在n 个数中均匀出现的期望值个数中均匀出现的期望值n计算出的计算出的 k值越小，表明在该位值越小，表明在该位(第第k 位位)各种符各种符号分布得越均匀号分布得越均匀172022/9/6数字分析法（续2）w位，仅位，仅9出现出现8次，次，n 1=(8-8/10)21+(0-8/10)29=57.6w位，仅位，仅9出现出现8次，次，n 2=(8-8/10)21+(0-8/10)29=57.6w位，位，0和和2各出现两次，各出现两次，1出现出现4次次n 3=(2-8/10)22+(4-8/10)21+(0-8/10)27=17.6w位，位，0和和5各出现两次，各出现两次，1、2、6、8各出现各出现1次次w位，位，0和和4各出现两次，各出现两次，2、3、5、6各出现各出现1次次w位，位，7和和8各出现两次，各出现两次，0、1、5、9各出现各出现1次次n 4=5=6=(2-8/10)22+(1-8/10)24+(0-8/10)24=5.6182022/9/6数字分析法（续3）w若散列表地址范围有若散列表地址范围有3位数字位数字,取各关键码的取各关键码的位做为记录的位做为记录的散列地址散列地址w也可以把第也可以把第，和第和第位相加，舍去进位，变成一位数，位相加，舍去进位，变成一位数，与第与第，位合起来作为散列地址。还可以用其它方法位合起来作为散列地址。还可以用其它方法 9 9 2 1 4 8 9 9 2 1 4 8 位，位，1 1=57.60=57.60 9 9 1 2 6 9 9 9 1 2 6 9位，位，2 2=57.60=57.60 9 9 0 5 2 7 9 9 0 5 2 7位，位，3 3=17.60 =17.60 9 9 1 6 3 0 9 9 1 6 3 0位，位，4 4=5.60 =5.60 9 9 1 8 0 5 9 9 1 8 0 5位，位，5 5=5.60=5.60 9 9 1 5 5 8 9 9 1 5 5 8位，位，6 6=5.60=5.60 9 9 2 0 4 7 9 9 2 0 4 7 9 9 0 0 0 1 9 9 0 0 0 1 符号分布的均匀度符号分布的均匀度192022/9/6数字分析法（续4）w数字分析法仅适用于事先明确知道表中数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况所有关键码每一位数值的分布情况n它完全依赖于关键码集合它完全依赖于关键码集合w如果换一个关键码集合，选择哪几位数如果换一个关键码集合，选择哪几位数据要重新决定据要重新决定202022/9/6平方取中法平方取中法 w特点：对特点：对关键码平方后关键码平方后，按哈希表大小，按哈希表大小(即长度为即长度为散列表表长散列表表长)，取中间的若干位作为哈希地址。取中间的若干位作为哈希地址。w理由：因为中间几位与数据的每一位都相关。理由：因为中间几位与数据的每一位都相关。例：例：25892589的平方值为的平方值为67029216702921，可以取中间的，可以取中间的029029为地址。为地址。212022/9/6折叠法折叠法 w折叠法是折叠法是将较长的关键字从左到右分割将较长的关键字从左到右分割成位数相同成位数相同的几段的几段(最后一段的位数可以少一些最后一段的位数可以少一些)，然后，然后把这几把这几段叠加并舍去进位段叠加并舍去进位，得到的结果作为散列地址。这，得到的结果作为散列地址。这种方法适用于关键字位数很多，而且每一位的数字种方法适用于关键字位数很多，而且每一位的数字分布大致均匀的情况。分布大致均匀的情况。种类：种类：1）移位叠加：将分割后的几部分低位对齐相加）移位叠加：将分割后的几部分低位对齐相加2）间界叠加：从一端沿分割界来回折送，然后对齐相加）间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况适于关键字位数很多，且每一位上数字分布大致均匀情况222022/9/6例例1.1.关键字为关键字为 ：04422058640442205864，哈希地址位数为，哈希地址位数为4 4586442200410088H(key)=0088移位叠加移位叠加58640224046092H(key)=6092间界叠加间界叠加例例2.关键字为关键字为：x=123x=1232032032412411121122020，哈希地址位数为哈希地址位数为3从左到右按从左到右按3 3个位数个位数段分割，共得到段分割，共得到5 5个段：个段：123123、203203、241241、112112、2020。采用采用移位叠加移位叠加得到：得到：A(x)A(x)123+203+241+112+20123+203+241+112+20699699若采用若采用间界叠加间界叠加，则从左到右来回折叠中，第二、四段反转为，则从左到右来回折叠中，第二、四段反转为302302和和211211得到：得到：B(x)B(x)123+123+302302+241+241+211211+20+20897 897 232022/9/6基