《哈希表的论文》由会员分享，可在线阅读，更多相关《哈希表的论文（13页珍藏版）》请在金锄头文库上搜索。
1、 哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈希表的优点，其次介绍了它的基础操作，接着从简单的例子中作了效率对比，指出其适用范围以及特点，然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题，最后总结全文。 正文正文 1.1. 引言引言哈希表（Hash Table）的应用近两年才在 NOI 中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。哈希
2、表又叫做散列表，分为“开散列“ 和“闭散列“。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表“仅指“闭散列“，关于其他方面读者可参阅其他书籍。2.2. 基础操作基础操作2.12.1 基本原理基本原理我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类“，然后将这个元素存储在相应“类“所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这
3、样就产生了“冲突“，换句话说，就是把不同的元素分在了相同的“类“之中。后面我们将看到一种解决“冲突“的简便做法。总的来说，“直接定址“与“解决冲突“是哈希表的两大特点。2.22.2 函数构造函数构造构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：a)a) 除余法：除余法：选择一个适当的正整数 p ，令 h(k ) = k mod p 这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。b)b) 数字选择法：数字选择法：如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，
4、所组成的新的值作为关键字或者直接作为函数值。2.32.3 冲突处理冲突处理线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3 ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。2.42.4 支持运算支持运算哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x)、插入元素(insert)、查找元素(member)。设插入的元素的关键字为 x ，A 为存储的数组。初始化比较容
5、易，例如const empty=maxlongint; / 用非常大的整数代表这个位置没有存储元素p=9997; / 表的大小procedure makenull;var i:integer;beginfor i:=0 to p-1 doAi:=empty;End;哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：function h(x:longint):Integer;beginh:= x mod p;end;我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate function locate(x:lon
6、gint):integer;var orig,i:integer;beginorig:=h(x);i:=0;while (ix)and(A(orig+i)mod S 5000，但是 262 1 then begin tmp:=tmp*27+ord(s1)-64; for i:=1 downto 0 do tmp:=tmp*27+ord(slength(s)-i)-64; 取第一位和后两位 end else for i:=1 to 3 do tmp:=tmp*27+ord(s1)-64;当长度为 1 的时候 特殊处理 hash:=tmp mod 13883; end; 值得指出的是，本题给出的字
7、符串大都没有什么规律，用哈希表可以做到 近似“平均“，但是对于大多数情况，字符串是有规律的（例如英文单词），这 个时候用哈希表反而不好（例如英语中有很多以 con 开头的单词），通常用检 索树解决这样的查找问题。 4.34.3 在广度优先搜索中应用的例子在广度优先搜索中应用的例子 在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先判重。 而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。来看下面的 例子： 转花盆转花盆 题意描述题意描述: : 给定两个正 6 边形的花坛，要求求出从第一个变化到第二个的最小操 作次数以及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的
8、 6 盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放 的不同种类的花不超过 3 种，对于任意两种花，数量多的花的盆数至少是数量 少的花的 2 倍 。（这是 SGOI-8 的一道题） 分析：分析： 首先确定本题可以用广度优先搜索处理，然后来看问题的规模。正 6 边 形共有 19 个格子可以用来放花，而且根据最后一句限定条件，至多只能存在 C(2,19) * C(5,17) = 1058148 种状态，用搜索完全可行。然而操作的时候， 可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解， 因此想到了哈希表。那么这个哈希函数如何设计呢？注意到 19 个格子组成 6
9、 边 形是有顺序的，而且每一个格子只有 3 种可能情况，那么用 3 进制 19 位数最大 320-1=3486784400 用 Cardinal 完全可以承受。于是我们将每一个状态与一 个整数对应起来，使用除余法就可以了。 4.44.4 小结小结 从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法， 但是每个字符都有“天生“的 ASCII 码，在设计哈希函数的时候可以直接利用。 而其他方法，例如利用检索树的查找，编写代码不如哈希表简洁。至于广度优 先搜索中的判重更是直接利用了哈希表的特点。 另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面的基 本操作就可以了，因此重点
10、应该是在哈希函数的设计上（尽管这两个例子的设 计都很简单），需要注意题目本身可以利用的条件，以及估计值域的范围。下 面我们看两个需要在哈希表基础上作一些变化的例子。 4.54.5 需要微小变化的例子需要微小变化的例子 下面，我们来分析一道 NOI 的试题： 方程的解数方程的解数 问题描述问题描述 已知一个 n 元高次方程： 其中： 是未知数， 是系数， 是指数。且 方程中的所有数均为整数。 假设未知数 1 M, i=1,n，求这个方程的整数解的个数。 约束条件约束条件 1n6；1M150； 方程的整数解的个数小于 。 本题中，指数 Pi(i=1,2,n)均为正整数。 这个是 NOI 2001
11、的第二试中的方程的解数。 分析：分析： 初看此题，题目要求出给定的方程解的个数，这个方程在最坏的情况 下可以有 6 个未知数，而且次数由输入决定。这样就不能利用数学方法直接求 出解的个数，而且注意到解的范围最多 150 个数，因此恐怕只能使用枚举法了。 最简单的思路是穷举所有未知数的取值，这样时间复杂度是 O(M6) ，无法承 受。因此我们需要寻找更好的方法，自然想到能否缩小枚举的范围呢？但是发 现这样也有很大的困难。我们再次注意到 M 的范围，若想不超时，似乎算法的 复杂度上限应该是 O(M3) 左右，这是因为 1503 0)and(ea,(t+i)mod p,1rc)or(ea,(t+i)
12、mod p,3rd) then inc(i); 线性重新散列 locate:=(t+i)mod p; end; 但是后来发现完全没有必要这样做，这样的哈希函数在计算 t 的时候浪费 了很多时间（不过数据规模不是很大，所以这点不十分明显），而且素数起到 的作用也不应当是这样的。其实让 rb,rc,rd 组成 n 进制数就完全能够 达到目的了，加入了素数不仅是小规模数据计算浪费时间，对大数据最后结果 的分布平均也没有起到比 n 进制数更多的作用。因此改为 t:=rb*sqr(n)+rc*n+rd; 当然肯定会有更好的哈希函数的。 4.74.7 小结小结 第一个例子，乍一看与哈希表毫无关系；第二个例子叙述比较复杂，但是 经过仔细分析，发现问题的本质都是确定“某个元素是否在给定集合中“，这正 是哈希表的特点。所以，不论题目的表面看起来如何，只要本质是需要高效的 数据检索，哈希表通常就是最好的选择！ 另外，这两个例子都在原来哈希表的基础上作了一些变化。第一个例子加 入了纪录某个值出现次数的域，第二个例子加入了纪录所有墙的情况以及原节 点编号的域。虽然都只是很小的变化，但是却给问题的解决带来了不小的方便。 因此我们得到提示：哈希表虽然有标准的操作，但也不是一成不变的，需要具 体问题具体分析，根据题目的要求和特点作出相应变化。
