Hash表的构建和冲突解决

1、哈希表概念及构建方法、哈希表的概念及作用一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在 比较 的基础上，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。哈希表最常见的例子是 以学生学号为关键字 的成绩表，1号学生的记录位置在第一条，10号学生的记录位置在第1。条 .如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录

2、呢？abcdefghij11 234567890姓名中各字拼音首字母用所有首字母编号值相加求和最小值可能为3最大值可能为klm no1111112345刘丽刘宏英lllhy244678可放75个学生pqrstu111122678901吴军 吴小艳wjwxy3372v w xyz2224252623李秋梅陈伟.lqmcw.4226.用上述得到的数值作为对应记录在表中的位置，得到下表:成绩一 成绩二.3.24 刘丽 829525 .26 陈伟.33吴军.42李秋梅.46刘宏英.72吴小艳78.上面这张表即哈希表。如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：李秋梅:lqm 12+17

3、+13=42取表中第42条记录即可。问题：如果两个同学分别叫刘丽 刘兰 该如何处理这两条记录？这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。二、哈希表的构造方法1、直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字 自身。地址0102.252627.100年龄12.252627.人数30002000.1050.2、数字分析法有学生的生日数据如下：年.月.日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15.经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加

4、，所以尽量不取前三位，取后三位比较好。3、平方取中法取关键字平方后的中间几位为哈希地址。4、折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为 0-442-20586-4, 贝U:+)5864422004+)5864022404100886092H(key)=0088H(key)=6092(a)移位叠加(b)间界叠加5、除留

5、余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p (p<=m) 6、随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random 为随机函数。通常用于关键字长度不等时采用此法哈希表及其查找算法12.4 . 1哈希表的基本概念前边我们所讨论的查找算法中无论是基于线性表结构还是基于二叉排序树结构，都有一个共同的特点就是在搜索过程中，需要通过对给定关键字与查找表中相应元素的关键字进行比较来实现，且都采用平均查找长度作为衡量算法好坏的指标，而一个算法的平均查找长度与关键字的比较次数有着密

6、切的关系，换句话说，就是算法的优劣将取决于关键字的比较次数。由此，我们引入一种想法即是否可以寻求一种不必进行关键字比较而达到查找目的的方法 呢？如果可以，则这样的平均查找长度将为零。哈希表给我们实现这样的想法提供了可能。哈希表是一种数据元素以散列方式组织的存储结构，在一块连续的存储空间中采用哈希法建立起来的符号表称为哈希表，其基本思想是：元素的存储位置与它的关键字间建立一个确定 的对应关系，即设关键字key与存储位置间的对应关系为H(key),若用一维数组来存放数据元素，则H(key)就表示该数组的下标。这样我们就可以称函数H为哈希(Hash)函数，H(key)为哈希地址，该一维数组就是哈希表

7、。显而易见，哈希表一旦建立， 在这样的存储结构上进行查找时，可以用给定的关键字和建立哈希表时所采用的哈希函数直接在给定的哈希表中进行查找。值得注意的是：由于数据元素序列中的各数据元素的关键字的取值可能会在一个很大的范围内，因而即使待查找的数据元素序列中的元素个数不是很多，也很难选取一个合适的哈希函数H,以确保不同key值的数据元素有不同的函数值。 这里我们把具有不同key值的数据元素，得到相同哈希函数值的现 象称为冲突。在大多数情况下，哈希函数是一种“压缩映象”，即把关键字取值范围很大的数据元素集合映射到一个范围确定的表中，因此，冲突是在所难免的。尽管如此，我们还是希望尽可能找到产生均匀映射的

8、哈希函数，以有效地降低冲突发生率；此外，在发生冲突时也必须有相应的解决冲突的办法。因此，构造哈希表的两大任务就是：建立哈希函数和找到解决冲突的办法。12.4 . 2哈希函数的构造方法哈希函数的构造方法很多，通常根据实际需要，遵循使关键字通过哈希函数转换所得到的地址尽可能地均匀分布在给定空间中的原则。因此，如何构造一个“好” 的哈希函数就是带有 很强的技术性和实践性的问题。这里，我们分别介绍几种常用的构造哈希函数的方法。1. 直接定址法当关键字是整型数时，可以取关键字本身或它的线性函数作为它的哈希地址。即：H(key)=key或者：H(key)=a ? key + b (其中a、b都是常数)直接

9、定址法的特点是函数简单，且对于不同的关键字不会发生冲突。但现实问题中，数据元素的关键字很少是连续的，因此，采用该方法可能会造成哈希表空间的浪费。2. 数字分析法这种方法适合于静态数据，即所有的关键字值都能够事先知道，然后检查分析关键字值中所有的数字，分析每一数字是否分布均匀， 并将不均匀的数字删除， 再根据存储空间的大小确 定构造哈希函数。例12.3设有如下8个学生的学号为：2002 42 23412002 82 35872002 23 71842002 36 92932002 52 16822002 76 54342002 18 36892002 60 4289观察这一组数据发现，左边的第1

