算法设计与分析结课论文

1、算法设计与分析结课论文Hash技术 学生姓名：胡项南 学 号：1130090050 专 业：计算机科学与技术年 级：2009级完成日期：2010年 月 日 指导教师：刘洋 成 绩：Hash技术摘要：随着科技日益发展，Hash函数的重要性越来越突出。本文介绍了几种构造Hash的方法，例如直接定址法、数字分析法、平方取中法、折叠法、除留余数法等，在构造Hash函数时，应当注意两点问题：（1）函数值应在1至记录总数之间。（2）尽量避免冲突。还介绍了几种处理Hash算法冲突的方法。除此之外，阐明了Hash函数的优缺点和它在现实生活中的应用。关键词：Hash函数，构造方法，应用，优缺点目录1. 绪论 1

2、.1 什么是算法 1.2 搜索算法2. Hash函数 2.1 Hash函数的基本概念 2.2 Hash函数的基本思想与一般模型 2.3 Hash函数的构造3. 处理冲突的方法 3.1 开放定址法 3.2 再哈希法 3.3 链地址法 3.4 建立一个公共溢出区4. Hash算法的优劣分析 5. Hash函数的应用 5.1 完整性的验证 5.2 数字签名 5.3 认证协议 5.4 加密算法6. 总结1. 绪论1. 1 什么是算法 算法的概念在计算机科学与技术领域几乎无处不在，在各种计算机系统的实现中，算法的设计往往处于核心的位置。1.2 搜索算法搜索问题是计算机技术面对的基本课题之一，自20世纪7

3、0年代以来，计算机应用的主流逐渐从计算机密集型向着数据密集型转化，计算机存储和处理的数据量越来越大，结构越来越复杂，因此，对搜索算法的研究始终是人们研究的重要领域。搜索算法与其他问题不同，它与数据结合的组织形式密切相关。在大多数情况下，搜索算法实际上是作为某种数据类型的运算或操作而不断的被调用的，搜索算法的优劣与数据结构密切相关。2. Hash函数2.1 Hash函数的基本概念Hash函数是把任意长度的二进制串映射到特定长度的二进制串函数，是最基本的二进制函数之一。Hash函数也被称为“凑数函数”，但这个名称很少被采用，70年代之前也被称为散列函数，现在我们经常将其称之为Hash或译为哈什。H

4、ash技术是一种提供高速数据存储与检索方式的优秀技术，已有近50年的发展历史。其中二十世纪五六十年代因汇编与编译系统的需要，Hash技术受到普遍重视，70年代以来，计算机在数据管理与人工智能领域广泛应用，大型数据库系统的设计备受关注。由于Hash算法的期望搜索时间与数据集合的大小无关，所以在数据量很大时，其查询性能优于平衡树等搜索算法。2.2 Hash算法的基本思想与一般模型 随着对Hash函数的不断探索，子啊上世纪九十年代Hash函数逐渐趋于成熟。Hash函数逐渐有了两个分支。一个分支就是针对大规模字符串词典，这就是我们常见的词典。另一个分支就是针对大规模稀疏整数集合，就是将一个大规模整数集

5、合的所有元素映射到一个较小集合。 Hash方法的基本思想是，首先产生从可能的关键字集合（又称全域）U=0.N-1到存储空间（Hash表）地址集合T=0.m-1的一个映射函数：h:U0.m-1。于是，要存储或检索关键字为xU的数据项只需计算函数h(x)，直接得到该数据项应在的地址。 然而对不同的关键字x,yU，h(x)=h(y)的情况可能出现，这种情形称为冲突（collision）。由于一般的|U|远远大于m，冲突难以避免，因此Hash技术研究的基本问题是： (1)设计一个好的Hash函数，计算简单，而又使数据项分布均匀以减少冲突；(2)设计解决冲突的策略和算法。集合SU为实际存于Hash表中的

6、关键字组合。|S|=nN。=n/m称为负载因子（load factor），值是决定哈希算法性能的主要因素。其值小于1，且越小越浪费空间，越接近1性能越下降。Hash算法的“散列”存储方式，使得它不能支持Minimum、Maximum、Successor、Predecessor这类的操作，而对于Search、Insert、Delete操作，不但可以支持而且有较高的性能。从抽象数据类型（ADT）的观点来说，Hash算法用于实现字典（Dictionary）类型，实际关键字集合S为固定不变时，称为静态字典，只支持Search操作，S为可变时，即动态数据集，称为动态字典，动态字典支持搜索、插入和删除操作

