哈希表是一种高效的数据结构本文分五个部分首先提出Word文件下载.docx
《哈希表是一种高效的数据结构本文分五个部分首先提出Word文件下载.docx》由会员分享，可在线阅读，更多相关《哈希表是一种高效的数据结构本文分五个部分首先提出Word文件下载.docx（10页珍藏版）》请在冰点文库上搜索。
，然后将这个元素存储在相应"
类"
所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"
冲突"
，换句话说，就是把不同的元素分在了相同的"
之中。
后面我们将看到一种解决"
的简便做法。
总的来说，"
直接定址"
与"
解决冲突"
是哈希表的两大特点。
函数构造
构造函数的常用方法（下面为了叙述简洁，设（）表示关键字为的元素所对应的函数值）：
）除余法：
选择一个适当的正整数，令（）
这里，如果选取的是比较大的素数，效果比较好。
而且此法非常容易实现，因此是最常用的方法。
）数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。
冲突处理
线性重新散列技术易于实现且可以较好的达到目的。
令数组元素个数为，则当（）已经存储了元素的时候，依次探查（（））,……，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。
当然这是可以通过扩大数组范围避免的）。
支持运算
哈希表支持的运算主要有：
初始化（）、哈希函数值的运算（（））、插入元素（）、查找元素（）。
设插入的元素的关键字为，为存储的数组。
初始化比较容易，例如
;
用非常大的整数代表这个位置没有存储元素
;
表的大小
;
[];
;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
（）;
;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数
（）;
;
（<
）（[（）]<
>
）
（）;
当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
素存储的单元，要么表已经满了
（）;
插入元素
定位函数的返回值
[][]
;
即为发生了错误，当然这是可以避免的
查找元素是否已经在表中
[]
;
这些就是建立在哈希表上的常用基本运算。
下文提到的所有程序都能在附录中找到。
.效率对比简单的例子与实验
下面是一个比较简单的例子：
集合（）问题描述：
给定两个集合、，集合内的任一元素满足≤≤
，并且每个集合的元素个数不大于
个。
我们希望求出、之间的关系。
只需确定在中但是不在中的元素的个数即可。
（这个题目是根据模拟赛的第一题改编的。
分析：
我们先不管与的具体关系如何，注意到这个问题的本质就是对于给定的集合，确定中的元素是否在中。
所以，我们使用哈希表来处理。
至于哈希函数，只要按照除余法就行了，由于故意扩大了原题的数据规模，（）;
当然本题可以利用别的方法解决，所以选取了速度最快的快速排序二分查找，让这两种方法作效率对比。
我们假定，对于随机生成的数据，计算程序重复运行次所用时间。
对比表格如下：
哈希表（）
快速排序二分查找（）
复杂度
（）（只有忽略了冲突才是这个结果。
当然实际情况会比这个大，但是重复的几率与哈希函数有关，不容易估计）
（）（）
测试数据规模
对于数据的说明：
在下用测试，为了使时间的差距明显，让程序重复运了行次。
同时哈希表中的，下标范围。
由于快速排序不稳定，因此使用了随机数据。
．对实验结果的分析：
注意到两个程序的用时并不像我们期望的那样，总是哈希表快。
设哈希表的大小为.
首先，当规模比较小的时候（大约为<
*，这个数据仅仅是通过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。
这是由于，虽然每次计算哈希函数用（）的时间，但是这个系数比较大。
例如这道题的（），通过与做同样次数的加法相比较，测试发现系数>
，因为运算本身与快速排序的比较大小和交换元素运算相比，比较费时间。
所以规模小的时候，（）（忽略冲突）的算法反而不如（）。
这一点在更复杂的哈希函数上会体现的更明显，因为更复杂的函数系数会更大。
其次，当规模稍大（大约为*<
<
*）的时候，很明显哈希表的效率高。
这是因为冲突的次数较少。
再次，当规模再大（大约为*<
）的时候，哈希表的效率大幅下降。
这是因为冲突的次数大大提高了，为了解决冲突，程序不得不遍历一段都存储了元素的数组空间来寻找空位置。
用白箱测试的方法统计，当规模为的时候，为了找空位置，线性重新散列平均做了次运算；
而当规模为的时候，平均竟然高达次运算，某些数据甚至能达到次。
显然浪费这么多次运算来解决冲突是不合算的，解决这个问题可以扩大表的规模，或者使用"
（尽管它是动态数据结构）。
然而需要指出的是，冲突是不可避免的。
初步结论：
当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现高效的特点，甚至还不如一般算法。
但是如果规模在中央，它高效的特点可以充分体现。
我们可以从图像直观的观察到这一点。
实验表明当元素充满哈希表的的时候，效率就已经开始明显下降。
这就给了我们提示：
如果确定使用哈希表，应该尽量使数组开大（由于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况例外），但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。
通常使它的容量至少是题目最大需求的，效果比较好（这个仅仅是经验，没有严格证明）。
.应用举例应用的简单原则
什么时候适合应用哈希表呢？
如果发现解决这个问题时经常要询问：
"
某个元素是否在已知集合中？
，也就是需要高效的数据存储和查找，则使用哈希表是最好不过的了！
那么，在应用哈希表的过程中，值得注意的是什么呢？
哈希函数的设计很重要。
一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标就是尽力避免冲突。
前面提到，在使用"
除余法"
的时候，（），最好是一个大素数。
这就是为了尽力避免冲突。
为什么呢？
假设，则哈希函数分类的标准实际上就变成了按照末三位数分类，这样最多类，冲突会很多。
一般地说，如果的约数越多，那么冲突的几率就越大。
简单的证明：
假设是一个有较多约数的数，同时在数据中存在满足（）>
，即有*,*,则有*[]*[].①其中[]的取值范围是不会超过[，]的正整数。
也就是说，[]的值只有种可能，而是一个预先确定的数。
因此①式的值就只有种可能了。
这样，虽然运算之后的余数仍然在[，]内，但是它的取值仅限于①可能取到的那些值。
也就是说余数的分布变得不均匀了。
容易看出，的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。
而素数的约数是最少的，因此我们选用大素数。
记住"
素数是我们的得力助手"
另一方面，一味的追求低冲突率也不好。
理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。
然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。
因此，函数还需要易于编码，即易于实现。
综上所述，设计一个好的哈希函数是很关键的。
而"
好"
的标准，就是较低的冲突率和易于实现。
另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。
有的时候，需要按照题目的要求对哈希表的结构作一些改进。
往往一些简单的改进就可以带来巨大的方便。
这些只是一般原则，真正遇到试卷的时候实际情况千变万化，需要具体问题具体分析才行。
下面，我们看几个例子，看看这些原则是如何体现的。
有关字符串的例子
我们经常会遇到处理字符串的问题，下面我们来看这个例子：
找名字问题描述：
给定一个全部由字符串组成的字典，字符串全部由大写字母构成。
其中为每个字符串编写密码，编写的方式是对于位字符串，给定一个位数，大写字母与数字的对应方式按照电话键盘的方式：
:
:
:
题目给出一个位的数，找出在字典中出现且密码是这个数的所有字符串。
字典中字符串的个数不超过。
（这个是的一道题。
分析：
看懂题目之后，对于给定的编码，只需要一个回溯的过程，所有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在给定的字典中了。
所以这个问题需要的还是"
由于给出的"
姓名"
都是字符串，因此我们可以利用字符的码。
那么，如何设计这个哈希函数呢？
注意到题目给出的字典中，最多能有个不同元素，而一个字符的码只能有种不同的取值，因此至少需要用在个位置上的字符（^>
，但是^<
），于是我们就选取个位置上的字符。
由于给定的字符串的长度从都有可能，为了容易实现，选取最开始的个字符，和最末尾的个字符。
让这个字符组成进制的位数，则这个数的值就是这个字符串的编码。
这样哈希函数就设计出来了！
不过，由于可能出现只有位的字符串，在写函数代码的时候需要特殊考虑；
大素数选取。
这个函数是这样的：
;
{用来记录进制数的值}
（）>
*（[]）;
*（[（）]）;
{取第一位和后两位}
*（[]）;
{当长度为的时候特殊处理}
值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似"
平均"
，但是对于大多数情况，字符串是有规律的（例如英文单词），这个时候用哈希表反而不好（例如英语中有很多以开头的单词），通常用检索树解决这样的查找问题。
在广度优先搜索中应用的例子
在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先判重。
而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。
来看下面的例子：
转花盆题意描述:
给定两个正边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。
一次操作是：
选定不在边上的一盆花，将这盆花周围的盆花按照顺时针或者逆时针的顺序依次移动一个单位。
限定一个花坛里摆放的不同种类的花不超过种，对于任意两种花，数量多的花的盆数至少是数量少的花的倍。
（这是的一道题）
首先确定本题可以用广度优先搜索处理，然后来看问题的规模。
正边形共有个格子可以用来放花，而且根据最后一句限定条件，至多只能存在（）*（）种状态，用搜索完全可行。
然而操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。
那么这个哈希函数如何设计呢？
注意到个格子组成边形是有顺序的，而且每一个格子只有种可能情况，那么用进制位数最大^用完全可以承受。
于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。
小结
从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法，但是每个字符都有"
天生"
的码，在设计哈希函数的时候可以直接利用。
而其他方法，例如利用检索树的查找，编写代码不如哈希表简洁。
至于广度优先搜索中的判重更是直接利用了哈希表的特点。
另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面的基本操作就可以了，因此重点应该是在哈希函数的设计上（尽管这两个例子的设计都很简单），需要注意题目本身可以利用的条件，以及估计值域的范围。
下面我们看两个需要在哈希表基础上作一些变化的例子。
升级会员 