HASH GAME - Online Skill Game GET 300

　　哈希表概念及构建方法 一、哈希表的概念及作用 一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。 哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０ 号学生的记录位置在第１０条... 如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？ a b c d e f g h i j k l m n o p q r s t u v w x y z 1 1 1 1 1 1 1 1 1 1 2 2 2 2 1 2 3 4 5 6 7 8 9 24 25 26 0 1 2 3 4 5 6 7 8 9 0 1 2 3 姓名中各字拼音首字母 用所有首字母编号值相加求 刘丽 ll 刘宏英 lhy 吴军 wj 吴小艳 wxy 李秋梅 lqm 陈伟 cw ... ... 24 46 33 72 42 26 ... 和 最小值可能为3 最大值可能为78 可放75个学生 用上述得到的数值作为对应记录在表中的位置，得到下表： 成绩一 成绩二... 3 ... ... ... 24 刘丽 82 95 25 ... 26 陈伟 ... ... 33 吴军 ... ... 42 李秋梅 ... ... 46 刘宏英 ... ... 72 吴小艳 ... ... 78 ... 上面这张表即哈希表。 如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置： 李秋梅:lqm 12+17+13=42 取表中第42条记录即可。 问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？ 这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。二、哈希表的构造方法 １、直接定址法 例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。 地址 01 02 ... 25 26 27 ... 100 年龄 1 2 ... 25 26 27 ... ... 人数 ... 3000 2000 ... 1050 ... ... ... ... ２、数字分析法 有学生的生日数据如下： 年.月.日 75.10.03 75.11.23 76.03.02 76.07.12 75.04.21 76.02.15 ... 经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。 ３、平方取中法 取关键字平方后的中间几位为哈希地址。４、折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。 例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则： 5864 4220 5864 0224 +) 04 +) 04 10088 H(key)=0088 移位叠加 6092 H(key)=6092 间界叠加 ５、除留余数法 取关键字被某个不大于哈希表表长m 的数p 除后所得余数为哈希地址。 H(key)=key MOD p (p=m) ６、随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key)=random(key) ,其中 random 为随机函数。通常用于关键字长度不等时采用此法 哈希表及其查找算法 哈希表的基本概念 前边我们所讨论的查找算法中无论是基于线性表结构还是基于二叉排序树结构，都有一个共 同的特点就是在搜索过程中，需要通过对给定关键字与查找表中相应元素的关键字进行比较 来实现，且都采用平均查找长度作为衡量算法好坏的指标，而一个算法的平均查找长度与关 键字的比较次数有着密切的关系，换句话说，就是算法的优劣将取决于关键字的比较次数。由此，我们引入一种想法即是否可以寻求一种不必进行关键字比较而达到查找目的的方法 呢？如果可以，则这样的平均查找长度将为零。哈希表给我们实现这样的想法提供了可能。哈希表是一种数据元素以散列方式组织的存储结构，在一块连续的存储空间中采用哈希法建 立起来的符号表称为哈希表，其基本思想是：元素的存储位置与它的关键字间建立一个确定 的对应关系，即设关键字 key 与存储位置间的对应关系为 H(key)，若用一维数组来存放数据元素，则 H(key)就表示该数组的下标。这样我们就可以称函数 H 为哈希（Hash）函数， H(key)为哈希地址，该一维数组就是哈希表。 显而易见，哈希表一旦建立，在这样的存储结构上进行查找时，可以用给定的关键字和建立哈希表时所采用的哈希函数直接在给定的哈希表中进行查找。值得注意的是：由于数据元素序列中的各数据元素的关键字的取值可能会在一个很大的范围内，因而即使待查找的数据元素序列中的元素个数不是很多，也很难选取一个合适的哈希函数H，以确保不同key 值的数据元素有不同的函数值。这里我们把具有不同 key 值的数据元素，得到相同哈希函数值的现象称为冲突。在大多数情况下，哈希函数是一种“压缩映象”，即把关键字取值范围很大的数据元素集合映射到一个范围确定的表中，因此，冲突是在所难免的。尽管如此，我们还是希望尽可能找到产生均匀映射的哈希函数，以有效地降低冲突发生率；此外，在发生冲突时也必须有相应的解决冲突的办法。因此，构造哈希表的两大任务就是：建立哈希函数和找到解决冲突的办法。 哈希函数的构造方法 哈希函数的构造方法很多，通常根据实际需要，遵循使关键字通过哈希函数转换所得到的地址尽可能地均匀分布在给定空间中的原则。因此，如何构造一个“好”的哈希函数就是带有很强的技术性和实践性的问题。这里，我们分别介绍几种常用的构造哈希函数的方法。 1．直接定址法 当关键字是整型数时，可以取关键字本身或它的线性函数作为它的哈希地址。即： H(key)=key 或者： H(key)=a ? key + b （其中a、b 都是常数） 直接定址法的特点是函数简单，且对于不同的关键字不会发生冲突。但现实问题中，数据元素的关键字很少是连续的，因此，采用该方法可能会造成哈希表空间的浪费。 2．数字分析法 这种方法适合于静态数据，即所有的关键字值都能够事先知道，然后检查分析关键字值中所有的数字，分析每一数字是否分布均匀，并将不均匀的数字删除，再根据存储空间的大小确定构造哈希函数。 例12.3 设有如下8个学生的学号为： 2002 42 2341 2002 82 3587 2002 23 7184 2002 36 9293 2002 52 1682 2002 76 5434 2002 18 3689 2002 60 4289 观察这一组数据发现，左边的第1、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) = 392 H(key5) = 516 H(key6) = 754 H(key7) = 136 H(key8) = 642 3．平方取中法 该方法是先计算出关键字key 的平方值即key2，然后取平方值中间的若干位作为哈希地址， 即： H(key) = key2的之间几位 这是一种常用的较好的构造哈希函数的办法。关键字经过求平方后，其中间的几位和组成关 键字的各位值均有关，从而使哈希地址的分布较为均匀，减少了发生冲突的可能性。 除了上述三种方法外，还有一些较为常用的方法如：除留余数法，折叠移位法等等。总而言之，构造哈希函数的方法可以多种多样，但以哈希地址分布均匀为优。 冲突解决的方法 如前所述，在实际应用中，无论如何构造哈希函数，冲突是无法完全避免的。为了解决冲突， 就需要为不同关键字值得到相同地址中的某一个或某几个数据元素寻找另外的存储地址，下 面介绍两种解决冲突的办法。 开放地址法 这个方法的基本思想是：当发生地址冲突时，按照某