湘潭大学-数据结构-课件-ppt-ch05-hashing

Preview,一种用于以常数平均时间执行插入、删除和查找的技术 不支持需要元素间任何排序信息的操作,散 列 表,第五章 散列,§1 一般想法,已有几种查找方法：,已经是相当不错的时间复杂度!,为二叉查找树的高度,到底还有没有其他适应性广 而速度又快的查找方法呢？,§1 一般想法,例1在登录QQ的时候，QQ服务器如何核对你的身份，以确定你就是该号码的主人？,【分析】看看是否可以用二分法查找。, 十亿（109 230）有效用户，用二分查找30次。, 十亿（109 230） × 1K 1024G，1T连续空间。, 按有效QQ号大小有序存储：在连续存储空间中，插入和删除一个新QQ号码将需要移动大量数据。,用不了二分查找， 我们该怎么办？,§1 一般想法,例2查英文字典的过程查询英文单词“zoo”，你为什么不用二分法，而直接从字典的后面找？, 我们已经根据要查找的关键词“zoo”在脑子里经过了“计算”，得出该关键词所在的大致位置，这样就能更快地找到它。这个“计算”过程非常类似于本章将要介绍的散列查找中的“散列函数计算”。,查字典的过程结合了散列查找（用于初步定位）、二分查找（一般不是准确二分）和顺序查找（当很接近关键词的时候）等几种查找方法。,§1 一般想法,例3网上搜索。搜索引擎是如何如此神速地把我们需要的有关信息找到的？,【分析】主要数据结构是“倒排索引” - “单词到文档”的映射关系。,如何在这个巨大无比的表格 中查找特定的关键词？,【问题】如何能够在极短的时间内（比如1秒内）搜索到需要的关键词？,§1 一般想法, 散列查找法的两项基本工作： 构造散列函数：确定关键词所在的存储位置的计算方法； 解决冲突：当多个关键词所在的存储位置相同时的解决方法。,【答案】散列查找法是很好方法之一！, 并且，期望查找的时间复杂度好于 ， 几乎是常量：O（1），即查找时间与问题规模无关！, 当然，散列查找法也有缺点和局限性,散列表的定义,形如“名字(Name)-属性(Attribute)”对的集合的“符号表(Symbol Table)”也叫做“散列表” （Hash Table，即哈希表）。,类型名称:符号表（SymbolTable） 数据对象集：符号表是“名字(Name)-属性(Attribute)”对的集合。 操作集：对于一个符号表Table SymbolTable，一个给定名字Name NameType，属性Attr AttributeType，以及正整数TableSize，符号表的基本操作主要有： 1、SymbolTable InitializeTable( int TableSize )：创建一个长度为TableSize的符号表； 2、Boolean IsIn( SymbolTable Table, NameType Name)： 查找特定的名字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, AttributeType Attr)： 向Table中插入一个新名字Name及其属性Attr； 6、 SymbolTable Delete(SymbolTable Table, NameType Name)： 从Table中删除一个名字Name及其属性。,§1 一般想法,“散列（Hashing）” 的基本思想是：以数据对象的关键字key为自变量，通过一个确定的函数关系 h，计算出对应的函数值h(key)，把这个值解释为数据对象的存储地址，并按此存放，即“存储位置 = h（key）”。, 散列方法中使用的计算函数称为“散列函数” （也称哈希函数），按这个思想构造的表称为“散列表”，所以它也是一种存储方法。, 在查找某数据对象时，用同样的方法“存储位置 = h（key）”计算出地址，将key与该地址单元中数据对象关键字进行比较，确定查找是否成功。,通常关键词的值域（允许取值的范围）远远大于表空间的地址集，所以说，冲突不可能避免，只能尽可能减少。, 可能将不同的关键字映射到同一个散列地址上，即h(keyi) = h(keyj)（当keyi keyj），这种现象称为“冲突(Collision)”， keyi 和keyj称为“同义词（synonym）”。,§1 一般想法,散列表,对每一个标识符key, 我们定义一个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） 其中mod 是求余运算，相当于C语言中的%运算。 用这个散列函数对11个数据对象建立查找表（忽略各关键词对应的属性部分，该例的关键词没有冲突）如下：, 查找时，对给定关键词keyi依然通过公式5.1计算出地址，再将keyi与该地址单元中关键词比较，若相等，则查找成功。 比如查找：key = 22, 地址是22%17 = 5，该地址空表示表中没有关键词22的信息。 比如查找：key = 40, 地址是40%17 = 6，该地址存的是23，40 23，故还要采用后面介绍的解决冲突的策略才能确定。,【定义】 设散列表空间大小为m，填入表中的元素个数是n，则称 n / m为散列表的“装填因子（Loaf(i)ng Factor）”。 装填因子 11 / 17 0.65。 实用时，常将散列表大小设计使得 0.50.8为宜。,§1 一般想法,例5将给定的10个C语言中的关键词(保留字或标准函数名)顺次存入一张散列表。这10个关键词为：acos、define、float、exp、char、atan、ceil、floor、clock、ctime。散列表设计为一个二维数组Table262，2列分别代表 2个槽。,装填因子 ?,10 / 52 = 0.19,为了把字母 a z 映射到 0 25, 如何设计散列函数h (key ) = ?,h(key) = key0 a,acos,acos,define,define,float,float,exp,exp,char,char,atan,atan,ceil,ceil,floor,floor,clock,ctime,如果没有溢出, T查询 = T插入 = T删除 = O( 1 ),如何设计散列函数，使得发生冲突的概率尽可能小？,当冲突或溢出不可避免时，如何处理使得表中没有空单元被浪费，同时插入、删除、查找等操作都能正确完成？,§1 一般想法,h的特征:, h ( key ) 应当易于计算，且使冲突最少化。, h(key)应当是均匀的，也就是说，对任意的key和任意的i，Probability( h(key)= i ) = 1 / b。这种类型的散列函数被称为均匀哈希函数（uniform hash function）。,§2 散列函数,h(key)= key % TableSize ; /* 若x是整数*/, 如果 TableSize = 10 且 key 都以0为个位，会怎样呢?, TableSize = 素数- 当关键字是随机整数时，是个好的散列函数,§2 散列函数,h(key)= ( keyi) % TableSize ; /* 若x是字符串 */,例6 TableSize = 10,007 ，字符串长度 8. 如果 keyi 0, 127, 那么 h(key) 0, ? ,1016,h(key)= (key0+ key1*27 + key2*272) % TableSize ;,总的组合数 （理论上）= 263 = 17,576, 实际组合数 3000,h(key)= ( keyN i 1 * 32i ) % TableSize ;,Index 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 散列函数, 处理冲突的方法,常用的处理冲突的方法有两种： 分离链接法； 开放定址法。,分离链接法（Separate Chaining）,【定义】分离链接法是解决冲突的一种方法，其做法是将所有关键词为同义词的数据对象通过结点链接存储在同一个单链表中。,struct ListNode; typedef struct ListNode *Position; struct HashTbl; typedef struct HashTbl *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设关键字序列为 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21; 散列函数取为：h(key) = key mod 11。 用分离链接法处理冲突。,HashTable InitializeTable( int TableSize ) HashTable H; int i; if ( TableSize TableSize = NextPrime( TableSize ); /* Better 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( “Out of s