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

1、Hash函数及其应用 and 程序对拍问题,By:LOI_50 Xiao 9*,Hash函数及其应用,做这个课件之前又看了一遍去年在郑州学习时大民子(ZQM,不认识的不解释，想了解的找度娘，求照片的看左光胜)讲的课件，朱老师做的比较全面，但有些地方解释得不是很详细，初学起来可能有些困难，本课件引用了朱老师很多内容，在网上又找了一些资料加以扩充，同学们课下可以看一下朱老师的原版课件。 Orz ZQM,问题一,读入n个正整数，每个数小于109 查询某个数是否在这n个数中出现 一共查询m次 n=100000 m=100000,out.txt YES YES NO,in.txt 5 - 5个数 8 1

2、 6 3 5 3 - 询问3次 3 6 9,分析,这题可以先对n个数进行快速排序，然后对于每次询问，用二分查找解决。 有没有更快的做法？,HASH！,什么是HASH？ 哈希表是一种高效的数据结构 。 散列方法是使用函数h将U映射到表T0.m-1的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。,哈希表最大的优点： 把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。,

3、整数HASH,一、直接定址法 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b 此法仅适合于： 地址集合的大小 = 关键字集合的大小,整数的Hash函数构造方法（1）,示例：有一组关键码如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 。散列函数为 Hash (key) = key - 940000 有Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630

4、 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按计算出的地址存放记录。 由于直接定址所得地址集合和关键字集合的大小相同。因此，对于不同的关键字不会发生冲突。 但实际中能使用这种哈希函数的情况很少。,整数的Hash函数 构造方法（2） 2直接取余法 关键字k除以m，取余数作为在Hash表中的位置。函数表达式可以写成： H(key) = key MOD p 其中， pm (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子,为什么要对 p 加限制？,给定一

5、组关键字为: 12, 39, 18, 24, 33, 21， 若取 p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3 可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。,整数的Hash函数 构造方法（3） 3乘积取整法 关键字k乘以一个在(0,1)中的实数（最好是无理数），得到一个(0,1)之间的实数；取出其小数部分，乘以m，再取整数部分，即得K在Hash表中的位置。函数表达式可以写成： 例如 就是一个好的选择。,整数的Hash函数 构造方法（4） 4平方取中法 把关键字K平方，然后取中间的 位作为Ha

6、sh函数值返回。由于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:array0.maxn of longint; function hash(x:longint):longint; begin hash:=x

7、mod 3; end; procedure push(x:longint); var i,j,k:longint; begin k:=hash(x); while (akx)and(ak0) do begin inc(k); if k=maxn then k:=0; end; ak:=x; inc(pk); 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 2

8、0 do writeln(ai, ,pi); end.,Example,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。,字符串HASH,问题二,问题一中的正整数改成字符串 （每个字符串的长度不超过20） 还是输入n个字符串，一共m次询问,in.txt 4 - 5个字符串 Orz OrzWhybert OrzTim OrzZQM 3 - 询问3次 OrzWhybert Tim Sacaleesiyon,out.txt YES NO NO,字符串本身就可以看成一个256进制（ANSI字符串为128进制）的大

9、整数，因此我们可以利用直接取余法（例如：mod 35111，3111757)，在线性时间内直接算出Hash函数值。 为了保证效果，仍然不能选择太接近2n的数；尤其是当我们把字符串看成一个2p进制数的时候，选择m= 2p -1会使得该字符串的任意一个排列的Hash函数值都相同。,常用字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，对其进行了一个小小的评测。,其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3

10、为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。 经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。,几种常用的字符串Hash代码,ELF Hash Function 黑书推荐的Hash函数 （黑书此处的注释：这是一个很有用的Hash函数，

11、他对长短字符串都很有效， 推荐大家把它作为字符串的Hash函数）黑书P97 function ELFHash(s1:string):dword;vari:integer;x:dword;beginELFHash:=0;x:=0;for i:=1 to length(s1) dobegin ELFHash:=(ELFHash shl 4)+ord(s1i); x:=ELFHash and $F0000000; /x = hash ,BKDR Hash Function function BKDRHash(s1:string):dword; /qword used;var i:integer; s

