哈希表是一种高效数据结构本文分五个部分首先提出.doc

1、哈希表是一种高效数据结构。本文分五个部分首先提出哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈希表的优点，其次 介绍了它的基础操作，接着从简单的例子中作了效率对比，指出其适用范围以及特点， 然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题，最后总结全文。 正文 . 引言哈希表（ ）的应用近两年才在中出现，作为一种高效的数据结构，它正在竞赛中 发挥着越来越重要的作用。哈希表最大的优点， 就是把数据的存储和查找消耗的时间大大降低，几乎可以看成 是常数时间； 而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况 下，用空间换时间的做法是值得的。另外，编码比较容易也是它

2、的特点之一。哈希表又叫做散列表，分为 “开散列” 和”闭散列 “ 。考虑到竞赛时多数人通常避免 使用动态存储结构， 本文中的 “哈希表 “仅指”闭散列 “ ，关于其他方面读者可参阅其他书 籍。. 基础操作 基本原理我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于 是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素 分类 “，然后将这个元素存储在相应 “类”所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对 于不同的元素，却计算出了相同

3、的函数值，这样就产生了” 冲突” ，换句话说，就是把不同的元素分在了相同的 “类” 之中。后面我们将看到一种解决 “冲突”的简便做法。总的来说， “直接定址 “与”解决冲突 “是哈希表的两大特点。函数构造构造函数的常用方法 (下面为了叙述简洁，设 () 表示关键字为 的元素所对应的 函数值)：) 除余法：选择一个适当的正整数 ，令 ( )这里， 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此 是最常用的方法。) 数字选择法：如果关键字的位数比较多， 超过长整型范围而无法直接运算，可以选择其中数字分 布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。冲突处理线性重

4、新散列技术易于实现且可以较好的达到目的。令数组元素个数为 ，则当 () 已经存储了元素的时候，依次探查(),，直到找到空的存储单元为止(或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是 可以通过扩大数组范围避免的)。支持运算哈希表支持的运算主要有：初始化 () 、哈希函数值的运算 () 、插入元素 () 、查找 元素 () 。设插入的元素的关键字为 ， 为存储的数组。初始化比较容易，例如; 用非常大的整数代表这个位置没有存储元素;表的大小;哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：();我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元

5、素若存在，它 应该存储在什么位置，因此加入一个定位的函数();J();J()() )();当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元 素存储的单元，要么表已经满了() ;J插入元素();();定位函数的返回值();定位函数的返回值; 即为发生了错误，当然这是可以避免的查找元素是否已经在表中（）;();这些就是建立在哈希表上的常用基本运算。下文提到的所有程序都能在附录中找到。.效率对比简单的例子与实验下面是一个比较简单的例子：集合（）问题描述：给定两个集合、，集合内的任一元素满足 ，因为 运算本身与快速排 序的比较大小和交换元素运算相比，比较费时间。所以规模小的时候， () (

6、忽略 冲突)的算法反而不如 () 。这一点在更复杂的哈希函数上会体现的更明显，因 为更复杂的函数系数会更大。其次，当规模稍大 (大约为 * ，即有* , *, 则有 * *.其中 的取值范围是不会超过,的正整数。也就是说， 的值只有 种可能，而 是一个 预先确定的数。因此 式的值就只有 种可能了。这样，虽然 运算之后的余 数仍然在,内，但是它的取值仅限于 可能取到的那些值。也就是说余数 的分布变得不均匀了。容易看出， 的约数越多，发生这种余数分布不均匀的情 况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数 记住” 素数是我们的得力助手 “。另一方面，一味的追求低冲突率也不好

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

8、我们看几个例子，看看这些原则是如何体现的。有关字符串的例子我们经常会遇到处理字符串的问题，下面我们来看这个例子：找名字 问题描述：给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编写密码， 编写的方式是对于 位字符串， 给定一个 位数， 大写字母与数字的对应方式按照电话键盘的方式：题目给出一个 位的数，找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过 。（这个是 的一道题。）分析： 看懂题目之后，对于给定的编码，只需要一个回溯的过程，所有可 能的原字符串都可以被列举出来， 剩下的就是检查这个字符串是否在给定的字典 中了。所以这个问题需要的还是 “某

9、个元素是否在已知集合中？ “由于给出的 “姓 名” 都是字符串，因此我们可以利用字符的码。那么，如何设计这个哈希函数呢？注意到题目给出的字典中，最多能有 个不同元素，而一个字符的 码只能 有 种不同的取值，因此至少需要用在个位置上的字符（A ，但是A*();(); 取第一位和后两位 (); 当长度为的时候特殊处理 值得指出的是， 本题给出的字符串大都没有什么规律， 用哈希表可以做到近似”平均” ，但是对于大多数情况，字符串是有规律的(例如英文单词)，这个时候用哈希表反而不好 (例如英语中有很多以 开头的单词) ，通常用检索树解决这样的查找问题。在广度优先搜索中应用的例子在广度优先搜索中， 一个

10、通用而且有效的剪枝就是在拓展节点之前先判重。而判重的本质也是数据的存储与查找， 因此哈希表大有用武之地。来看下面的例子：转花盆 题意描述 :给定两个正边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。一次操作是： 选定不在边上的一盆花， 将这盆花周围的盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过种， 对于任意两种花， 数量多的花的盆数至少是数量少的花的倍(这是 的一道题)分析： 首先确定本题可以用广度优先搜索处理，然后来看问题的规模。正边形 共有个格子可以用来放花，而且根据最后一句限定条件，至多只能存在 () * () 种状态，用搜索

11、完全可行。然而操作的时候， 可以预料产生的重复节点是相当多 的，需要迅速判重才能在限定时间内出解， 因此想到了哈希表。那么这个哈希函 数如何设计呢？注意到个格子组成边形是有顺序的， 而且每一个格子只有种可能情况，那么用进制位数最大A用 完全可以承受。于是我们将每一个状态与 个整数对应起来，使用除余法就可以了。小结从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法， 但是每个字符都有”天生”的 码，在设计哈希函数的时候可以直接利用。而其他 方法，例如利用检索树的查找，编写代码不如哈希表简洁。至于广度优先搜索中 的判重更是直接利用了哈希表的特点。另外，我们看到这两个题目都是设计好哈希

12、函数之后，直接利用前面的基 本操作就可以了，因此重点应该是在哈希函数的设计上(尽管这两个例子的设计 都很简单)，需要注意题目本身可以利用的条件，以及估计值域的范围。下面我 们看两个需要在哈希表基础上作一些变化的例子。需要微小变化的例子下面，我们来分析一道 的试卷：方 程的解数问题描述已知一个元高次方程：+& 花內 +knx/n = 0其中：_-?是未知数，卞险是系数，：忙 n是指数。且方程中的所有数均为整数。假设未知数W甬W,，求这个方程的整数解的个数。约束条件| +陶M約|+忆必齐| )(,() )线性重新散列 线性重新散列 但是后来发现完全没有必要这样做， 这样的哈希函数在计算 的时候浪费了 很多时间(不过数据规模不是很大，所以这点不十分明显)，而且素数起到的作 用也不应当是这样的。其实让 组成 进制数就完全能够达到目的了， 加 入了素数不仅是小规模数据计算浪费时间， 对大数据最后结果的分布平均也没有 起到比 进制数更多的作用。因此改为*()*;当然肯定会有更好的哈希函数的。小结第一个例子，乍一看与哈希表毫无关系；第二个例子叙述比较复杂，但是 经过仔细分析， 发现问题的本质都是确定 “某个元素是否在给定集合中 “，这正是 哈希表的特点。所以，不论题目的表面看起来