伍佰目录 短网址
  当前位置:海洋目录网 » 站长资讯 » 站长资讯 » 文章详细 订阅RssFeed

算法篇-数据结构3

来源:本站原创 浏览:155次 时间:2022-02-26

哈希:

  1. 在记录的存储地址和它的关键字之间建立一个确定的对应关系;这样不经过比较,一次存取就能得到元素。

  2. 哈希函数——在记录的关键字与记录的存储位置之间建立的一种对应关系。是从���,��Ǩ关键字空间到存储位置空间的一种映象。

  3. 哈希表——应用哈希函数,由记录的关键字确定记录在表中的位置信息,并将记录根据此信息放入表中,这样构成的表叫哈希表。

  4. Hash查找适合于关键字可能出现的值的集合远远大于实际关键字集合的情形。

  5. 更适合查找,不适合频繁更新

  6. Hash表等查找复杂依赖于Hash值算法的有效性,在最好的情况下,hash表查找复杂度为O(1)。只有无冲突的hash_table复杂度才是O(1)。一般是O(c),c为哈希关键字冲突时查找的平均长度。插入,删除,查找都是O(1)。平均查找长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大

7.由于冲突的产生,使得哈希表的查找过程仍然是一个给定值与关键字比较的过程。

  • 根据抽屉原理,冲突是不可能完全避免的,所以,选择好的散列函数和冲突处理方法:

    1.构造一个性能好,冲突少的Hash函数

    2.如何解决冲突

常用的哈希函数

  1. 直接定址法、仅适合于:地址集合的大小 == 关键字集合的大小

  2. 数字分析法、对关键字进行分析,取关键字的若干位或其组合作哈希地址。仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。

  3. 平方取中法、以关键字的平方值的中间几位作为存储地址。

  4. 折叠法、将关键字分割成位数相同的几部分,然后取这几部分的叠加和(舍去进位)做哈希地址。移位叠加/间界叠加。

适合于:

关键字的数字位数特别多,且每一位上数字分布大致均匀情况。

  1. 除留余数法、取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址,即H(key)=key%p,p<=m。

  2. 随机数法、取关键字的伪随机函数值作哈希地址,即H(key)=random(key),适于关键字长度不等的情况。

冲突解决

  1. 开放定址法。

当冲突发生时,形成一个探查序列;

沿此序列逐个地址探查,直到找到一个空位置(开放的地址),将发生冲突的记录放到该地址中。

即Hi=(H(key)+di) % m,i=1,2,……k(k<=m-1),H(key)哈希函数,m哈希表长,di增量序列。

缺点:删除:只能作标记,不能真正删除;溢出;载因子过大、解决冲突的算法选择不好会发生聚集问题。

要求装填因子α较小,故当结点规模较大时会浪费很多空间。

线性探测再散列:di=1,2,3,…,m-1二次探测再散列:di=12,-12,22,-22,…,±k2(k<=m/2)伪随机探测再散列: di为伪随机数序列
  1. 链地址法:将所有关键字为同义词的记录存储在一个单链表中,并用一维数组存放头指针。

拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间。

一旦发生冲突,在当前位置给单链表增加结点就行。

  1. 其他方法:再哈希法、建立公共溢出区

在用拉链法构造的散列表中,删除结点的操作易于实现。

拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间。

由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况。拉链法解决冲突时,需要使用指针,指示下一个元素的存储位置

  1. 开哈希表–链式地址法;闭哈希表–开放地址法.开哈希和闭哈希主要的区别在于,随着哈希表的密集度提高,使用闭哈希时,不仅会与相同哈希值的元素发生冲突,还容易与不同哈希值的元素发生冲突;

而开哈希则不受哈希表疏密与否的影响,始终只会与相同哈希值的元素冲突而已。

所以在密集度变大的哈希表中查找时,显然开哈希的平均搜索长度不会增长。

  1. 设有n个关键字具有相同的Hash函数值,则用线性探测法把这n个关键字映射到Hash表中需要做n(n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表,至少要进行n(n+1)/2次探测

Hash查找效率:装填因子=表中记录数/表容量

  推荐站点

  • At-lib分类目录At-lib分类目录

    At-lib网站分类目录汇集全国所有高质量网站,是中国权威的中文网站分类目录,给站长提供免费网址目录提交收录和推荐最新最全的优秀网站大全是名站导航之家

    www.at-lib.cn
  • 中国链接目录中国链接目录

    中国链接目录简称链接目录,是收录优秀网站和淘宝网店的网站分类目录,为您提供优质的网址导航服务,也是网店进行收录推广,站长免费推广网站、加快百度收录、增加友情链接和网站外链的平台。

    www.cnlink.org
  • 35目录网35目录网

    35目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向35目录推荐、提交优秀网站。

    www.35mulu.com
  • 就要爱网站目录就要爱网站目录

    就要爱网站目录,按主题和类别列出网站。所有提交的网站都经过人工审查,确保质量和无垃圾邮件的结果。

    www.912219.com
  • 伍佰目录伍佰目录

    伍佰网站目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向伍佰目录推荐、提交优秀网站。

    www.wbwb.net