12、eed:dword; hash:qword; begin seed:=131; / 31 131 1313 13131 131313 etc. hash:=0;for i:=1 to length(s1) do hash:=(hash*seed+ord(s1i) and $FFFFFFFF; BKDRHash:=hash and $7FFFFFFF;end;,AP Hash Function function APHash(s1:string):dword;var i:integer;begin APHash:=0; for i:=1 to length(s1) do if i and 1=1

13、 then APHash:=APHash xor (APHash shl 7) xor ord(s1i) xor (APHash shr 3) else APHash:=APHash xor (not (APHash shl 11) xor ord(s1i) xor (APHash shr 5);APHash:=APHash and $7FFFFFFF; end;,Hash函数的冲突,冲突 两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。 安全避免冲突的条件 最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：其一是|

14、U|m其二是选择合适的散列函数。这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。 影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关。 设m和n分别表示表长和表中填人的结点数，则将=n/m定义为散列表的装填因子(Load Factor)。越大，表越满，冲突的机会也越大。通常取1。,解决冲突 我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。我们这里主要讲一种： 开放定址法 （闭散列法）,开放定址法的一般形式为：hi=(h(key)+di)m 1im-1其中： h(key)为散

15、列函数，di为增量序列，m为表长。 h(key)是初始的探查位置，后续的探查位置依次是hl，h2，hm-1，即h(key)，hl，h2，hm-1形成了一个探查序列。 若令开放地址一般形式的i从0开始，并令d0=0，则h0=h(key)，则有： hi=(h(key)+di)m 0im-1 探查序列可简记为hi(0im-1)。,如果di值可能为1,2,3,.m-1，称线性探测再散列。 如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,.k*k,-k*k(k=m/2)称二次探测再散列。 如果di取值可能为伪随机数列。称伪随机探测再散列。,例：在长度为11的哈希表中已填有关键字分

16、别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下：,线性探查方法比较容易实现，但它存在着一个问题，称作一次群集。随着时间的推移，连续被占用的槽被不断增加，平均查找时间也随着不断增加。群集现象很容易出现，这是因为当一个空槽前有i的满的槽时，该空槽为下一个将被占用的槽的概率是（i+1)/m。连续被占用的槽的序列将会变得越来越长，因而平均查找时间也会随之增加。,其它解决冲突的方法： 1.再哈希法 当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。 2.链地址法 将所有关键字为同义词的记录存储在同一线性链表

17、中。 3.建立一个公共溢出区 假设哈希函数的值域为0,m-1,则设向量HashTable0.m-1为基本表，另外设立存储空间向量OverTable0.v用以存储发生冲突的记录。,推荐题目 POJ 1200 Crazy Search （Rabin-Karp） POJ 1635 Subway tree systems （树同构） POJ 1971 Parallelogram Counting （统计平行四边形） POJ 2002 Squares （统计正方形） POJ 3504 Obfuscation （忽略顺序的字符串hash） POJ 1690 (Your)(Term)(Project) (公

18、式Hash） POJ 2549 Sumsets 参考文献： 朱全民老师PPTHASH函数及其应用 算法导论算法艺术与信息学竞赛 网上各大牛相关资料,OI考试中的程序对拍 (Windows系统),一做都会，样例很对，评测不A。 本来可能很简单的题目因为一点点疏忽拿了很少的分，或者一些较复杂的题目经不正确的优化后导致部分答案错误，此时的样例不是试验用而变成了坑爹用。我们可能多多少少都有过这样的情况，那怎样避免这种前况的发生？相信各位大牛都会回答：“多试几组数据不就完了”。是的，道理不假，但是手动测试的速度实在不敢恭维，特别是在NOIP这种分秒必争的考试中此种方法就显得更加无力了。 就这个问题我特别

19、请教了周昕宇（Tim）神牛，他讲了一种程序对拍结果的方法。在NOI2010中周神犇用此种方法对拍了20+W组数据，可能正是凭借此种方法砍下了NOI2010夏令营第一和NOIP2010 400分，实践证明此种方法效果确实不错，所以在这里拿出来和大家分享一下。,OI考试的时候 你是不是经常有这样的苦恼：,因为NOIP山东赛区目前的比赛用系统为Windows XP，所以这里只介绍一下在Windows环境下的程序对拍方法。据Tim介绍在Linux下的更为复杂精密，这里就不作详细介绍了，有兴趣可以自己了解一下。,下面进入正题,1.新建一个记事本文件，在其中贴入以下代码： :loop echo %* |

20、datamaker.exe prog.in prog.exe prog.out prog_right.exe prog.ans fc prog.out prog.ans if errorlevel=1 goto end goto loop :end,代码解释：,:loop echo %* | datamaker.exe prog.in/用datamaker生成数据并加入prog.in prog.exe prog.out/执行优化后的程序prog读入数据，输出结果prog.out prog_right.exe prog.ans/执行未优化的程序prog_right，输出结果prog.ans fc prog.out prog.ans/对比两个程序结果是否相同 if errorlevel=1 goto end/如果不同停止执行 goto loop/如果相同继续执行 :end,2.将此文件重命名并把扩展名改为 .bat,3.建立datamaker并生成datamaker可执行文件,以a+b为例：,4.prog.pas与prog_right.pas