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

1、2022/7/18第23讲 散列检索本讲主要内容10.3.0 散列中的基本问题10.3.1 散列函数10.3.2 开散列方法10.3.3 闭散列方法10.3.4 闭散列表的算法实现10.3.5 散列方法的效率分析碰撞的处理2022/7/1810.3.0 散列中的基本问题基于关键码比较的检索 顺序检索，=, !=二分法、树型 , = , 检索是直接面向用户的操作当问题规模n很大时，上述检索的时间效率可能使得用户无法忍受最理想的情况根据关键码值，直接找到记录的存储地址不需要把待查关键码与候选记录集合的某些记录进行逐个比较2022/7/18由数组的直接寻址想到的例如，读取指定下标的数组元素根据数组的

2、起始存储地址、以及数组下标值而直接计算出来的，所花费的时间是O(1)与数组元素个数的规模n无关受此启发，计算机科学家发明了散列方法（Hash, 有人称“哈希”，还有称“杂凑”）散列是一种重要的存储方法也是一种常见的检索方法2022/7/18散列基本思想一个确定的函数关系h以结点的关键码K为自变量函数值h(K)作为结点的存储地址检索时也是根据这个函数计算其存储位置通常散列表的存储空间是一个一维数组散列地址是数组的下标2022/7/18例子1已知线性表关键码集合为：S = and, array, begin, do, else, end, for, go, if, repeat, then, un

3、til, while, with可设散列表为：char HT2268;散列函数H(key)的值，取为关键码key中的第一个字母在字母表a, b, c, ., z中的序号，即：H(key)=key0 a2022/7/18例子1（续）2022/7/18例子2修改散列函数：散列函数的值为key中首尾字母在字母表中序号的平均值，即：int H3(char key) int i = 0; while (i8) & (keyi!=0) i+; return(key0 + key(i-1) 2*a) /2 )2022/7/18例子2（续）2022/7/18几个重要概念负载因子 =n/m散列表的空间大小为m填

4、入表中的结点数为n冲突某个散列函数对于不相等的关键码计算出了相同的散列地址在实际应用中，不产生冲突的散列函数极少存在同义词发生冲突的两个关键码2022/7/182022/7/1810“生日悖论”1939年，H.Davenport提出“生日悖论”断言：房间内有23人，其两人生日不同的概率为:0.4927若增加17人，则两人生日不同的概率降低:10倍（降低为原先的1/10）2022/7/182022/7/1811“生日悖论”当n=23发生的概率大约是0.507。 其他数字的概率见下表：2022/7/18要选定“好”的散列函数能将关键字均匀影射到哈希空间上计算哈希函数简单高效有好的解决冲突的方法要设

5、定处理冲突的方法 2022/7/18构造散列函数的方法 直接定址法 数值分析法 平方取中法 折叠法 基数转换法除留余数法 2022/7/18直接定址法取关键字或关键字的某个线性函数值为散列地址。H(key)key或H(key)akey+b 其中，a和b为常数，调整 a与b的值可以使哈希地址取值范围与存储空间范围一致。 地址 0 1 51年份 1949 1950 2000人数 关键字是年份，散列函数取关键字的线性函数： H(key)=key+(-1949) 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低2022/7/18特征位抽取法（数值分析法

6、） 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数 8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址假设表长为l00，则可取两位十进制数(0099)组

7、成散列地址，取哪两位?原则是使得到的散列地址尽量避免产生冲突2022/7/18数字分析法（续1）计算各位数字中符号分布的均匀度 k 的公式其中， 表示第 i 个符号在第 k 位上出现的次数n/r 表示各种符号在 n 个数中均匀出现的期望值计算出的 k 值越小，表明在该位 (第k 位)各种符号分布得越均匀2022/7/18数字分析法（续2）位，仅9出现8次， 1 =(8-8/10)21+(0-8/10)2 9=57.6位，仅9出现8次， 2 =(8-8/10)21+(0-8/10)2 9=57.6 位，0和2各出现两次，1出现4次 3 =(2-8/10)22+(4-8/10)2 1+ (0-8/

8、10)2 7 =17.6位，0和5各出现两次，1、2、6、8各出现1次位，0和4各出现两次，2、3、5、6各出现1次位，7和8各出现两次，0、1、5、9各出现1次 4 = 5 = 6 = (2-8/10)22+(1-8/10)2 4+(0-8/10)2 4 =5.62022/7/18数字分析法（续3）若散列表地址范围有 3 位数字, 取各关键码的位做为记录的散列地址也可以把第，和第位相加，舍去进位，变成一位数，与第，位合起来作为散列地址。还可以用其它方法 9 9 2 1 4 8 位， 1 = 57.60 9 9 1 2 6 9位， 2 = 57.60 9 9 0 5 2 7位， 3 = 17.

