电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

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

39页
  • 卖家[上传人]:F****n
  • 文档编号:88241745
  • 上传时间:2019-04-21
  • 文档格式:PPT
  • 文档大小:996.50KB
  • / 39 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、Preview,一种用于以常数平均时间执行插入、删除和查找的技术 不支持需要元素间任何排序信息的操作,散 列 表,第五章 散列,1 一般想法,已有几种查找方法:,已经是相当不错的时间复杂度!,为二叉查找树的高度,到底还有没有其他适应性广 而速度又快的查找方法呢?,1 一般想法,例1在登录QQ的时候,QQ服务器如何核对你的身份,以确定你就是该号码的主人?,【分析】看看是否可以用二分法查找。, 十亿(109 230)有效用户,用二分查找30次。, 十亿(109 230) 1K 1024G,1T连续空间。, 按有效QQ号大小有序存储:在连续存储空间中,插入和删除一个新QQ号码将需要移动大量数据。,用不了二分查找, 我们该怎么办?,1 一般想法,例2查英文字典的过程查询英文单词“zoo”,你为什么不用二分法,而直接从字典的后面找?, 我们已经根据要查找的关键词“zoo”在脑子里经过了“计算”,得出该关键词所在的大致位置,这样就能更快地找到它。这个“计算”过程非常类似于本章将要介绍的散列查找中的“散列函数计算”。,查字典的过程结合了散列查找(用于初步定位)、二分查找(一般不是准确二分)和顺序查找

      2、(当很接近关键词的时候)等几种查找方法。,1 一般想法,例3网上搜索。搜索引擎是如何如此神速地把我们需要的有关信息找到的?,【分析】主要数据结构是“倒排索引” - “单词到文档”的映射关系。,如何在这个巨大无比的表格 中查找特定的关键词?,【问题】如何能够在极短的时间内(比如1秒内)搜索到需要的关键词?,1 一般想法, 散列查找法的两项基本工作: 构造散列函数:确定关键词所在的存储位置的计算方法; 解决冲突:当多个关键词所在的存储位置相同时的解决方法。,【答案】散列查找法是很好方法之一!, 并且,期望查找的时间复杂度好于 , 几乎是常量:O(1),即查找时间与问题规模无关!, 当然,散列查找法也有缺点和局限性,散列表的定义,形如“名字(Name)-属性(Attribute)”对的集合的“符号表(Symbol Table)”也叫做“散列表” (Hash Table,即哈希表)。,类型名称:符号表(SymbolTable) 数据对象集:符号表是“名字(Name)-属性(Attribute)”对的集合。 操作集:对于一个符号表Table SymbolTable,一个给定名字Name Name

      3、Type,属性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

      4、 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, 我们定义一个has

      5、h函数(散列函数) 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为散列表的“装填因子(Lo

      6、af(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的特征

      7、:, 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

      8、 ;,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;

      9、 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

      《湘潭大学-数据结构-课件-ppt-ch05-hashing》由会员F****n分享,可在线阅读,更多相关《湘潭大学-数据结构-课件-ppt-ch05-hashing》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.