10、、2、3、4位的数值不太均匀，因此删除；第9位中数值8出现次数太多，因此也删除；第 6位中数值2出现三次，6出现两次，因此也删除；第8位中数值2出现2次，假设哈希表长度为1000,因此可以选择第5、7、8位组成哈希地址：得到如下 结果：H(key1) = 423 H(key2) = 835 H(key3) = 271 H(key4) = 392H(key5) = 516 H(key6) = 754 H(key7) = 136 H(key8) = 6423. 平方取中法该方法是先计算出关键字key的平方值即key2 ,然后取平方值中间的若干位作为哈希地址，即：H(key) = key2 的之间几

11、位这是一种常用的较好的构造哈希函数的办法。关键字经过求平方后，其中间的几位和组成关 键字的各位值均有关，从而使哈希地址的分布较为均匀，减少了发生冲突的可能性。除了上述三种方法外，还有一些较为常用的方法如：除留余数法，折叠移位法等等。总而言之，构造哈希函数的方法可以多种多样，但以哈希地址分布均匀为优。12.4 . 3冲突解决的方法如前所述，在实际应用中，无论如何构造哈希函数，冲突是无法完全避免的。为了解决冲突，就需要为不同关键字值得到相同地址中的某一个或某几个数据元素寻找另外的存储地址，下面介绍两种解决冲突的办法。1. 开放地址法这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表

12、中的其他存储单元，直到找到空位置为止。这个过程可用下式描述：Hi(key) = (H(key)+di ) mod m (i = 1,2, , k(k < m - 1)其中：H(key)为关键字key的直接哈希地址，m为哈希表的长度，di为每次再探测时的地址 增量。采用这种方法时，首先计算出元素的直接哈希地址H(key),如果该存储单元已被其他元素占用，则继续查看地址为 H(key) + d2的存储单元，如此重复直至找到某个存储单元为空时，将关键字为key的数据元素存放到该单元。增量d可以有不同的取法，并根据其取法有不同的称呼：(1) di = 1 , 2, 3,线性探测再散列；(2) d

13、i = 12 , 12, 22, - 22,二次探测再散列；(3) di =伪随机序列 伪随机再散列；例12.4设有哈希函数 H(key) = key mod 7,哈希表的地址空间为 06,对关键字序列(32,13, 49, 55, 22, 38, 21)按线性探测再散列和二次探测再散列的方法分别构造哈希表。解：(1)线性探测再散列：32% 7 = 4;13% 7 = 6;49% 7 = 0;55 % 7 = 6 发生冲突，下一个存储地址(6 + 1) % 7 = 0 ,仍然发生冲突，再下一个存储地址：(6+ 2) % 7 = 1未发生冲突，可以存入。22 % 7 = 1发生冲突，下一个存储地

14、址是：(1 + 1) % 7 = 2未发生冲突；38 % 7 = 3 ;21 % 7 = 0发生冲突，按照上面方法继续探测直至空间5,不发生冲突，所得到的哈希表对应存储位置：下标：0 1 2 3 4 5 649 55 22 38 32 21 13(2)二次探测再散列：下标：0 1 2 3 4 5 649 22 21 38 32 55 13注意：对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎，不能直接地删除，因为这样将会截断其他具有相同哈希地址的元素的查找地址，所以，通常采用设定一个特殊的标志以示该元素已被删除。2. 链地址法链地址法解决冲突的做法是：如果哈希表空间为0m?1,

15、设置一个由m个指针分量组成的一 维数组STm,凡哈希地址为i的数据元素都插入到头指针为 STi的链表中。这种方法有点 近似于邻接表的基本思想，且这种方法适合于冲突比较严重的情况。例12.5设有8个元素 a,b,c,d,e,f,g,h ,采用某种哈希函数得到的地址分别为：(0 , 2, 4,1, 0, 8,乙2,当哈希表长度为10时，采用链地址法解决冲突的哈希表如图12.4所示。图12 4链地址法示意图12.4 . 4哈希查找哈希查找，顾名思义就是基于哈希表结构的查找算法，其基本思想是，按照建立哈希表时的哈希函数，根据给定关键字值， 直接求出其哈希地址，若该地址中数据元素为空，则查找失如果败；如果该地址中数据元素不为空，且其关键字值与给定关键字值相等，则查找成功;该地址中数据元素不为空，但其关键字值不等于给定关键字值，则需按照