哈希表是一种高效的数据结构本文分五个部分首先提出Word文件下载.docx

1、，然后将这个元素存储在相应类所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了冲突，换句话说，就是把不同的元素分在了相同的之中。后面我们将看到一种解决的简便做法。总的来说，直接定址与解决冲突是哈希表的两大特点。 函数构造构造函数的常用方法（下面为了叙述简洁，设 （） 表示关键字为 的元素所对应的函数值）：） 除余法：选择一个适当的正整数 ，令 （ ） 这里， 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。） 数字选择法：如果关键字的位数比较多，超过长整型范围而无法直接运算，可

2、以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。 冲突处理线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 ，则当 （） 已经存储了元素的时候，依次探查 （） , ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 支持运算哈希表支持的运算主要有：初始化（）、哈希函数值的运算（）、插入元素（）、查找元素（）。设插入的元素的关键字为 ， 为存储的数组。初始化比较容易，例如 ; 用非常大的整数代表这个位置没有存储元素; 表的大小 ; ;哈希函数值的运算根据函数的不同而

3、变化，例如除余法的一个例子： （）; ;我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 （）; （）（） ） （）;当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元素存储的单元，要么表已经满了（） ;插入元素 定位函数的返回值 ; 即为发生了错误，当然这是可以避免的查找元素是否已经在表中 ;这些就是建立在哈希表上的常用基本运算。下文提到的所有程序都能在附录中找到。. 效率对比 简单的例子与实验 下面是一个比较简单的例子：集合 （ ） 问题描述： 给定两个集合、，集合内的任一元素满足 ，并且每个集合的元素个数不大于

4、个。我们希望求出、之间的关系。只需确定在 中但是不在 中的元素的个数即可。（这个题目是根据 模拟赛 的第一题改编的。分析： 我们先不管 与 的具体关系如何，注意到这个问题的本质就是对于给定的集合 ，确定 中的元素是否在 中。所以，我们使用哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了原题的数据规模， （） ; 当然本题可以利用别的方法解决，所以选取了速度最快的快速排序二分查找，让这两种方法作效率对比。 我们假定 ，对于随机生成的数据，计算程序重复运行次所用时间。 对比表格如下：哈希表（） 快速排序二分查找（） 复杂度 （） （只有忽略了冲突才是这个结果。当然实际情况会比这个大

5、，但是重复的几率与哈希函数有关，不容易估计） （ ） （ ） 测试数据规模 对于数据的说明： 在 下用 测试，为了使时间的差距明显，让程序重复运了行次。同时哈希表中的 ，下标范围 。由于快速排序不稳定，因此使用了随机数据。 对实验结果的分析： 注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设哈希表的大小为 . 首先，当规模比较小的时候（大约为 ，因为 运算本身与快速排序的比较大小和交换元素运算相比，比较费时间。所以规模小的时候，（）（忽略冲突）的算法反而不如 （）。这一点在更复杂的哈希函数上会体现的更明显，因为更复杂的函数系数会更大。 其次，当规模稍大 （大约为 * *） 的时候，很

6、明显哈希表的效率高。这是因为冲突的次数较少。 再次，当规模再大 （大约为 * ，即有 * , *, 则有 * * . 其中 的取值范围是不会超过 ， 的正整数。也就是说， 的值只有 种可能，而 是一个预先确定的数。因此 式的值就只有 种可能了。这样，虽然 运算之后的余数仍然在 ， 内，但是它的取值仅限于 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出， 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住素数是我们的得力助手 另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，

7、这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。 综上所述，设计一个好的哈希函数是很关键的。而好的标准，就是较低的冲突率和易于实现。 另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。 这些只是一般原则，真正遇到试卷的时候实际情况千变万化，需要具体问题具体分析才行。下面，我们看几个例子，看看这些原则是如何体现的。 有关字符串的例子 我们经常会遇到处理字符串的

8、问题，下面我们来看这个例子：找名字 问题描述： 给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编写密码，编写的方式是对于 位字符串，给定一个 位数，大写字母与数字的对应方式按照电话键盘的方式： : : : 题目给出一个 位的数，找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过 。（这个是 的一道题。分析： 看懂题目之后，对于给定的编码，只需要一个回溯的过程，所有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在给定的字典中了。所以这个问题需要的还是由于给出的姓名都是字符串，因此我们可以利用字符的 码。那么，如何设计这个哈希函数呢？注意

9、到题目给出的字典中，最多能有 个不同元素，而一个字符的 码只能有 种不同的取值，因此至少需要用在个位置上的字符（ ，但是 *（）; *（）; 取第一位和后两位 *（）;当长度为的时候特殊处理 值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似平均，但是对于大多数情况，字符串是有规律的（例如英文单词），这个时候用哈希表反而不好（例如英语中有很多以 开头的单词），通常用检索树解决这样的查找问题。 在广度优先搜索中应用的例子 在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。来看下面的例子：转花盆 题意描述:

10、 给定两个正边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过种，对于任意两种花，数量多的花的盆数至少是数量少的花的倍 。（这是 的一道题） 首先确定本题可以用广度优先搜索处理，然后来看问题的规模。正边形共有个格子可以用来放花，而且根据最后一句限定条件，至多只能存在 （） * （） 种状态，用搜索完全可行。然而操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。那么这个哈希函数如何设计呢？注意到个格

11、子组成边形是有顺序的，而且每一个格子只有种可能情况，那么用进制位数最大 用 完全可以承受。于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。 小结 从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法，但是每个字符都有天生的 码，在设计哈希函数的时候可以直接利用。而其他方法，例如利用检索树的查找，编写代码不如哈希表简洁。至于广度优先搜索中的判重更是直接利用了哈希表的特点。 另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面的基本操作就可以了，因此重点应该是在哈希函数的设计上（尽管这两个例子的设计都很简单），需要注意题目本身可以利用的条件，以及估计值域的范围。下面我们看两个需要在哈希表基础上作一些变化的例子。