7、。2.3 Hash函数的构造Hash函数的设计一般应能兼顾计算简单和分布均匀，在大多数应用问题中，可能的关键字集合U往往远远大于地址空间的规模。例如以姓名字符串作为关键字，|U|=N是一个极大的值，而Hash表的长度m和实际关键字集合S（|S|=n）与N相比小得多。因此，分布均匀的要求就是要对于h:U(0,m-1)，SU，|S|=n，使尽量小，其中|.|集合的势（求集合元素的个数），h(-i)为被h映射至地址i的关键字全体。当且仅当=n时达到最小值，意味着将无任何冲突产生。无冲突的Hash函数称为完备Hash函数（Perfect Hash Function），简称PHF。事实上，无冲突的要求是

8、极难达到的。“生日悖论”指出，在23个人中，有两个人的生日在同一天的概率为0.51，即当|S|=n=23，m=365时，发生冲突的概率已经在50%以上。而当n=50时，发生冲突的概率已达0.97。在D.Knuth所举的实例中指出，当n=31，m=41时，无冲突的映射函数只占全部可能映射函数的1/107。因此，在大多数情形下只能追求将冲突尽可能减少。下面介绍几种常见的Hash函数的构造方法。2.3.1 直接定址法直接定址法使用关键字的线性函数来计算哈希地址。也就是说,直接定址法所用的哈希函数为： H(key)=a×keyb （a、b为常数）例如：表2.1是从1岁到100岁人口统计表，其

9、中年龄为关键字。如果想把这100个记录存放到这些存储单元中，可以定义哈希函数为：若果想把这100个记录存放到这些存储单元中，可以定义Hash 为 H(key)=key-1。 0 1 2 98 99 地址010203252627100年龄123252627人数3000200050001050表2.1直接定址Hash函数例显然，在直接定址法中，不同关键字的哈希地址也不相同，因此不会出现冲突。该方法适合于关键字的分布基本连续的情况。2.3.2 数字分析法 1.数字分析法选用关键字中某些取值较分散的数字位来构成哈希地址。2. 对于长度为m的哈希表，每个存储单元都有一个地址码（即下标），其中最大地址码的

10、数字位数称为该哈希表的地址码位数。 例如，对于长度为100的哈希表，其最大地址码99的位数2称为哈希表的地址码位数。 0 1 2 98 99 在关键字的位数比哈希表的地址码位数大很多时，我们可以对这些关键字进行分析，丢掉一些分布不均匀的位，留下分布均匀的位作为哈希地址。例如：已知表2.2有80个记录，每个记录的关键字是8位数。假设哈希表的长度为100，其地址码位数是2位，可以选择两个分布均匀的位构成每个记录的哈希地址。 0 1 98 99 表2.2 Hash地址表Hash地址458134653272813722428481387422038130136728813228173981338967

11、51813544571381419955 通过对对这80个关键字进行分析，可知第1、2、3、8位太扎堆了，其余4位的分散性还可以。因此，取这4位中的任意两位( 比如、 )作为哈希地址。 总之，数字分析法适合于事先知道可能的关键字，关键字较长且某些位分布较均匀的情况。而这种根据数据分析法构造的Hash函数也可能发生冲突。2.3.3 平方取中法 平方取中法是取关键字平方的中间几位作为哈希地址，具体几位取决于哈希表的地址码位数。 理论依据是：一个数的平方的中间几位与这个数的每一位都相关 。因此，平方取中法所得到的哈希地址与关键字的每一位相关，使得哈希地址具有较好的分散性。例如：已知表2.3中的关键字

12、（八进制）如下，假设哈希表的长度为512。由于512=(1000)8，该哈希表的地址码长度为3，因此，可取中间3位作为每个记录的哈希地址。表2.3关键字（关键字）Hash地址0100001000001011001210000210116013704004402061431054131021634745651745由此可见平方取中法适合于事先不了解关键字的全部情况，或者 关键字较短的情况。下面给出平方取中法的哈希函数：/平方取中法Hash函数，结设关键字值32位的整数/Hash函数将返回*key的中间10位int Hash(int key)/计算key的平方key *=key;/去掉第11位ke

