- 1、本文档共48页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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)