散列法的课程设计说明书

《散列法的课程设计说明书》由会员分享，可在线阅读，更多相关《散列法的课程设计说明书（25页珍藏版）》请在金锄头文库上搜索。

1、中北大学数 据 结 构课 程 设 计 说 明 书学生姓名: 淮华瑞学 号：1021010908学 院:软件学院专 业:软件工程题 目:散列表的实验研究指导教师康珺2011年12月20日1. 设计任务概述（包括系统总体框图及功能描述）建立散列表系统总体框图二次探测再散列线性探测再散列链地址法链地址法查找二次探测再散列查找线性探测再散列查找问题描述 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。概要设计 散列又称哈希或杂凑。散列法（Hashing）在

2、表项的存储位置与它的关键码之间建立一个确定的对应函数关系Hash（），以使每个关键码与结构中的唯一存储位置相对应，该关系可用下式表示：Address=Hash（Record.key）相应的表称为哈希表，这种方法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。 哈希函数是一个映象，哈希函数的设定灵活，只要使得任何关键字所得的哈希函数值都落在表长范围之内即可。

3、当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1k2，但H(k1)=H(k2)，这种现象称为冲突，此时称k1和k2为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。 综上所述，哈希法主要包括以下两方面的内容。 (1）如何构造哈希函数； (2） 如何处理冲突。2. 本设计所采用的数据结构（如：链表、栈、树、图等）一、散列函数 通常，构造散列函数应该注意的几个问题包括：首先，散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在1m-1之间;其次，散列函数计算出来的地址应能均匀分布在整个地址空间中；再次，散列函数

4、应当是尽量简单的。1直接定址法 直接定址法蓝颜元素关键码的某个线性函数值作为该元素的散列地址（散列地址，即元素最终在字典中的存储位置）。如下面的函数式：Hash（key）=akey+b式中，a，b为常数。采用该种方法，当向字典中加入某一新元素时算法自动调用此函数，以确定该元素最终的存储位置。若某元素关键码key为1，上式中，a=2，b=3则该元素最终会存储在字典第5个位置中。 直接定址法的优点是实现方法简单，算法时间复杂度较小，而且不会产生冲突。但是，直接定址法要求散列地址空间的大小与关键码集合的大小一致，而这种要求是苛刻的，一般很难实现。例如当关键码的范围为11000000时，元素散列地址的

5、个数也要达到1000000。这么大的散列地址是不合实际的。2.除留余数法 设散列表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数k，或选取一个不含有小于20的质因子的合数作为除数。利用下面的式子计算元素的散列地址的方法称为除留余数法。Hash（key）=key%k，km其中，“%”是整数除余法取余的运算，要求这时的质数不是接近2的幂。例如，当元素的关键码key为2008，散列地址总数为50，这时取k=47，则散列地址为Hash（2008）=2008%47=34，所以运算将存储在字典第47个位置中。 除留余数法将有效缩减散列地址空间的大小，例如上例散列地址空间中只有50个有效的散列地

6、址。除留余数法的缺点是极易发生冲突，如关键码为1914的元素经过上述教例函数计算后也将获得散列地址34。此时出现的两个不同元素争用同一存储地址的情况就称为冲突。3.平方取中法 平方取中法是一种常用的实现散列函数的方法。 平方取中法是一种先放大再集合的构造方法，这种构造模式先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值，这种取中间数的方法是一种类随机方案，因此也可以认为平方取中法是一种产生伪随机数的方法。因为一个乘积的中间几位数和乘数的每一位都相关，所以有此产生的散列地址较为均匀。 利用平方取中法实现散列函数的过程：首先，利用一定的编码规则把元素的关键码转换成

7、标识符。然后，求出标识符的内码表示并计算内码的平方值。最后，取内码平方数的中间x位作为元素最终的散列地址。简而言之，即先计算构成关键码表示符的内码平方，然后按照散列表的大小取中间的若干位作为散列地址。 在平方取中法中，地址空间内散列地址的数目一般为2的k次幂，并在计算出内码平方的平方后，根据k的大小决定最终散列地址的位数。例如某个地址空间中散列地址的个数为128，则最终取内码平方中间7位作为元素最终的散列地址。4.乘余取整法 乘余取整法利用下面的式子计算元素的散列地址。Hash（key）=Z（akey%1） 其中，a为一个常数且0a1，Z为一个整数。式akey%1表示akey取小数部分，即ak

8、ey%1= akey- akey 。例如，当元素关键码为2008， 小数a为0.6180339，整数Z为10000，则散列地址计算为Hash（2008）=10000（0.61803392008%1）=120。 乘余取整法不但会缩减散列地址空间的大小，还能极大减小冲突情况的发生几率。Knuth对常数a的取法做了仔细的研究，发现虽然a取任何值都可以，但一般取黄金分割数0.6180339比较好。5.折叠法折叠法的工作方式很有趣，此方法把关键吗从左至右划分为位数相等的几部分，每一部分的位数与散列地址数相同。当关键码位数不能被散列地址位数整除时，最后一部分可取得短些。 折叠法有两种，即位移法和分界法。

9、其中，位移法所采取的具体方式是把各部分的最后一位对齐相加。分界法所采用的具体方式是各部分不折断，而沿各部分的分界来回折叠，然后对齐相加，并将相加的结果当做散列地址。折叠法适用于关键码位数很多，且每一位上数字分布比较均匀的情况。下面通过实例演示这两种方法的工作方式。 设关键码key=987654321，散列地址为4位。位移法和分界法计算散列地址的算式如图所示。9876 98765432 2345 + 1 + 1 15309 12222 移位法 分界法由式可见，位移法计算结果为15309，由于散列地址为4位，所以舍去最高位数字1，元素最终的散列地址为5309。分界法结算结果为12222，同样舍去最

10、高位数字1，元素最终的散列地址为2222。二、散列冲突解决方法在构造散列函数的过程中，不可避免地会出现冲突的情况。所谓处理冲突，就是在有冲突发生时，为产生冲突的关键字找到另一个地址存放该关键字。在解决冲突的过程中，可能会得到一系列散列地址hi（i=1,2，n),也就是发生第一冲突时，经过处理后得到第一新地址记作h1，如果h1仍然会冲突，则处理后得到第二个地址h2，依此类推，直到hn不产生冲突，将hn作为关键字的储存地址。处理冲突的方法比较常用的主要有开放定址法、再散列法和链地址法。1. 开放定址法开放定址法是解决冲突比较常用的方法。开放定址法就是利用散列表中的空地址存储产生冲突的关键字。当冲突

11、发生时，按照下列公式处理冲突：hi=（h（key）+di）%m，其中i=1,2，m-1其中，h（key）为散列函数，m为散列表长，di为地址增量。地址增量di可以以下三种方法获得：（1） 线性探测再散列：当冲突发生时，地址增量di依次取1,2，m-1自然数列，即di=1,2，m-1。（2） 二次探测再散列：在冲突发生时，地址增量di依次取自然数的平方，即di=12，12,22，22，k2，k2。（3） 伪随机数再散列：在冲突发生时，地址增量di依次取随机数序列。例如，在长度为14的散列表中，在将关键字183,123,230,91存放在散列表中的情况如图所示。Hash地址 0 1 2 3 4 5

12、 6 7 8 9 10 11 12 13 18312323091散列表冲突发生前示意图当要插入关键字149时，有散列函数h（149）=149%13=6，而单元6已经存在关键字，产生冲突，利用线性探测再散列法解决冲突，即h1=（6+1）%14=7，将149储存在单元7中，如图所示。Hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18312314923091插入关键字149后的示意图当要插入关键字227时，由散列函数h（227）=227%13=6，而单元6已经存在关键字，产生冲突，利用线性探测再散列法解决冲突，即h1=（6+1）%14=7，仍然冲突，继续利用线性探测法

13、，即h2=（6+2）%14=8，单元8空闲，因此将227存储在单元8中，如图所示。Hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18312314922723091插入关键字227后的示意图当然，在冲突发生时，也可以利用二次探测再散列解决冲突。在图11.33中，如果要插入关键字227，因为产生冲突，利用二次探测再散列法解决冲突，即h1=（6+1）%14=7，再次产生冲突时，有h2=（61）%14=5，将227储存在单元5中，如图所示。Hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18322712314923091利用二次探测再散列解决冲突示意图2. 再散列法再散列法就是在冲突发生时，利用另外一个散列函数再次求散列函数的地址，直到冲突不再发生为止，即hi=rehash（key），i=1,2，n其中，rehash表示不同的散列函数。这种再散列法一般不容易再次发生冲突，但是需要事先构造多个散列函数，这是一件不太容易的也不现实的事情。3. 链地址法 数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法链地址法