9、60 9 9 1 6 3 0位， 4 = 5.60 9 9 1 8 0 5位， 5 = 5.60 9 9 1 5 5 8位， 6 = 5.60 9 9 2 0 4 7 9 9 0 0 0 1 符号分布的均匀度2022/7/18数字分析法（续4）数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况它完全依赖于关键码集合如果换一个关键码集合，选择哪几位数据要重新决定2022/7/18平方取中法 特点：对关键码平方后，按哈希表大小(即长度为散列表表长) ，取中间的若干位作为哈希地址。理由：因为中间几位与数据的每一位都相关。 例：2589的平方值为6702921，可以取中间的029为地址。

10、2022/7/18折叠法 折叠法是将较长的关键字从左到右分割成位数相同的几段(最后一段的位数可以少一些)，然后把这几段叠加并舍去进位，得到的结果作为散列地址。这种方法适用于关键字位数很多，而且每一位的数字分布大致均匀的情况。 种类：1）移位叠加：将分割后的几部分低位对齐相加2）间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况2022/7/18例1.关键字为 ：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=609

11、2间界叠加例2.关键字为 ：x=12320324111220，哈希地址位数为3从左到右按3个位数段分割，共得到5个段：123、203、241、112、20。采用移位叠加得到： A(x)123+203+241+112+20699若采用间界叠加，则从左到右来回折叠中，第二、四段反转为302和211得到： B(x)123+302+241+211+20897 2022/7/18基数转换法把关键码看成是另一进制上的数后再把它转换成原来进制上的数取其中若干位作为散列地址一般取大于原来基数的数作为转换的基数，并且两个基数要互素2022/7/18例：基数转换法例如，给定一个十进制数的关键码是(210485)1

12、0，把它看成以13为基数的十三进制数(210485)13 ，再把它转换为十进制 (210485)13 = 2135 + 1134 + 4132 + 813 + 5 = (771932)10假设散列表长度是10000，则可取低4位1932作为散列地址2022/7/18除留余数法 除留余数法采用取模运算(%)，把关键字除以某个不大于散列表表长的整数得到的余数作为散列地址。散列函数形式为：H(key)=keyp pm注意：如果p选不好，就容易产生同义词。特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取pm的最大质数2022/7/18散列函数的应用在

13、实际应用中应根据关键码的特点，选用适当的散列函数有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”若关键码不是整数而是字符串时，可以把每个字符串转换成整数，再应用平方取中法2022/7/18有6个元素的关键码分别为：（14，23，39，9，25，11）选取关键码与元素位置间的函数为H(k)=k mod 7通过哈希函数对6个元素建立哈希表：253923914冲突现象举例：6个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有冲突！ 0 1 2 3 4 5 62022/7/18哈希冲突的解决方法 主要介绍：闭

14、散列法（开放地址法）当发生冲突时，在冲突位置的前后附近寻找可以存放记录的空闲单元。 开散列法（链地址法） 2022/7/18闭散列法 基本思想：所有元素存储在散列表数组中。元素经散列函数计算出来的地址称为基地址。若插入元素x，而x的基地址已被某个同义词占用，则根据某种策略将x存储在数组的另一个位置。探测：寻找“下一个”空位的过程称为探测探测地址：Hi( H(key)+di) m i=1,2,k (km-1) m为表长， di为增量线性探测再散列 (di=1,2,3,m-1)二次探测再散列 (di=12，-12，22，-22，k2 km/2) 双重散列法（随机数法） 2022/7/18线性探测法

15、基本思想：当发生冲突时，从冲突位置的下一个单元顺序寻找可存放记录的空单元，只要找到一个空位，就把元素放入此空位中。顺序查找时，我们把散列表看成一个循环表，即如果到最后一个位置也没有找到空单元，则回到表头开始继续查找。此时，如果仍然未找到空位，则说明散列表已满，需要进行溢出处理。 2022/7/18线性探测法示例关键字为(13,19,39,24,28,57,76,51,84)，散列表长m=13，散列函数为H(key)=key%11 0 1 2 3 4 5 6 7 8 9 10 11 121339191111324391912111324392819121212022/7/18线性探测法示例(续)

