作业散列法实验研究.docx
课程设计题目1 .具体要求散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。2 .开发环境VC+6.03 .算法设计思想散列又称哈希或杂凑。散列法(HaShiIIg)在表项的存储位置与它的关键码之间建立一个确定的对应函数关系HaSh(),以使每个关键码与结构中的唯一存储位置相对应，该关系可用下式表示：Address=Hash(Record.key)相应的表称为哈希表，这种方法的基本思想是：首先在元素的关键字k和元素的存储位置P之间建立一个对应关系H,使得p=H(k),H称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k),从而达到按关键字直接存取元素的目的。哈希函数是一个映象，哈希函数的设定灵活，只要使得任何关键字所得的哈希函数值都落在表长范围之内即可。当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即k1k2,但H(k1)=H(k2),这种现象称为冲突，此时称k1和k2为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。综上所述，哈希法主要包括以下两方面的内容：(1)如何构造哈希函数；(2)如何处理冲突。4 .数据结构与算法描述一、散列函数通常，构造散列函数应该注意的几个问题包括：首先，散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在1m-1之间;其次，散列函数计算出来的地址应能均匀分布在整个地址空间中；再次，散列函数应当是尽量简单的。(1)直接定址法直接定址法蓝颜元素关键码的某个线性函数值作为该元素的散列地址(散列地址，即元素最终在字典中的存储位置)。如下面的函数式：Hash(key)=a×key+b式中，a,b为常数。采用该种方法，当向字典中加入某一新元素时算法自动调用此函数，以确定该元素最终的存储位置。若某元素关键码key为1,上式中，a=2,b=3则该元素最终会存储在字典第5个位置中。直接定址法的优点是实现方法简单，算法时间复杂度较小，而且不会产生冲突。但是，直接定址法要求散列地址空间的大小与关键码集合的大小一致，而这种要求是苛刻的，一般彳艮难实现。例如当关键码的范围为1I(XXXMX)时，元素散列地址的个数也要达到IOOOOO0。这么大的散列地址是不合实际的。(2)除留余数法设散列表中允许的地址数为m,取一个不大于m,但最接近或等于m的质数K或选取一个不含有小于20的质因子的合数作为除数。利用下面的式子计算元素的散列地址的方法称为除留余数法。Hash(key)=key%k,k<m其中，是整数除余法取余的运算，要求这时的质数不是接丘2的帛。例如，当元素的关键码key为2008,散列地址总数为50,这时取k=47,则散列地址为HaSh(2008)=2008%47=34,所以运算将停储在字典第47个位置中。除留余数法将有效缩减散列地址空间的大小，例如上例散列地址空间中只有50个有效的散列地址。除留余数法的缺点是极易发生冲突，如关键码为1914的元素经过上述教例函数计算后也招获得散列地址34。此时出现的两个不同元素争用同一存储地址的情况就称为冲突。(3)平方取中法平方取中法是一种常用的实现散列函数的方法。平方取中法是一种先放大再集合的构造方法，这种构造模式先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值，这种取中间数的方法是一种类随机方案，因此也可以认为平方取中法是一种产生伪随机数的方法。因为一个乘积的中间几位数和乘数的每一位都相关，所以有此产生的散列地址较为均匀。利用平方取中法实现散列函数的过程：首先，利用一定的编码规则把元素的关键码转换成标识符。然后，求出标识符的内码表示并计算内码的平方值。最后，取内码平方数的中间X位作为元素最终的散列地址。简而言之，即先计算构成关键码表示符的内码平方，然后按照散列表的大小取中间的若干位作为散列地址。在平方取中法中，地址空间内散列地址的数目一般为2的k次席，并在计算出内码平方的平方后，本即居k的大小决定最终散列地址的位数。例如某个地址空间中散列地址的个数为128,则最终取内码平方中间7位作为元素最终的散列地址。(4)乘余取整法乘余取整法利用下面的式子计算元素的散列地址。Hash(key)=Z×(a×key%1)其中，a为一个常数且O<a<1,Z为一个整数。式axkey%1表示axkey取小数部分，即a×key%1=a×key-a×key。例如，当元素关铺码为2008,小数a为0.6180339,整数Z为IOoO0,则散列地址计算为HaSh(2008)=10000×(0.6180339×2008%1)=120o乘余取整法不但会缩减散列地址空间的大小，还能极大减小冲突情况的发生几率。KnUth对锄a的取法做了仔细的研究，发现虽然a取任何值都可以，但一般取黄金分割数06180339匕傲好。(5)折叠法折叠法的工作方式很有趣，此方法把关键吗从左至右划分为位数相等的几部分，每一部分的位数与散列地址数相同。当关键码位数不能被散列地址位数整除时，最后一部分可取得短些。折叠法有两种，即位移法和分界法。其中，位移法所采取的具体方式是把各部分的最后一位对齐相加。分界法所采用的具体方式是各部分不折断，而沿各部分的分界来回折叠，然后对齐相加，并将相加的结果当做散列地址。折叠法适用于关键码位数很多，且每一位上数字分布比较均匀的情况。下面通过实例演示这两种方法的工作方式。设关键码key=987654321,散列地址为4位。位移法和分界法计算散列地址的算式如图所示。9876987654322345+1+11530912222移位法分界法由式可见，位移法计算结果为15309,由于散列地址为4位，所以舍去最高位数字1,元素最终的散列地址为5309o分界法结算结果为12222,同样舍去最高位数字1,元素最终的散列地址为2222。二、散列冲突解决方法在构造散列函数的过程中，不可避免地会出现冲突的情况。所谓处理冲突，就是在有冲突发生时，为产生冲突的关键字找到另一个地址存放该关键字。在解决冲突的过程中，可能会得到一系列散列地址hi(i=1,2,，n),也就是发生第一冲突时，经过处理后得到第一新地址记作h1,如果h1仍然会冲突，则处理后得到第二个地址h2,依此类推，直到hn不产生冲突，将hn作为关键字的储存地址。处理冲突的方法比较常用的主要有开放定址法、再散列法和链地址法。(1)开放定址法开放定址法是解决冲突比较常用的方法。开放定址法就是利用散列表中的空地址存储产生冲突的关键字。当冲突发生时，按照下列公式处理冲突：hi=(h(key)+di)%m,其中i=1,2,.,m-1其中，h(key)为散列函数，m为散列表长，di为地址增量。地址增量di可以以下三种方法获得：线性探测再散列：当冲突发生时，地址增量di依次取12,，m-1自然数列，即di=1,2,.,m-1o二次探测再散列：在冲突发生时，地址增量di依次取自然数的平方，即di=h,12,力22.k2k?o后庙机数哥散加展冲突发生时，地址增量di依次取随机数序列。例如，在长度为14的散列表中，在将关键字183,123,230,91存放在散列表中的情况如图所示。Hash地址01234567891011121318312323091散列表)中突发生前示意图当要插入关键字149时，有散列函数h(149)=149%13=6,而单元6已经存在关键字，产生冲突，利用线性探测再散列法解决冲突，即h1=(6+1)%14=7,W149储存在单元7中，如图所示。HaSh地址01234567891011121318312314923091插入天键字149后的小总图当要插入关键字227时，由散列函数h(227)=227%13=6,而单元6已经存在关键字，产生冲突，利用线性探测再散列法解决冲突，即h1=(6÷1)%14=7,仍然冲突，继续利用线性探测法，即h2=(6+2)%14=8,单元8空闲，因此将227存储在单元8中，如图所示。HaSh地址01234567891011121318312314922723091插入关键字227后的不惹图当然，在冲突发生时，也可以利用二次探测再散列解决冲突。在图11.33中，如果要插入关键字227,因为产生冲突，利用二次探测再散列法解决冲突，即h1=(6÷1)%14=7,再次产生冲突时，有h2=(61)%14=5,将227储存在单元5中，如图所示。Hash地址O1234567891011121318322712314923091利用_次探测在散列解)夬阡突刀意向(2)再散列法再散列法就是在冲突发生时，利用另外一个散列函数再次求散列函数的地址，直到冲突不再发生为止，即hi=rehash(key),i=1,2.,n其中，rehash表示不同的散列函数。这种再散列法一般不容易再次发生冲突，但是需要事先构造多个散列函数，这是一件不太容易的也不现实的事情。(3)链地址法数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法一一链地址法，我们可以理解为'链表的数组”，如图：0TTTTTT而v123496I叶T娥I十一I1|才T337|4r353IJrj目显叶数组，数组的每个成员包括一个指针，指向一个链表的头,当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。三、哈希法性能分析由于冲突的存在，哈希法仍需进行关键字比较，因此仍需用平均查找长度来评价哈希法的查找a蟋希法中影响关键字比较次数的因素有三个：哈希函数、nr处理冲突的方法以及哈希表的装填因子。哈希表的装填因子的定义如下：哈界春中不素个数哈希表的长度 线性探测再散列查找成功时Snc12Ue查找失败时c 伪随机探测再散列、二次探测查找成功时查找失败时 链址法查找成功时S1I1m21查找失败时U111n1212从以上讨论可知：哈希表的平均查找长度是装填因子的函数，而与待散列元素数目无关。因此，无论元素数目n有多大，都能通过调整,使哈希表的平均查找长度较小。5.源代码/*包含头文件*/#inc1ude<std1ib.h>#inc1ude<stdio.h>#inc1ude<ma11oc.h>typedefintKeyType;typedefStrUCt*元素类型定义*/(KeyTypekey;/*关键字*/inthi;
