湘潭大学-数据结构-课件-ppt-Ch05-Hashing

1、 Preview一种用于以常数平均时间执行插入、删除和查找的技术不支持需要元素间任何排序信息的操作散 列 表第五章 散列1 一般想法一般想法已有已有几种查找方法：几种查找方法：h)(log2NO已经已经是相当不错的时间复杂度是相当不错的时间复杂度!顺序查找顺序查找二分查找（静态查找）二分查找（静态查找）二叉查找树二叉查找树)(NO)(log2NO)(hO为二叉查找树的高度到底还有没有其他到底还有没有其他适应性广适应性广而而速度又快速度又快的查找方法呢？的查找方法呢？1 一般想法一般想法例例1在登录在登录QQ的时候，的时候，QQ服务器如何服务器如何核对你核对你的身份的身份，以确定你就是该号码的主

2、人？，以确定你就是该号码的主人？【分析分析】看看是否可以用看看是否可以用二分法二分法查找。查找。 十亿十亿（109 230）有效用户，用二分查找有效用户，用二分查找30次次。 十亿十亿（109 230） 1K 1024G，1T连续空间。连续空间。 按有效按有效QQ号大小号大小有有序存储序存储：在连续存储空间中，在连续存储空间中，插插入和删除入和删除一个新一个新QQ号码将需要号码将需要移动大量数据移动大量数据。用不了二分查找，用不了二分查找，我们该怎么办？我们该怎么办？1 一般想法一般想法例例2查英文字典的过程查英文字典的过程查询英文单词查询英文单词“zoo”，你为什么不用二分法，而直接从字典的

3、后面找？你为什么不用二分法，而直接从字典的后面找？ 我们已经根据要查找的关键词我们已经根据要查找的关键词“zoo”在脑子里经过了在脑子里经过了“计计算算”，得出该关键词所在的，得出该关键词所在的大致位置大致位置，这样就能，这样就能更快地更快地找到它。找到它。这个这个“计算计算”过程非常类似于本章将要介绍的散列查找中的过程非常类似于本章将要介绍的散列查找中的“散列函数计算散列函数计算”。 查字典的过程结合了查字典的过程结合了散列查找散列查找（用于初步定位）、（用于初步定位）、二分查找二分查找（一般不是准确二分）和（一般不是准确二分）和顺序查找顺序查找（当很接近关键词的时候）等（当很接近关键词的时

4、候）等几种查找方法。几种查找方法。1 一般想法一般想法例例3网上搜索。网上搜索。搜索引擎搜索引擎是如何如此是如何如此神速地神速地把我们把我们需要的需要的有关信息有关信息找到的？找到的？【分析分析】主要数据结构是主要数据结构是“倒排索引倒排索引” - “单词到文档单词到文档”的映射关系。的映射关系。如何在这个巨大无比的表格如何在这个巨大无比的表格中查找特定的关键词中查找特定的关键词？ DocsTerms文档文档1文档文档2文档文档m1文档文档m关键词关键词13: 1,12,2002: 1, 223: 9,40,52关键词关键词202: 11,224: 9,20,32,655: 5,9,10,32

5、,35关键词关键词n1005: 3,9,10,32,56 10: 5,6,19,.,44关键词关键词n5: 1,9,20,22,55001: 7【问题问题】如何能够在极短的时间内（比如如何能够在极短的时间内（比如1秒内）搜索到需要的关键词？秒内）搜索到需要的关键词？ 1 一般想法一般想法 散列查找法的两项基本工作：散列查找法的两项基本工作：构造散列函数：构造散列函数：确定关键词所在的存储位置的确定关键词所在的存储位置的计算方法计算方法； 解决冲突：解决冲突：当多个关键词所在的存储位置相同时的解决方法。当多个关键词所在的存储位置相同时的解决方法。【答案答案】散列查找法散列查找法是是很好很好方法之

6、一！方法之一！)(log2NO 并且，期望查找的并且，期望查找的时间复杂度时间复杂度好于好于 ，几乎是常量：几乎是常量：O（1），即查找时间与问题规模无关！），即查找时间与问题规模无关！ 当然，散列查找法也有当然，散列查找法也有缺点和局限性缺点和局限性散列表散列表的定义的定义 形如形如“名字名字(Name)-属性属性(Attribute)”对的集合的对的集合的“符号表符号表(Symbol Table)”也叫做也叫做“散列表散列表” （Hash Table，即，即哈希表哈希表）。）。类型名称类型名称:符号表（符号表（SymbolTable）数据对象集：数据对象集：符号表是符号表是“名字名字(Na

7、me)-属性属性(Attribute)”对的集合。对的集合。操作集：操作集：对于一个符号表对于一个符号表Table SymbolTable，一个给定名字，一个给定名字Name NameType，属性，属性Attr AttributeType，以及正整数，以及正整数TableSize，符号表的基本操作主要有：，符号表的基本操作主要有：1、SymbolTable InitializeTable( int TableSize )：创建一个长度为：创建一个长度为TableSize的符号表；的符号表；2、Boolean IsIn( SymbolTable Table, NameType Name)： 查

8、找特定的名字查找特定的名字Name是否在符号表是否在符号表Table中；中；3、AttributeType Find( SymbolTable Table, NameType Name)： 获取获取Table中指定名字中指定名字Name对应的属性；对应的属性；4、SymbolTable Modefy(SymbolTable Table, NameType Name, AttributeType Attr)： 将将Table中指定名字中指定名字Name的属性修改为的属性修改为Attr；5、SymbolTable Insert(SymbolTable Table, NameType Name, A

9、ttributeType Attr)： 向向Table中插入一个新名字中插入一个新名字Name及其属性及其属性Attr；6、 SymbolTable Delete(SymbolTable Table, NameType Name)： 从从Table中删除一个名字中删除一个名字Name及其属性。及其属性。1 一般想法一般想法“散列（散列（Hashing）” 的基本思想是：以数据对象的关键字的基本思想是：以数据对象的关键字key为自变量，通过一个确定的为自变量，通过一个确定的函数关系函数关系 h，计算出对应的函数值，计算出对应的函数值h(key)，把这个值解释为数据对象的存储地址，并按此存放，即，

10、把这个值解释为数据对象的存储地址，并按此存放，即“存储位置存储位置 = h（key）”。 散列方法中使用的计算函数称为散列方法中使用的计算函数称为“散列函数散列函数” （也称哈希函数），（也称哈希函数），按这个思想构造的表称为按这个思想构造的表称为“散列表散列表”，所以它也是一种存储方法。，所以它也是一种存储方法。 在查找某数据对象时，用同样的方法在查找某数据对象时，用同样的方法“存储位置存储位置 = h（key）”计计算出地址，将算出地址，将key与该地址单元中数据对象关键字进行比较，确定查与该地址单元中数据对象关键字进行比较，确定查找是否成功。找是否成功。通常关键词的通常关键词的值域值域（

11、允许取值的范围）远远大于表空间的（允许取值的范围）远远大于表空间的地址地址集集，所以说，所以说，冲突不可能避免，只能尽可能减少冲突不可能避免，只能尽可能减少。 可能将可能将不同的关键字映射到同一个散列地址不同的关键字映射到同一个散列地址上，即上，即h(keyi) = h(keyj)（当（当keyi keyj），这种现象称为），这种现象称为“冲突冲突(Collision)”， keyi 和和keyj称为称为“同义词（同义词（synonym）”。1 一般想法一般想法散列表散列表0 1 s 1 ht 0 ht 1 ht b 1 b bucketss slots 对每一个标识符对每一个标识符key,

12、我们我们定义一个定义一个hash函数（散列函数）函数（散列函数） h ( key ) = key 在在 ht 中的位置中的位置 (如：包含如：包含 key 的桶的索引号）的桶的索引号）1 一般想法一般想法例例4有有n = 11个数据对象的集合，关键词是正整数，分别为个数据对象的集合，关键词是正整数，分别为 18，23，11，20，2，7，27，30，42，15，34。如果符号表的。如果符号表的大小用大小用TableSize = 17（通常用一个素数），选取散列函数（通常用一个素数），选取散列函数h如下：如下：h(key) = key mod TableSize （公式（公式 5.1）其中其中m

13、od 是求余运算，相当于是求余运算，相当于C语言中的语言中的%运算。运算。用这个散列函数对用这个散列函数对11个数据对象建立查找表（个数据对象建立查找表（忽略各关键词对应的属性部分，该例的关键词没有冲突）如下：）如下： 查找时，对给定关键词查找时，对给定关键词keyi依然通过公式依然通过公式5.1计算出地址，再计算出地址，再将将keyi与该地址单元中关键词比较，若相等，则查找成功。与该地址单元中关键词比较，若相等，则查找成功。 比如查找：比如查找：key = 22, 地址是地址是22%17 = 5，该地址空表示表中，该地址空表示表中没有关键词没有关键词22的信息。的信息。比如查找：比如查找：k

14、ey = 40, 地址是地址是40%17 = 6，该地址存的是，该地址存的是23，40 23，故还要采用后面介绍的，故还要采用后面介绍的解决冲突解决冲突的策略才能确定。的策略才能确定。地址地址0123456789 10 11 12 13 14 15 16关键词关键词 34 18 2 2023 7 4227 113015【定义定义】 设散列表空间大小为设散列表空间大小为m，填入表中的元素个数是，填入表中的元素个数是n，则称，则称 n / m为散列表的为散列表的“装填因子（装填因子（Loaf(i)ng Factor）”。 装填因子装填因子 11 / 17 0.65。 实用时，常将散列表大小设计使得

15、实用时，常将散列表大小设计使得 0.50.8为宜为宜。1 一般想法一般想法例例5将给定的将给定的10个个C语言中的关键词语言中的关键词(保留字或标准函数名保留字或标准函数名)顺次存入一张散列表。这顺次存入一张散列表。这10个关键词为：个关键词为：acos、define、float、exp、char、atan、ceil、floor、clock、ctime。散列表设计为一个散列表设计为一个二维数组二维数组Table262，2列分别代表列分别代表 2个槽。个槽。 槽槽 1槽槽 0012345625装填因子装填因子 ?10 / 52 = 0.19为了把字母为了把字母 a z 映射到映射到 0 25,

16、如何设计散列如何设计散列函数函数h (key ) = ? h(key) = key0 aacosacosdefinedefinefloatfloatexpexpcharcharatanatanceilceilfloorfloorclockctime如何设计如何设计散列函数散列函数，使得，使得发生发生冲突的概率冲突的概率尽可能小？尽可能小？当当冲突或溢出冲突或溢出不可避免时，不可避免时，如如何处理何处理使得表中没有空单元被使得表中没有空单元被浪费，同时浪费，同时插入、删除、查找插入、删除、查找等操作都能正确完成？等操作都能正确完成？1 一般想法一般想法h的特征的特征: h ( key ) 应当应

17、当易于易于计算，且使计算，且使冲突最少化冲突最少化。 h(key)应当是均匀的，也就是说，对任意的应当是均匀的，也就是说，对任意的key和任意的和任意的i，Probability( h(key)= i ) = 1 / b。这种类型的散列函数被称。这种类型的散列函数被称为为均匀哈希函数（均匀哈希函数（uniform hash function）。）。2 散列函数散列函数h(key)= key % TableSize ; /* 若若x是整数是整数*/ 如果如果 TableSize = 10 且且 key 都以都以0为个位，会怎样呢为个位，会怎样呢? TableSize = 素数素数- 当关键字是随

18、机整数时，是个当关键字是随机整数时，是个好的散列函数好的散列函数2 散列函数散列函数h(key)= ( keyi) % TableSize ; /* 若若x是字符串是字符串 */例例6 TableSize = 10,007 ，字符串长度，字符串长度 8. 如果如果 keyi 0, 127, 那么那么 h(key) 0, ? 1016h(key)= (key0+ key1*27 + key2*272) % TableSize ;总的组合数总的组合数 （理论上）（理论上）= 263 = 17,576 实际组合数实际组合数 3000h(key)= ( keyN i 1 * 32i ) % Table

19、Size ;key0 key1keyN-2 keyN-1Index Hash3( const char *x, int TableSize ) unsigned int HashVal = 0; /* 1*/ while( *x != 0 ) /* 2*/ HashVal = ( HashVal 5 ) + *x+; /* 3*/ return HashVal % TableSize; 比比*27要快要快你能让它更你能让它更快吗？快吗？ 如果如果 key 太长太长 (如：街道地址如：街道地址), 前面的字符会左移出前面的字符会左移出界。界。 选择关键字选择关键字中的部分字中的部分字符。符。2

20、散列函数散列函数 处理冲突的方法处理冲突的方法常用的处理冲突的方法有两种：常用的处理冲突的方法有两种：分离链接法；分离链接法；开放定址法开放定址法。分离链接法分离链接法（Separate Chaining）【定义定义】分离链接法是解决冲突的一种方法，其做法是将所有关分离链接法是解决冲突的一种方法，其做法是将所有关键词为键词为同义词同义词的数据对象通过结点链接存储的数据对象通过结点链接存储在同一个单链表中在同一个单链表中。struct ListNode; typedef struct ListNode *Position; struct HashTbl; typedef struct HashT

21、bl *HashTable; struct ListNode ElementType Element; Position Next; ; typedef Position List; /* List *TheList will be an array of lists, allocated later */ /* The lists use headers (for simplicity), */ /* though this wastes space */ struct HashTbl int TableSize; List *TheLists; ; 3 分离链接法分离链接法例例7设关键字序

22、列为设关键字序列为 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21; 散列函数取为：散列函数取为：h(key) = key mod 11。 用用分离链接法分离链接法处理冲突。处理冲突。 94 50 16 22 3 89 11 47 37 92 29 7 8 21 01 23 4567 8910H11HashTable InitializeTable( int TableSize ) HashTable H; int i; if ( TableSize TableSize = NextPrime( TableSize ); /* Bette

23、r be prime */ H-TheLists = malloc( sizeof( List ) * H-TableSize ); /*Array of lists*/ if ( H-TheLists = NULL ) FatalError( Out of space! ); for( i = 0; i TableSize; i+ ) /* Allocate list headers */H-TheLists i = malloc( sizeof( struct ListNode ) ); /* Slow! */if ( H-TheLists i = NULL ) FatalError( O

24、ut of space! ); else H-TheLists i -Next = NULL; return H; 3 分离链接法分离链接法 创建空散列表创建空散列表HTheListsTableSize3 分离链接法分离链接法 在散列表中查找在散列表中查找keyPosition Find ( ElementType Key, HashTable H ) Position P; List L; L = H-TheLists Hash( Key, H-TableSize ) ; P = L-Next; while( P != NULL & P-Element != Key ) /* Pro

25、bably need strcmp */ P = P-Next; return P; 你的散列函数你的散列函数等同于第三章中给出的执行等同于第三章中给出的执行Find 的的程序程序 - List ADT3 分离链接法分离链接法 向散列表中插入向散列表中插入 key void Insert ( ElementType Key, HashTable H ) Position Pos, NewCell; List L; Pos = Find( Key, H ); if ( Pos = NULL ) /* Key is not found, then insert */NewCell = malloc

26、( sizeof( struct ListNode ) ); if ( NewCell = NULL ) FatalError( Out of space! ); else L = H-TheLists Hash( Key, H-TableSize ) ; NewCell-Next = L-Next; NewCell-Element = Key; /* Probably need strcpy! */ L-Next = NewCell; 再一次再一次?! Tip: 使表的大小与预期的使表的大小与预期的keys的数量大致相等的数量大致相等 (即使装填因子即使装填因子 1). 开放定址法（开放定址

27、法（Open Addressing）【定义定义】所谓开放定址法，就是一旦产生了所谓开放定址法，就是一旦产生了冲突冲突，即该地址，即该地址已经存放了其它数据元素，就去已经存放了其它数据元素，就去寻找另一个空的散列地址寻找另一个空的散列地址。 若发生了第若发生了第 i 次冲突，试探的下一个地址将增加次冲突，试探的下一个地址将增加f(i)，基本公式是：基本公式是：hi(key) = (h(key)+f(i) mod TableSize ( 1 i TableSize ) f(i)决定了不同的解决冲突方案：决定了不同的解决冲突方案：线性探测、二次探测、双散列线性探测、二次探测、双散列。在在没有装满没有

28、装满的散列表中，的散列表中，空的散列地址空的散列地址是否总能找到是否总能找到？f(i)= if(i) = i2f(i) = i*h2(key)Algorithm: insert key into an array of hash table index = hash(key); initialize i = 0 - the counter of probing; while ( collision at index ) index = ( hash(key) + f(i) ) % TableSize;if ( table is full ) break;else i +; if ( table

29、 is full )ERROR (“No space left”); elseinsert key at index;冲突解决函数冲突解决函数f(0) = 0. Tip: 平均平均 0.5.例例8 将将n = 11个个C的库函数映射到一个散列表的库函数映射到一个散列表 ht ，其中，其中b = 26 buckets ， s = 1.1. 线性探测法线性探测法（Linear Probing） 以以增量序列增量序列 1，2，（，（TableSize -1）循环试探下一个存储地址。循环试探下一个存储地址。4 开放定址法开放定址法f ( i ) = i ; /* 线性函数线性函数 */acos ato

30、i char define exp ceil cos float atol floor ctimebucketx012345678910 25search timeacos1atoi2char1define1exp1ceil4cos5float3atol9floor5ctime9装填因子装填因子 = 11 / 26 = 0.42平均搜索次数平均搜索次数 = 41 / 11 = 3.73虽然虽然 p 不大不大,但最坏情形可能会但最坏情形可能会很大很大.使用线性探测的使用线性探测的预期探测次数：预期探测次数： 对对成成功功的的查查找找 ) )1 1( (对对插插入入和和不不成成功功的的查查找找 )

31、 )1 1( (1 11 12 21 1) )1 1( (1 12 21 12 2 p p= 1.36造成一造成一次聚集次聚集( primary clustering): 散列到区块中的任何散列到区块中的任何key都需要多次都需要多次试选单元才能解决冲突，然后该关试选单元才能解决冲突，然后该关键字才被添加到相应区块中键字才被添加到相应区块中例例9设关键词序列为设关键词序列为 47，7，29，11，9，84，54，20，30， 散列表表长散列表表长TableSize =13， 装填因子装填因子 = 9/13 0.69； 散列函数为：散列函数为：h(key) = key mod 11。 用用线性探

32、测法线性探测法处理冲突，列出依次插入后的散列表，处理冲突，列出依次插入后的散列表， 并估算查找性能。并估算查找性能。关键词关键词 (key)4772911984542030散散列地址列地址 h(key)37709710984 开放定址法开放定址法地址地址操作操作0123456789101112说说 明明插入插入4747无冲突无冲突插入插入7477无冲突无冲突插入插入2947729d1 = 1插入插入111147729无冲突无冲突插入插入911477299无冲突无冲突插入插入841147729984d3 = 3插入插入54114772998454d1 = 1插入插入201147729984542

33、0d3 = 3插入插入30113047 7299845420d6 = 6“一次聚集一次聚集（Primary Clustering）”现象：需要经过现象：需要经过很很多次冲突多次冲突才找到空位置。才找到空位置。表表线性探测法构建散列表的过程线性探测法构建散列表的过程关键词关键词 (key)4772911984542030散散列地址列地址 h(key)3770971098冲突次数冲突次数0010031364 开放定址法开放定址法 图图5-12表示了期望探测次数与装填因子表示了期望探测次数与装填因子 的关系。的关系。图图5-12 线性探测法（虚线）、随机方法（实线）线性探测法（虚线）、随机方法（实线

34、）U表示不成功查找，表示不成功查找，I表示插入，表示插入，S表示成功查找表示成功查找当装填因子当装填因子 0.5的时候，各的时候，各种探测法的种探测法的期望探测次数都期望探测次数都不大不大，也比较接近。，也比较接近。随着随着 的增大，线性探测法的期望的增大，线性探测法的期望探测次数增加较快，探测次数增加较快，不成功查找和不成功查找和插入操作插入操作的期望探测次数比成功查的期望探测次数比成功查找的期望探测次数找的期望探测次数要大要大。合理的的最大装入因子应合理的的最大装入因子应该该不超过不超过0.85。2. 平方探测法平方探测法（Quadratic Probing） 即即平方探测法平方探测法以增

35、量序列以增量序列12，-12，22，-22，q2，-q2且且q TableSize/2 循环试探下一个存储地址。循环试探下一个存储地址。4 开放定址法开放定址法f ( i ) = i 2 ; /* 一个平方函数一个平方函数*/例例10设关键词序列为设关键词序列为 47，7，29，11，9，84，54，20，30 散列表表长散列表表长TableSize = 11（即满足（即满足42+3形式的素数）形式的素数） 装填因子装填因子 = 9/11 0.82 散列函数为：散列函数为：h(key) = key mod 11 用用平方探测法平方探测法处理冲突，列出依次插入后的散列表处理冲突，列出依次插入后的

36、散列表关键词关键词 key4772911984542030散散列地址列地址h(key)3770971098表平方探测法构建散列表的过程表平方探测法构建散列表的过程地址地址操作操作012345678910说说 明明插入插入4747无冲突无冲突插入插入7477无冲突无冲突插入插入2947729d1 = 1插入插入111147729无冲突无冲突插入插入911477299无冲突无冲突插入插入841147847299d2 = -1插入插入54114784729954无冲突无冲突插入插入2011204784729954d3 = 4插入插入3011302047 84729954d3 = 4“二次聚集二次聚集

37、（Secondary Clustering） ”现象：现象：散列到同一地址的那些数据对象散列到同一地址的那些数据对象将探测相同的备选单元将探测相同的备选单元。关键词关键词 key4772911984542030散散列地址列地址h(key)3770971098冲突次数冲突次数0010020334 开放定址法开放定址法30【定理定理】如果使用平方探测，且表的大小是如果使用平方探测，且表的大小是素数素数，那么当表，那么当表至少有一至少有一半是空半是空的时候，总能够插入一个新元素。的时候，总能够插入一个新元素。证明证明: 证明前证明前 TableSize/2 个备选位置是个备选位置是互异的互异的。即对

38、任意。即对任意 0 TableSize ); while( H-TheCells CurrentPos .Info != Empty & H-TheCells CurrentPos .Element != Key ) CurrentPos += 2 * +CollisionNum 1; if ( CurrentPos = H-TableSize ) CurrentPos = H-TableSize; return CurrentPos; 比比mod快快返回结果是什么返回结果是什么?f(i)=f(i 1)+2i 12* 是移位操作是移位操作如果这两个条件如果这两个条件交换会怎样？交换会怎

39、样？4 开放定址法开放定址法void Insert ( ElementType Key, HashTable H ) Position Pos; Pos = Find( Key, H ); if ( H-TheCells Pos .Info != Legitimate ) /* OK to insert here */ H-TheCells Pos .Info = Legitimate; H-TheCells Pos .Element = Key; /* Probably need strcpy */ Question: 怎样删除怎样删除key?Note: 如果如果插入和删除混合的插入和删除混合的次数过多，插入会明显变慢。次数过多，插入会明显变慢。 即使一次聚集问题解决了，即使一次聚集问题解决了，二次聚集二次聚集问题仍然存在。问题仍然存在。3. 双散列探测法双散列探测