- 1、本文档共38页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构 第九章 动态查找
* 一、哈希表是什么? 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作 六、哈希表也可用来构造静态查找表 9.3 哈 希 表 以上两节讨论的表示查找表的各种结构的共同特点:记录在表中的位置和它的关键字之间不存在一个确定的关系, 一、哈希表是什么? 查找的过程为给定值依次和关键字集合中各个关键字进行比较, 查找的效率取决于和给定值进行比较的关键字个数。 用这类方法表示的查找表,其平均查找长度都不为零。 不同的表示方法,其差别仅在于: 关键字和给定值进行比较的顺序不同。 只有一个办法:预先知道所查关键字在表中的位置, 对于频繁使用的查找表,希望 ASL = 0。 即,要求:记录在表中位置和其关键字之间存在一种确定的关系。 若以下标为000 ~ 999 的顺序表表示之。 例如:为每年招收的 1000 名新生建立一张查找表,其关键字为学号,其值的范围为 xx000 ~ xx999 (前两位为年份)。 则查找过程可以简单进行:取给定值(学号)的后三位,不需要经过比较便可直接从顺序表中找到待查关键字。 但是,对于动态查找表而言, 因此在一般情况下,需在关键字与记录在表中的存储位置之间建立一个函数关系,以 f(key) 作为关键字为 key 的记录在表中的位置,通常称这个函数 f(key) 为哈希函数。 1) 表长不确定; 2) 在设计查找表时,只知道关键字所属 范围,而不知道确切的关键字。 {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dai} 例如:对于如下 9 个关键字 设 哈希函数 f(key) =?(Ord(第一个字母) -Ord(A)+1)/2? Chen Zhao Qian Sun Li Wu Han Ye Dai 问题: 若添加关键字 Zhou , 怎么办? 能否找到另一个哈希函数? 1) 哈希函数是一个映象,即:将关键字的集合映射到某个地址集合上, 它的设置很灵活,只要这个地址集合的大小不超出允许范围即可; 从这个例子可见: 2) 由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生“冲突”现象,即: key1? key2,而 f(key1) = f(key2)。 3) 很难找到一个不产生冲突的哈希函数。一般情况下,只能选择恰当的哈希函数,使冲突尽可能少地产生。 因此,在构造这种特殊的“查找表” 时,除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。 哈希表的定义: 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法,将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上,并以关键字在地址集中的“象”作为相应记录在表中的存储位置,如此构造所得的查找表称之为“哈希表”。 二、构造哈希函数的方法 对数字的关键字可有下列构造方法: 若是非数字关键字,则需先对其进行数字化处理。 1. 直接定址法 3. 平方取中法 5. 除留余数法 4. 折叠法 6. 随机数法 2. 数字分析法 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a ? key + b 1. 直接定址法 此法仅适合于: 地址集合的大小 = = 关键字集合的大小 此方法仅适合于: 能预先估计出全体关键字的每一位上各种数字出现的频度。 2. 数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us),分析关键字集中的全体, 并从中提取分布均匀的若干位或它们的组合作为地址。 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ,同时平方值的中间各位又能受到整个关键字中各位的影响。 3. 平方取中法 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。 将关键字分割成若干部分,然后取它们的叠加和为哈希地址。有两种叠加处理的方法:移位叠加和间界叠加。 4. 折叠法 此方法适合于: 关键字的数字位数特别多。 5. 除留余数法 设定哈希函数为: H(key) = key MOD p 其中, p≤m (表长) 并且 p 应为不大于 m 的素数
您可能关注的文档
最近下载
- AP宏观经济学 2012年真题 (选择题+问答题) AP Macroeconomics 2012 Released Exam and Answers (MCQ+FRQ).pdf VIP
- 浙科版《综合实践活动》五下 第五课 活动A、我当小法官—走进法庭教案.doc
- 8.1 认识生命 课件-2024-2025学年统编版道德与法治七年级 上册 ).pptx VIP
- 化工制图教学设计(全套).docx VIP
- 2024-2030年中国氦(液氦和气态氦)行业市场发展趋势与前景展望战略分析报告.docx
- AP宏观经济学(2013年真题)全套含选择题.pdf VIP
- 自考00537中国现代文学史重点知识点汇总速记宝典.pdf
- 建积分之术筑工程之技:定积分及其应用教学实施报告.pdf
- AP宏观经济学(2015年真题)全套含选择题.pdf VIP
- 英语--倒装句讲解..ppt VIP
文档评论(0)