16、继续插入 57,76,51,841324573928191231210 1 2 3 4 5 6 7 8 9 10 11 121324573928197612312111324573928195176123121311324573928195176841231213152022/7/18线性探测法的ASLASLSUCC=1/9*(4*1+2*2+2*3+1*5)=19/9ASLUNSUCC =1/13*(1+1+4+3+2+1+7+6+5+4+3+2+1) =40/132022/7/18关于探查序列插入和检索函数都假定每个关键码的探查序列中至少有一个存储位置是空的否则可能会进入一个无限循环中也可

17、以限制探查序列长度2022/7/18线性探测法的优缺点优点：计算简单，只要有空位，就可将元素存入缺点：容易产生“二次聚集”：不同基地址的元素争夺同一个单元的现象叫作“二次聚集”。平均查找长度大。 2022/7/18二次探测法 加大探测序列的步长，使发生冲突的元素的位置比较分散 ,步长 di=12，-12，22，-22，k2（km/2） ,在地址i产生冲突，不是探测i+l地址，而是探测i+12，i-12，i+22，i-22的地址 2022/7/18双重散列法(随机数法） 以关键字的另一个散列函数值作为增量。设两个散列函数为：H1和H2，则得到的探测序列为：(d+H2(key)%m ，(d+2H2

18、(key)%m ，(d+3H2(key)%m ， 其中d=H1(key)由此可知，双重散列法探测下一个开放地址的公式为：di=(d+i*H2(key)%m (1im-1)使H2的值和m互素 2022/7/18链地址法 基本思想：开散列法的一种简单形式是把散列表的每个地址空间定义为一个单链表的表头指针，单链表中每个结点包括一个数据域和一个指针域，数据域存储查找表中的元素。散列地址相同的所有元素存储在以该散列地址为表头指针的单链表里 2022/7/18链地址法示例关键字为(13,19,39,24,28,57,76,51,84)，散列表长m=13，散列函数为H(key)=key%11 0123456

19、789101112245713281939845176ASLss=1/9*(5*1+3*2+1*3)=14/9ASLun=1/11*(6*1+2*2+2*3+1*4)=20/11对查找失败时的平均查找长度有两种观点 2022/7/18关于闭散列法和开放地址法闭散列法在有的教材上称为“开放地址法”。闭散列法中“闭”的含义是散列表的长度是确定的，定义后不能增加；开放地址法中“开放”，是指数组的每一个地址有可能被任何基地址的元素占用，即每个地址对所有元素都是开放的。 2022/7/18关于开散列法和链地址法开散列法在有的教材上称为“链地址法”。开散列法中“开”的含义是散列表的元素的个数不受限制（只受

20、内存大小限制），即具有相同哈希函数值的关键字都可链到同一链表中；由于用链表解决冲突，所以这种解决冲突的方法有时称链地址法。 2022/7/18散列表的查找散列表查找过程和散列表的生成相似：首先根据选定的哈希函数，计算出给定关键字的哈希地址：若该地址为空，则查找失败。若该地址不空，且所存关键字的值恰好等于所查关键字，则查找成功。若该地址不空，但所存关键字的值不等于所查关键字，则按着造表时使用的解决冲突的方法，继续查找，直到成功或失败。2022/7/18哈希查找过程及分析1. 哈希查找过程给定k值计算H(k)此地址为空关键字=k查找失败查找成功按处理冲突方法计算HiYNYN2022/7/18装填因

21、子装填因子越小，发生冲突的可能性越小，装填因子越大，发生的冲突的可能性越大2022/7/18散列表的查找及分析 散列表的平均查找长度是的函数，不是记录数n的函数。线性探测法查找成功时的平均查找长度为： 链地址法查找成功时的平均查找长度为： 对关键字集不大且频繁使用的关键字，也能找到“完美函数”2022/7/18散列表小结平均查找长度(ASL)最小。缺点有：占用存储空间大开放定址法删除元素只能作标记，不能物理的删除，浪费了空间只能按关键字随机查找，不能按非关键字查找仍有比较2022/7/182022/7/1847下面关于哈希(Hash，杂凑)查找的说法正确的是( )A哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B除留余数法是所有哈希函数中最好的 C不存在特别好与坏的哈希函数，要视情况而定D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 C自测题 2022/7/182022/7/1848 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行多少次探测？( ) A. k-1次 B. k次 C.