13、y >>=11;/返回第10位（即key*key的中间10位）return key %10242.3.4 折叠法折叠法是按照哈希表的地址码位数，将关键字分割成位数相同的几段（最后一段可能少些），然后将这几部分相加，得到的和即为哈希地址。例如：假设哈希表的地址码位数为3，关键字key为：72320324111220。按照地址码位数，将关键字每3位分段，得到：723 203 241 112 20。然后，将他们叠加。则可得，H(key)=299。 所以折叠法适合于关键字较长，地址码位数较小，同时关键字中每位的取值又较扎堆的情况。2.3.5 除留余数法除留余数法的哈希函数定义为：H(key

14、)=key MOD p（p m ），其中，m为哈希表的长度，p是小于等于m的正整数。例如，对2.4中的关键字，如果取p=29 表2.4key28356377105H(key)28651918如果取p=21，就会出现许多同义词，如表2.5 表2.5key28356377105H(key)7140140经验表明，p应选择为略小于m的素数，或者选择无小于20的素因子的合数。2.3.6 随机乘数法随即乘数法，也称为“乘余取整法”。随机乘数法使用一个随机实数f，0f1，乘积f*k的分数部分在01之间，用这个分数部分的值与n（Hash表的长度）相乘，乘积的整数部分就是对应的Hash值，显然这个Hash值落

15、在0n-1之间。其表达公式为：Hash(k)=n*(f*k%1)其中“f*k%1”表示f*k的小数部分，即f*k%1=f*k-f*k。例如，对下列关键字值集合采用随机乘数法计算Hash值，随机数f=0.1031149002，Hash表长度n=100，可得表2.6 表2.6kf*kn*(f*k)的小数部分)Hash(k)31942632948.4731147.784114771830974092.8564886.504488662944364926.4172742.144274291969784865.8276983.5966983此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=

16、2p.Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329.比较理想。3. 处理冲突的方法 虽然在构造哈希函数时，我们想了多种办法来尽量防止冲突的发生，但是，在许多情况下冲突依然会出现。 所谓处理冲突，就是要为记录Ri找到另一个空闲的哈希地址。在探测过程中，可能得到的新哈希地址H1仍然冲突，则再求下一个新哈希地址H2，直到得到的新哈希地址Hk确实为一个空闲的哈希地址，这时把记录Ri存入，本次冲突处理完毕。3.1 链地址法链地址法的主要思想是将关键字为同义词的记录存放在同一个单链表中。例如：对于查找表16, 19, 9, 33，

17、试利用函数 H(key)=key MOD 7,把它存储到长度m=7的哈希表中，并用链地址法处理冲突。假如要查找K=33的记录，求出H(33)=5，得到同义词链表的头指针，然后顺链表找关键字为33的结点；如果直到链表结尾也未发现，则查找不成功。 3.2 建立公共溢出区 在这种方法中，除了建立有m个分量的基本表外，还会建立有v个分量的溢出表。在存储查找表中的每个记录时，首先根据其关键字求哈希地址,如果基本表中该位置空闲，则把记录存在该分量中；否则，则把记录存储到溢出表中。3.3 再哈希法 在这种方法中，事先预备了一系列哈希函数RH() (1is)。当存储某个记录R发生冲突时，先使用H=RH(key

18、)，若H还冲突，再使用H=RH(key)，直到某个H不再冲突为止。3.4 开放定址法 开放定址法的公式：H=(H(key)+d)MOD m, i=1,2,k (km1)其中，key为发生冲突记录的关键字，H(key)为哈希函数，m为哈希表长度，d为增量序列。根据增量序列d的不同取法，形成了三种不同的处理冲突的方法：（1）线性探测再散列：1, 2, 3, , m-1（2）二次探测再散列：12, -12, 22, -22, , k2, -k2 (km/2)（3）伪随机探测再散列: 随机序列例如：假设哈希表长度 m=12，哈希函数 H(key)=key MOD 11 。把关键字为17、60、29、3

