“负载因子”。-read.ppt

  1. 1、本文档共108页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法与数据结构 第十章 散 列 结 构 枚举向量,这种向量中使用的下标不是整数,而是某枚举类型的实例。 对枚举向量,查询的出发点是一个枚举值,要做就是由这个枚举值出发,确定有关数据元素的存储位置。 作为查询出发点的值可能有各种不同情况,需要进一步研究有关的技术和方法。 在集合与字典的一章里,已经讨论了一些结构和技术,那里使用的基本技术是关键码比较。 散列结构与枚举向量有类似之处:这里采用的基本存储结构也是一个向量,要做的也是从关键码出发,直接确定数据元素的存储位置。但是散列结构更具一般性,原则上说它允许任意种类的关键码。 设计良好的散列结构可以具有非常高的操作效率,因此这种结构在计算机领域中应用广泛,是一种非常有效的存储和查询结构。 下面将首先介绍散列结构的基本思想,然后重点讨论散列结构实现的两个基本要素:散列函数和“碰撞”的各种解决技术。本章的后面部分把散列结构作为集合和字典的重要实现技术,讨论这些方面的有关问题。 10.1 基本概念 散列函数是一种数据转换函数,它的参数应该是某种查询的依据,一般称为“关键词”或“关键码”,而函数返回的是一个无符号整数值,作为确定下标的依据。 散列的基本想法就是构造一个对应关系,把每个关键码对应到一个整数(存储位置)。这样,如果需要存储与某个关键码相关的数据,就将它存到与关键码对应的存储位置里去;如果需要查询与某个关键码有关的信息,就到与这个关键码对应的位置中去找。 “散列”(hash)一词的意思是进行某种混合性的变换,从关键码本身看,这种变换可能并没有很清楚的具体意义。散列这个词在有些中文教科书或文献中被译为“杂凑”,散列结构也被称为“散列表”、“杂凑表”,或者按照音译称为“哈希表”等。 根据散列函数概念,可以定义一种新向量类,叫作simpleHashVector类(简单散列向量类)。这里把它定义为向量类Vector的一个子类。简单散列向量比普通向量多一个数据成分,那就是一个指向散列函数的指针hashfun。对具体的简单散列向量而言,这个数据成分是在构造时建立,是一种不能改变的性质。 简单散列向量类有两个类型参数,一个是向量的索引(关键码)类型H,另一个是向量元素类型T。 ? template class H, class T class simpleHashVector : public vectorT { public: //构造函数 simpleHashVector(int max, int (?f)(const H )); simpleHashVector(int max, int (?f)(const H ), T initialValue); simpleHashVector(const simpleHashVectorH, T v); //下标操作 T operator [ ] (const H index); private: // 记录散列函数的函数指针 const int (?hashfun)(const H );[qzy1] }; 类10.1 simpleHashVector类规范说明 ? 简单散列向量类的定义与枚举向量有相似的地方,例如对它们都可以用字符序列形式的向量下标直接存取相关元素。 但是对于枚举向量,作为下标的字符序列必须是某个枚举类型的值,下标操作的实现是由系统自动将枚举值转换成内部整数值。而对于简单散列向量,则可以使用真正的字符串,这种字符串可以送去打印等。 在查询元素位置时,散列结构首先用给定的散列函数,把H类型的关键码(可以看作是一种广义“下标”)转换成一个适当的整数值,然后再把该整数转换成对于向量合法的下标值。后一转换一般直接采用按向量大小取余数的方式。 ? template class H,class T T hashVectorH,T::operator[ ] (const H index) { return vectorT::operator[ ]((?hashfun)(index) % size); } ? 简单散列向量类的其他成员函数都非常简单。读者不难自己实现它们。 10.2 散 列 函 数 理想的散列函数是个一对一映射,它能把有关的一组关键码映射到连续的一组整数值,每个关键码对应一个整数值,反之依然。 10.3 开地址散列向量 为了解决碰撞,人们提出了许多方法,本节先介绍其中的一种,称为“开地址法”。用这种方法建立的散列结构称为“开地址散列向量”。 类10.2给出openHashVector的规范说明。为了叙述简单,我们假设向量中每个元素都只包含关键码自身,元素类型就是关键码类型。这时模板类的参数只

文档评论(0)

189****0315 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档