Hash函数及其应用and程序对拍问题.pptx

  1. 1、本文档共48页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Hash函数及其应用and程序对拍问题概要1

Hash函数及其应用 and 程序对拍问题;Hash函数及其应用;做这个课件之前又看了一遍去年在郑州学习时大民子(ZQM,不认识的不解释,想了解的找度娘,求照片的看左光胜)讲的课件,朱老师做的比较全面,但有些地方解释得不是很详细,初学起来可能有些困难,本课件引用了朱老师很多内容,在网上又找了一些资料加以扩充,同学们课下可以看一下朱老师的原版课件。 Orz ZQM;问题一;out.txt YES YES NO;分析;什么是HASH? 哈希表是一种高效的数据结构 。 散列方法是使用函数h将U映射到表T[0..m-1]的下标上(m=O(|U|))。这样以U中关键字为自变量,以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。 ;哈希表最大的优点: 把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。;整数HASH;一、直接定址法 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a ? key + b 此法仅适合于: 地址集合的大小 = 关键字集合的大小 ;示例:有一组关键码如下: { 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 }。散列函数为 Hash (key) = key - 940000 有Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按计算出的地址存放记录。 由于直接定址所得地址集合和关键字集合的大小相同。因此,对于不同的关键字不会发生冲突。 但实际中能使用这种哈希函数的情况很少。 ;整数的Hash函数 构造方法(2) 2.直接取余法 关键字k除以m,取余数作为在Hash表中的位置。函数表达式可以写成: H(key) = key MOD p 其中, p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子;为什么要对 p 加限制? ;整数的Hash函数 构造方法(3) 3.乘积取整法 关键字k乘以一个在(0,1)中的实数(最好是无理数),得到一个(0,1)之间的实数;取出其小数部分,乘以m,再取整数部分,即得K在Hash表中的位置。函数表达式可以写成: 例如 就是一个好的选择。 ;整数的Hash函数 构造方法(4) 4.平方取中法 把关键字K平方,然后取中间的 位作为Hash函数值返回。由于K的每一位都会对其平方中间的若干位产生影响,因此这个方法的效果也是不错的。但是对于比较小的K值效果并不是很理想,实现起来也比较繁琐。为了充分利用Hash表的空间,M最好取2的整数次幂。例如,表容量M=24=16,,关键值K=100,那么 h(k)=8 理由:因为中间几位与数据的每一位都相关 例:2589的平方值为6702921,可以取中间的029为地址 ;const maxn=10000; var i,m,n:longint; a,p:array[0..maxn] of longint; function hash(x:longint):longint; begin hash:=x mod 3; end; procedure push(x:longint); var i,j,k:longint; begin k:=hash(x); while (a[k]x)and(a[k]0) do begin inc(k); if k=maxn then k:=0; end; a[k]:=x; inc(p[k]); end; begin fillchar(a,sizeof(a),0); fillchar(p,sizeof(p),0); push(2);push(5);push(5);push(55); push(69);push(99);push(99);push(99); for i:=0 to 20 do writel

文档评论(0)

yaocen + 关注
实名认证
内容提供者

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

1亿VIP精品文档

相关文档