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

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