19、8的记录存入哈希表中,前3个记录存入后得到： 0 1 2 3 4 5 6 7 8 9 10 11 60172938由于H(38)=5，于是发生了冲突。（1） 线性探测再散列 此时，增量序列为 1，2，3，m1。 用它处理时，首先得到地址H=(5+1) MOD 12=6，仍然冲突；再求下一个地址H=(5+2) MOD 12=7，仍然冲突；再求下一个地址H=(5+3) MOD 12=8，该地址空闲，于是记录38存入该位置。 可以看出，线性探测再散列是从发生冲突的位置起，顺序向后寻找空位。当哈希表未满时，总能找到一个空位。（2） 二次探测再散列 此时增量序列为 12，-12，22，-22，32，-3

20、2，k2，-k2 用它处理时，首先得到地址H=(5+1) MOD 12=6，仍然冲突；再求下一个地址H=(5-1) MOD 12=4，该地址空闲，记录38存入. 可以看出，二次探测再散列是在发生冲突的位置两侧寻找空位。 （5） 伪随机探测再散列 此时增量序列d为某个伪随机数序列。 用它处理时，对冲突记录的关键字38，依次用公式：H=(H(38)+d)MOD m计算H、H、，直到某个H空闲为止，并将记录存入H位置。4. Hash算法的优劣分析 Hash方法独特的按内容寻址的检索方式是一种高级的“联想”式存储与检索技术。它的期望时间代价为O(1)阶，与数据集规模无关。 不足之处 ：（1）按内容寻址

21、的方式决定了它是把数据“散列”（scattering）到Hash表中，因此它不适用于涉及数据内容之间关系的查询。例如，求最大、最小元，删除最小元，后继，前导，求关键字key值在某一范围内的一组数据等等。 （2）Hash算法的最坏情形时间代价为O(n)阶，使其不能在诸如防空系统、空中交通调度系统等“紧急”系统中采用，因为一旦出现一次最坏情形，会造成重大事故。（3）前文对Hash算法的性能分析过程中，所有的分析结果都是在“实际关键字集合S是全域U的一个随机子集”等条件下得到的。如果全集U中的关键字不是等可能性地出现在Hash表中，这种情况在实际问题中是经常遇到的，例如关键字为程序中的标识符名，有些

22、名称如m、n、m1、m2、m3等等，出现的概率远远多于其它名称，在这种情形下，期望性能可能变差。对此，也有一些方法予以解决，如泛Hash（Universal Hashing）方法。 （4）Hash算法的性能与负载因子的值密切相关。在数据集不断增加时，负载因子逐渐增大，并接近于1，会使系统性能明显下降。 例如=n/m>0.9或>0.95时，扩大Hash区，即所谓空间倍增（array doubling）技术，需要把数据集中的所有数据按照新的Hash函数重新转存入新的Hash区，这一工作代价很大。为解决空间倍增所需的高代价问题，可采用线性扩张Hash算法。基本思想是指定一对负载因子的上限

23、和下限,在可能关键字集合S的大小n改变的过程中，一旦 超过,存储区扩充一个桶（可存放b条数据项），当小于时，存储区缩减一个桶。这样就保证动态数据集上的操作总是在良好的性能下工作。5. Hash函数的应用5.1 完整性的验证 完整性验证：由HASH函数的抗碰撞性，它相当于文件的指纹.完整性验证是指数据未经授权不能进行改变，即信息在存储或传输过程中不被修改的特性。它保证收到的数据是授权实体所发的数据，如果文件的HASH值没有变，我们就可以确定消息没有变化。HASH函数这种性质的应用是非常广泛的。病毒检测中的校验和算法就是通过定期的计算文件的 HASH值并存储，只要HASH值和上次计算的结果相比没有变化，就可以肯定文件没有被病毒感染5.2 数字签名 数字签名：由于其易于计算的特性，HASH函数可以用于数字签名中。在这种签名协议中，双方必须事先协商好双方都支持的HASH函数和签名算法。因为在数字签名中使用公钥算法，公钥算法的缺点是运算速度较慢，先对文件算HASH值，再对HASH值进行签名，这样一是可以提高计算速度，另外也可以更安全。 5.3 认证协议 认证协议：有些协议使用询问应答机制。通信两方分别为A和B，双方共享一个授权口令。通信时，A发送一个随机串发起询问，B对随机串和共享口令这个整体计算HASH值k，把k作为应答发送给A，A也计算随机串和