浅谈竞赛中哈希表的应用
浅谈竞赛中哈希表的应用
哈尔滨市第三中学 刘翀
[关键词] 应用 哈希表 数据结构
[摘要]
哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈希表的优点，其次介绍了它的基础操作，接着从简单的例子中作了效率对比，指出其适用范围以及特点，然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题，最后总结全文。
[正文]
1.引言
哈希表（Hash Table）的应用近两年才在NOI中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。
哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
哈希表又叫做散列表，分为“开散列”和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方面读者可参阅其他书籍。
2.基础操作
2.1基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数
（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。
总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。
2.2函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a)除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
b)数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的
值作为关键字或者直接作为函数值。
2.3冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3……，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。
2.4支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ，A 为存储的数组。
初始化比较容易，例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:=x mod p;
end;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i
inc(i);
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
//素存储的单元，要么表已经满了
locate:=(orig+i) mod S;
end;
插入元素
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误，当然这是可以避免的 end;
查找元素是否已经在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
这些就是建立在哈希表上的常用基本运算。
下文提到的所有程序都能在附录中找到。
3.效率对比
3.1简单的例子与实验
下面是一个比较简单的例子：
===================================================================
集合( Subset )
问题描述：
给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤ 109，并且每个集合的元素个数
不大于104个。我们希望求出A、B之间的关系。只需确定在B 中但是不在 A 中的元素的个
数即可。
这个题目是根据OIBH NOIP 2002 模拟赛 # 1 的第一题改编的。
分析：我们先不管A 与 B 的具体关系如何，注意到这个问题的本质就是对于给定的集合A ，确定B 中的元素是否在 A 中。所以，我们使用
哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了
原题的数据规模，H(x) = x mod 15889;
当然本题可以利用别的方法解决，所以选取了速度最快的快速排序+二分查找，让这两种方法作效率对比。
我们假定 |A|=|B| ，对于随机生成的数据，计算程序重复运行50次所用时间。
对比表格如下：
哈希表（sec）快速排序+二分查找(sec)
O(N log N+ N) = O(N log N)
(只有忽略了冲突才是这
复杂度 O(N)
个结果。当然实际情况会比这
个大，但是重复的几率与哈希
函数有关，不容易估计)
测试数据规模————
500 0.957 0.578 1000 1.101 0.825 2500 1.476 1.565 5000 2.145 2.820 7500 2.905 4.203 10000 3.740 5.579 13500 7.775 7.753 15000 27.550 8.673
对于数据的说明：在 Celeron566 下用 TP 测试，为了使时间的差距明显，让程序重复运了行50次。同时哈希表中的P= 15889 ，下标范围 0..15888 。由于快速排序不稳定，因此使用了随机数据。
3．2 对试验结果的分析：
注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设
哈希表的大小为 P .
首先，当规模比较小的时候（大约为a< 10% * P ，这个数据仅仅是通
过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。这是由于，虽然每次计算哈希函数用O(1) 的时间，但是这个系数比较大。例如这道题的 H(x)=x mod 15589 ，通过与做同样次数的加法相比较，测
试发现系数 > 12 ，因为 mod 运算本身与快速排序的比较大小和交换元
素运算相比，比较费时间。所以规模小的时候，O(N)（忽略冲突）的算法
反而不如 O(NlogN)。这一点在更复杂的哈希函数上会体现的更明显，因
为更复杂的函数系数会更大。
其次，当规模稍大 （大约为 15%*P < a < 85%*P ） 的时候，很明显
哈希表的效率高。这是因为冲突的次数较少。
再次，当规模再大 （大约为 90%*P < a < P ）的时候，哈希表的效
率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得
不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统
计，当规模为13500的时候，为了找空位置，线性重新散列平均做了150000 次运算；而当规模为15000 的时候，平均竟然高达2000000 次运算，某
些数据甚至能达到4265833次。显然浪费这么多次运算来解决冲突是不合
算的，解决这个问题可以扩大表的规模，或者使用“开散列”（尽管它是
动态数据结构）。然而需要指出的是，冲突是不可避免的。
初步结论：
当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现
高效的特点，甚至还不如一般算法。但是如果规模在中央，它高效的特点
可以充分体现。我们可以从图像直观的观察到这一点。
时间效率 数据规模
试验表明当元素充满哈希表的 90% 的时候，效率就已经开始明显下
降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大（由
于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况
例外），但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。
通常使它的容量至少是题目最大需求的 120% ，效果比较好（这个仅仅是
经验，没有严格证明）。
4.应用举例
4.1 应用的简单原则
什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问：“某个元素是否在已知集合中？”，也就是需要高效的数据存储和查找，
则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意
的是什么呢？
哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因
此我们的目标就是尽力避免冲突。前面提到，在使用“除余法”的时候，
h(k)=k mod p ，p 最好是一个大素数。这就是为了尽力避免冲突。为什么
呢？假设 p=1000 ，则哈希函数分类的标准实际上就变成了按照末三位数
分类，这样最多1000类，冲突会很多。一般地说，如果 p 的约数越多，
那么冲突的几率就越大。
简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(p,q)=d >1 ，即有p=a*d , q=b*d, 则有q mod p= q – p* [q div p]
=q – p*[b div a] . ①其中[b div a ] 的取值范围是不会超过 [0，b] 的正整
数。也就是说， [b div a] 的值只有 b+1 种可能，而 p 是一个预先确定
的数。因此①式的值就只有 b+1 种可能了。这样，虽然mod 运算之后
的余数仍然在 [0，p-1] 内，但是它的取值仅限于①可能取到的那些值。
也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这
种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最
少的，因此我们选用大素数。记住“素数是我们的得力助手”。
另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样
的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设
计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数
还需要易于编码，即易于实现。
综上所述，设计一个好的哈希函数是很关键的。而“好”的标准，就是较低的冲突率和易于实现。
另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往一
些简单的改进就可以带来巨大的方便。
这些只是一般原则，真正遇到试题的时候实际情况千变万化，需要具体问题具体分析才行。下面，我们看几个例子，看看这些原则是如何体现
的。
4.2有关字符串的例子
我们经常会遇到处理字符串的问题，下面我们来看这个例子：
====================================================================== 找名字
问题描述：
给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编写密码，编写的方式是对于 n 位字符串，给定一个 n 位数，大写字母与数字的对应方式按照电话键盘的方式：
2: A,B,C 5: J,K,L 8: T,U,V
3: D,E,F 6: M,N,O 9: W,X,Y
4: G,H,I 7: P,R,S
题目给出一个1——12 位的数，找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过 8000 。
这个是USACO Training Gate 1.2.4 的一道题。
分析：看懂题目之后，对于给定的编码，只需要一个回溯的过程，所有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在
给定的字典中了。所以这个问题需要的还是“某个元素是否在已知集合
中？”由于给出的“姓名”都是字符串，因此我们可以利用字符的 ASCII 码。那么，如何设计这个哈希函数呢？注意到题目给出的字典中，最多能
有5000 个不同元素，而一个字符的 ASCII 码只能有26 种不同的取值，
因此至少需要用在3个位置上的字符（26^3 > 5000，但是26^2 < 5000 ），于是我们就选取3个位置上的字符。由于给定的字符串的长度从1——12
都有可能，为了容易实现，选取最开始的1个字符，和最末尾的2个字符。
让这3个字符组成27进制的3位数，则这个数的值就是这个字符串的编
码。这样哈希函数就设计出来了！
不过，由于可能出现只有1位的字符串，在写函数代码的时候需要特殊考虑；大素数选取 13883 。
这个函数是这样的：
function hash(s:string):integer;
var i,tmp:longint;
begin
tmp:=0; {用来记录27进制数的值}
if length(s)>1 then begin
tmp:=tmp*27+ord(s[1])-64;
for i:=1 downto 0 do
tmp:=tmp*27+ord(s[length(s)-i])-64; {取第一位和后两位}
end
else for i:=1 to 3 do
tmp:=tmp*27+ord(s[1])-64;{当长度为1的时候特殊处理} hash:=tmp mod 13883;
end;
值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似“平均”，但是对于大多数情况，字符串是有规律的（例如英文单词），这个时候用哈希表反而不好（例如英语中有很多以 con 开头的单词），通常用检索树解决这样的查找问题。
4.3在广度优先搜索中应用的例子
在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。
来看下面的例子：
转花盆
题意描述:
给定两个正6边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的6盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过3种，对于任意两种花，数量多的花的盆数至少是数量少的花的2倍
这是 SGOI-8 的一道题
分析：首先确定本题可以用广度优先搜索处理，然后来看问题的规模。
正6边形共有19个格子可以用来放花，而且根据最后一句限定条件，至多只能存在C(2,19) * C(5,17) = 1058148 种状态，用搜索完全可行。然而操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。那么这个哈希函数如何设计呢？注意到19个格子组成6边形是有顺序的，而且每一个格子只有3种可能情况，那么用3进制19位数最大 3^20-1=3486784400 用 Cardinal 完全可以承受。于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。
4.4小结
从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法，但是每个字符都有“天生”的 ASCII 码，在设计哈希函数的时候可以直接利用。而其他方法，例如利用检索树的查找，编写代码不如哈希表简洁。至于广度优先搜索中的判重更是直接利用了哈希表的特点。
另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面的基本操作就可以了，因此重点应该是在哈希函数的设计上（尽管这两个例子的设计都很简单），需要注意题目本身可以利用的条件，以及估计值域的范围。下面我们看两个需要在哈希表基础上作一些变化的例子。
4.5需要微小变化的例子
下面，我们来分析一道 NOI 的试题：
======================================================================= 方程的解数
问题描述
已知一个n 元高次方程：
121122......0n p p p n n k x k x k x +++=
其中：x 1, x 2, …,x n 是未知数，k 1,k 2,…,k n 是系数，p 1,p 2,…p n 是指数。且方程中的所有数均为整数。
假设未知数1≤ x i ≤M, i=1,,,n ，求这个方程的整数解的个数。
约束条件
1≤n ≤6；1≤M ≤150；
123112......2n p p p n k M k M k M +++<
方程的整数解的个数小于231。
本题中，指数Pi(i=1,2,……,n)均为正整数。
这个是 NOI 2001 的第二试中的《方程的解数》。
分析：初看此题，题目要求出给定的方程解的个数，这个方程在最坏
的情况下可以有6个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且注意到解的范围最多150个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样时间复杂度是 O(M^6) ，无法承受。因此我们需要寻找更好的方法，自然想到能否缩小枚举的范围呢？但是发现这样也有很大的困难。我们再次注意到M 的范围，若想不超时，似乎算法的复杂度上限应该是 O(M^3) 左右，这是因为 150^3 < 10000000 。这就启示我们能否仅仅通过枚举3个未知数的值来找到答案呢？如果这样，前一半式子的值 S 可以确定，这时只要枚举后3 个数的值，检查他们的和是否等于 -S 即可。这样只相当于在 O(M^3) 前面加了一个系数，当然还需要预先算出 1 到 150 的各个幂次的值。想到了这里，问题就是如何迅速的找到某个 S 是否曾经出现过，以及出现过了多少次，于是又变成了“某个元素是否在给定集合中”这个问题。所以，我们还是使用哈希表解决这个问题。至于哈希函数不是问题，还是把 S 的值作为关键字使用除余法即可。然而有一点需要注意，这个例子我们不仅需要纪录某个 S 是否出现，出现的次数也很重要，所以可以用一个2维数组，仅仅是加了一个存储出现次数的域而已。
Var
e:array[0..max-1,1..2]of longint; {e[x,1] 记录哈希函数值为 x 的 S 值， e[x,2]
记录这个 S 值出现了几次}
因此 insert 过程也需要一些变化：
procedure ins(x:longint);
var posi:longint;
begin
posi:=locate(x);
e[posi,1]:=x;
inc(e[posi,2]); {仅仅这一条语句，就可以记录下来 S 出现了几次}
end;
4.6最后一个例子
下面我们来仔细分析下面这个问题：
迷宫的墙
题意描述:
神话中byte山边有一个井之迷宫。迷宫的入口在山顶。迷宫中有许多房间，每个的颜色是以下之一：红、绿、蓝。两个相同颜色的房间看起来相似而不可区分。每个房间里有三口井标以1,2,3。从一个房间到另一间只有一种方式：从上面房间的井里跳到（不一定竖直地）井底的房间。可以从入口房间到达任何其他房间。迷宫中的所有通路走向坐落在最底部的龙宫。所有的迷宫之旅对应了一系列在相继访问的房间里选择的井的标号。这一列数称为一个旅行计划。一个走过好几次迷宫的英雄bytezar画好了图，然而有的房间重复出现了多次。
输入：
第一行有一个整数n,2<=n<=6000，房间数（包括龙宫）。房间从１到n标号，较大编号的房间再较低处（入口房间编号１，龙宫编号n）。接下的n-1行描述迷宫的房间（除了龙宫）和井。每行有一个字母，一个空格，和三个由空格分隔的整数。字母代表了房间的颜色（C——红，Z——绿，N——蓝），第i(i=1,2,3)个数是第i个井通往的房间号。
输出：
迷宫最少的房间数目
这是 IOI 2003 中国国家集训队难题讨论活动的 0020 题。
分析：题目的意思是给出这个迷宫的地图，去掉重复出现的房间，找出这个迷宫的最少房间数目。于是关键就是确定什么样的房间是重复的。
通过对样例的分析，可以看出这样的房间是重复的：如果两个房间 i 和 j （1<=i,j <=n-1），他们的颜色相同，而且第 k (k=1,2,3) 堵墙通向的房间或者相同、或者重复。因为这样从 i 和 j 可到达的房间是完全相同的。
所以，我们只需要记录下每个房间的情况和已经被确定相同的房间，然后挨个比较即可。于是又需要用到高效的数据存储与查找，自然想到哈希表。然而，这里面需要对哈希表作更大的改进：首先每个房间只能是3种颜色之一，因此针对每种颜色分别建立哈希表，可以使哈希函数的自变量减少一个；其次还需要纪录每个不重复的房间每堵墙都通向哪个房间，还有哪些房间是重复的。
具体这样实现：
var
e:array[0..2,0..p-1,1..4]of longint; {0..2 代表共有3种颜色，0..p-1 是哈希函数的值域，而 1..4 中的 1..3 表示三堵墙连接到那个房间，4 表示这个单元存储的是哪个节点}
r:array[1..maxn]of longint; {r[i] 表示与 i 相同的节点。如果有多个节点都是相同的，择取其中最大的（这一点不需要特殊的操作，只要在处理节点的时候注意就行了）}
至于哈希函数，最开始我是随意的写了一个（因为越是随意的，就越是随机的！），定位函数是这样的：
function locate(var a,b,c,d:longint):longint;
var t:longint;
i:integer;
begin
t:=r[b]*10037+r[c]*5953+r[d]*2999; {用3堵墙的值任意乘大素数相加再取余数，使得结果分布比较随机，也就比较均匀}
t:=t mod p;
i:=0;
while (e[a,(t+i)mod p,1]<>0)and(e[a,(t+i)mod p,1]<>r[b]) do
if (e[a,(t+i)mod p,2]<>r[c])or(e[a,(t+i)mod p,3]<>r[d]) then inc(i); {线性重新散列}
locate:=(t+i)mod p;
end;
但是后来发现完全没有必要这样做，这样的哈希函数在计算 t 的时候浪费了很多时间（不过数据规模不是很大，所以这点不十分明显），而且素数起到的作用也不应当是这样的。其实让 r[b],r[c],r[d] 组成 n 进制数就完全能够达到目的了，加入了素数不仅是小规模数据计算浪费时间，对大数据最后结果的分布平均也没有起到比 n 进制数更多的作用。因此改为
t:=r[b]*sqr(n)+r[c]*n+r[d];
当然肯定会有更好的哈希函数的。
4.7小结
第一个例子，乍一看与哈希表毫无关系；第二个例子叙述比较复杂，但是经过仔细分析，发现问题的本质都是确定“某个元素是否在给定集合中”，这正是哈希表的特点。所以，不论题目的表面看起来如何，只要本质是需要高效的数据检索，哈希表通常就是最好的选择！
另外，这两个例子都在原来哈希表的基础上作了一些变化。第一个例子加入了纪录某个值出现次数的域，第二个例子加入了纪录所有墙的情况以及原节点编号的域。虽然都只是很小的变化，但是却给问题的解决带来了不小的方便。因此我们得到提示：哈希表虽然有标准的操作，但也不是一成不变的，需要具体问题具体分析，根据题目的要求和特点作出相应变化。
5. 总结
本文介绍了有关哈希表方面的内容，分析了它的特点和优点，指出了应用需要注意的问题，并且重点举了几个例子来说明它在竞赛中的应
用。希望读者读完本文能够对哈希表有更全面的了解，并能在竞赛中应
用自如！
参考文献：
1．《算法与数据结构（第二版）》 付清祥 王晓东 编著
2．《奥赛兵法信息学（计算机）》 朱全民 主编
3．《SGOI-8 烦恼的设计师 解题报告》 曙光网信息学
4．《Data Structures》 USACO Training Gate
附录：
这是我第一次写论文，水平很有限，希望大家指出我的缺点和不足！
我的邮箱iliuchong@https://www.wendangku.net/doc/e25980517.html,
下面是所有前面提到的程序。其中只有 SGOI-8 Flowers 的程序是网上提供的标程，其余的都是我自己写的，并且已经通过所有测试数据。
1．哈希表的程序
program subset;
const max=15889;
var fin,fout:text;
a,b,s,j:longint;
index:array[0..max-1]of longint;
t:real;
function locate(t:longint):longint;
var tmp:longint;
begin
tmp:=t mod max;
while (index[tmp]<>0)and(index[tmp]<>t) do
tmp:=(tmp+1) mod max;
locate:=tmp;
end;
procedure int(t:longint);
begin
index[locate(t)]:=t;
end;
function member(t:longint):boolean;
begin
if index[locate(t)]=t then member:=true
else member:=false;
end;
procedure init;
var shu,i:longint;
begin
assign(fin,'subset.in');
assign(fout,'subset.out');
reset(fin);
rewrite(fout);
close(fout);
fillchar(index,sizeof(index),0);
read(fin,a);
for i:=1 to a do
begin
read(fin,shu);
int(shu);
end;
end;
procedure main;
var i,shu:longint;
begin
read(fin,b);
s:=0;
for i:=1 to b do
begin
read(fin,shu);
if not member(shu) then inc(s);
end;
end;
procedure out;
begin
writeln(s);
close(fin);
end;
begin
t:=meml[$40:$6C];
for j:=1 to 50 do
begin
init;
main;
out;
end;
t:=meml[$40:$6C]-t;
writeln(t/18.181818:0:8);
end.
2．快速排序+二分查找的程序program subset;
const max=16101;
var a,b,s,j:longint;
da:array[1..max]of longint;
fin:text;
t:real;
procedure init;
var i:longint;
begin
assign(fin,'subset.in');
reset(fin);
read(fin,a);
for i:=1 to a do
read(fin,da[i]);
end;
procedure sort(m,n:longint);
var p:longint;
function locate:longint;
var value,i,j,temp:longint;
begin
value:=da[(m+n) div 2];
i:=m-1;
j:=n+1;
while true do
begin
repeat
inc(i);
until da[i]>=value;
repeat
dec(j);
until da[j]<=value;
if i temp:=da[i]; da[i]:=da[j]; da[j]:=temp; end else begin if I<>j then locate:=j else locate:=j-1;; exit; end; end; end; begin if m p:=locate; sort(m,p); sort(p+1,n); end; end; procedure main; var i,x:longint; function member(x:longint):boolean; var p,e,mid:longint; begin p:=1; e:=a; mid:=(p+e) div 2; while (p<>mid)and(e<>mid)and(da[mid]<>x) do begin if x=da[mid] then begin member:=true; exit; end; if x e:=mid; mid:=(p+e)div 2; end else begin p:=mid; mid:=(p+e)div 2; end; end; if (da[p]=x)or(da[e]=x)or(da[mid]=x) then member:=true else member:=false; end; begin read(fin,b); s:=0; for i:=1 to b do begin read(fin,x); if not member(x) then inc(s); end; end; procedure out; begin writeln(s); close(fin); end; begin t:=meml[$40:$6C]; for j:=1 to 50 do begin init; sort(1,a); main; out; end; t:=meml[$40:$6C]-t; writeln(t/18.181818:0:8); end. 3．《找名字》的程序 program namenum; const empty:string[12]=' '; value:array[2..9,1..3]of string=(('A','B','C'), ('D','E','F'), ('G','H','I'), ('J','K','L'), ('M','N','O'), ('P','R','S'), ('T','U','V'), ('W','X','Y')); var fin,fout,dict:text; index:array[-1..13882]of string[12]; quest:string; check:boolean; function hash(s:string):integer; var i,tmp:longint; begin tmp:=0; if length(s)>1 then begin tmp:=tmp*27+ord(s[1])-64; for i:=1 downto 0 do tmp:=tmp*27+ord(s[length(s)-i])-64; end else for i:=1 to 3 do tmp:=tmp*27+ord(s[1])-64; hash:=tmp mod 13883; end; function locate(s:string):integer; var tmp,i:integer; begin tmp:=hash(s); i:=0; while (index[(i+tmp)mod 13883]<>s)and(index[(i+tmp)mod 13883]<>empty) do i:=(i+23)mod 13883; locate:=(i+tmp)mod 13883; end; procedure int(s:string); var tmp:integer; begin tmp:=locate(s); index[tmp]:=s; end; procedure init; var s:string; i:integer; begin assign(fin,{'d:\namenum.txt'}'namenum.in'); assign(fout,{'d:\namenum.out'}'namenum.out'); reset(fin); rewrite(fout); assign(dict,{'d:\dict1.txt'}'dict.txt'); reset(dict); for i:=0 to 13882 do index[i]:=empty; while not eof(dict) do begin readln(dict,s); int(s); end; close(dict); readln(fin,quest); close(fin); end; function member(s:string):boolean; var tmp:integer; begin tmp:=locate(s); if index[tmp]=s then member:=true else member:=false; end; procedure work; var st:string; j:integer; procedure examin(t:integer;ch:string); var i:integer; begin if t=length(quest) then begin st:=st+ch; if member(st) then begin writeln(fout,st); check:=true; end; exit; end; st:=st+ch; for i:=1 to 3 do begin examin(t+1,value[ord(quest[t+1])-ord('0'),i]); delete(st,length(st),1); end; end; begin check:=false; for j:=1 to 3 do begin st:=''; examin(1,value[ord(quest[1])-ord('0'),j]); end; if not check then writeln(fout,'NONE'); close(fout); end; begin init; work; end. 4．《转花盆》的程序（这个程序是 SGOI-8 Flowers 的标准程序）program flowers; const size=1058148; base=262143; circle:array[1..7,1..6] of longint =((1,2,6,10,9,4), (2,3,7,11,10,5), (4,5,10,14,13,8), (5,6,11,15,14,9), (6,7,12,16,15,10), (9,10,15,18,17,13), (10,11,16,19,18,14)); x:array[1..7] of longint=(2,2,3,3,3,4,4); y:array[1..7] of longint=(2,3,2,3,4,2,3); InputFn='flowers.in'; OutputFn='flowers.out'; var last,next,q:array[1..size] of longint; id:array[1..size] of shortint; hash:array[0..base] of longint; step,i,j,k,start,target,qs,l,r:longint; bit,s,t:array[1..19] of longint; d:array[0..7] of longint; nowlast,nowid:longint; f,fo:text; procedure init; var d:array[0..5] of longint; i,j:longint; begin assign(f,InputFn); reset(f); for i:=1 to 19 do read(f,s[i]); for i:=1 to 19 do read(f,t[i]); close(f); d[0]:=0; for i:=1 to 19 do begin inc(d[0]); d[d[0]]:=s[i]; for j:=1 to d[0] do if d[j]=s[i] then break; s[i]:=j-1; if j<>d[0] then dec(d[0]); inc(d[0]); d[d[0]]:=t[i]; for j:=1 to d[0] do if d[j]=t[i] then break; t[i]:=j-1; if j<>d[0] then dec(d[0]); end; fillchar(next,sizeof(next),0); fillchar(hash,sizeof(hash),0); end; function change(a,b:longint; plus:longint):longint; var i:longint; begin for i:=1 to 6 do d[i]:=(a div bit[circle[b,i]]) mod 3; d[7]:=d[1]; d[0]:=d[6]; for i:=1 to 6 do a:=a+(d[i+plus]-d[i])*bit[circle[b,i]]; change:=a; end; procedure out; var i,j,dep:longint; stack:array[1..20] of longint; begin i:=qs; dep:=0; while i<>1 do begin inc(dep); stack[dep]:=id[i]; i:=last[i]; end; for i:=dep downto 1 do if stack[i]>0 then writeln(fo,x[stack[i]],' ',y[stack[i]],' ',1) else writeln(fo,x[-stack[i]],' ',y[-stack[i]],' ',0); end; procedure insert(now:longint); var i:longint; begin if now=target then 一: 需求分析 (2) 三: 详细设计（含代码分析） (4) 1.程序描述: (4) 2具体步骤 (4) 四调试分析和测试结果 (7) 五，总结 (9) 六.参考文献; (10) 七.致谢 (10) 八.附录 (11) 一: 需求分析 问题描述：设计哈希表实现电话号码查询系统。 基本要求 1、设每个记录有下列数据项：电话号码、用户名、地址 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少 两种），考察平均查找长度的变化。 二: 概要设计 进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。 具体流程图如下所示: 三: 详细设计（含代码分析） 1.程序描述: 本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储 struct node { string phone; //电话号码 string name; //姓名 string address;//地址 node *next; //链接下一个地址的指针 }; 2具体步骤 1. 要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node *infor_phone[MAX]; node *infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息 用链式法和再哈希法解决冲突： int hash(string key) //以姓名或者电话号码的前四位运算结果作为哈{ //希码 int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=0;i--) { cur=key[i]-'0'; result=result*9+cur; } result%=(MOD); return result; 附件4： 北京理工大学珠海学院 课程设计任务书 2010 ～2011学年第二学期 学生姓名：专业班级： 指导教师：工作部门： 一、课程设计题目 哈希表应用 二、课程设计内容（含技术指标） 【问题描述】 利用哈希表进行存储。 【任务要求】 任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。 设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。 设计目的：实现哈希表的综合操作 简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。 显示元素：显示已经创建的哈希表。 查找元素：查找哈希表中的元素，分为查找成功和查找不成功。 插入元素：在哈希表中，插入一个元素，分为插入成功和失败。 删除元素：在已有的数据中，删除一个元素。 退出系统：退出程序。 【测试数据】 自行设定，注意边界等特殊情况。 三、进度安排 1．初步设计：写出初步设计思路，进行修改完善，并进行初步设计。 2．详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。 3．测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。 4．报告撰写：根据上面设计过程和结果，按照要求写出设计报告。 5．答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。 四、基本要求 1．在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 2．在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 3．设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。 从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 课程负责人签名： 年月日 数据结构课程设计哈希表设计问题 目录 1 前言 (1) 2 需求分析 (1) 2.1 任务和要求 (1) 2.2 运行环境 (1) 2.3 开发工具 (1) 3 分析和设计 (2) 3.1 系统分析及设计思路 (2) 3.2 主要数据结构及算法 (2) 3.3 函数流程图 (2) （1）哈希表的创建及初始化流程图 (2) 5 课程设计总结 (13) 5.1 程序运行结果或预期运行结果 (13) 说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。 (14) 5.2 设计结论 (15) 参考文献 (15) 致谢 (15) 1 前言 从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。 根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2 需求分析 2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。 2.2 运行环境 （1）WINDOWS2000/XP系统 （2）Visual C++ 6.0编译环境或TC编译环境 2.3 开发工具 C语言 3 分析和设计 3.1 系统分析及设计思路 （1）创建哈希表 （2）姓名（结构体数组）初始化 （1）用除留余数法构建哈希函数 （2）用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 (4) 显示哈希表 显示哈希表的的格式： 3.2 主要数据结构及算法 定义结构体typedef struct hashtable创建哈希表 定义函数Hash_Init(HashTable ht)来对哈希表初始化 定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分配地址 定义函数Hash_Init(ht)输入30个名字 定义函数Hash_Create(HashTable ht)来求哈希表长度 定义函数hash_output(HashTable h)来输出哈希表 定义函数Hash_Link()构造链表函数 定义函数int hash_search(int h[],int key)查找输入的名字 3.3 函数流程图 （1）哈希表的创建及初始化流程图 哈希表实现电话号码查询系统 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用 C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二需求分析 1、程序的功能 1)读取数据 ①读取原电话本存储的电话信息。 ②读取系统随机新建电话本存储的电话信息。 2)查找信息 ①根据电话号码查询用户信息。 ②根据姓名查询用户信息。 3)存储信息 查询无记录的结果存入记录文档。 2、输出形式 1)数据文件“old.txt”存放原始电话号码数据。 2)数据文件“new.txt”存放有系统随机生成的电话号码文件。 3)数据文件“out.txt”存放未查找到的电话信息。 4)查找到相关信息时显示姓名、地址、电话号码。 3、初步测试计划 1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存 到“new.txt”中。 2)分别采用伪随机探测再散列法和再哈希法解决冲突。 3)根据姓名查找时显示给定姓名用户的记录。 4)根据电话号码查找时显示给定电话号码的用户记录。 5)将没有查找的结果保存到结果文件Out.txt中。 6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。三概要设计 1、子函数功能 int Collision_Random(int key,int i) //伪随机数探量观测再散列法处理冲突 void Init_HashTable_by_name(string name,string phone,string address) //以姓名为关键字建立哈希表 int Collision_Rehash(int key,string str) //再哈希法处理冲突 void Init_HashTable_by_phone(string name,string phone,string address) //以电话号码为关键字建立哈希表 void Outfile(string name,int key) //在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中void Outhash(int key) //输出哈希表中的记录 void Rafile() //随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n) //建立哈希表 int Search_by_name(string name) //根据姓名查找哈希表中的记录 int Search_by_phone(string phone) //根据电话号码查找哈希表中的记录 1. 引言 哈希表（Hash Table）的应用近两年才在NOI（全国青少年信息学奥林匹克竞赛）中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。 哈希表又叫做散列表，分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方面读者可参阅其他书籍。 2. 基础操作 2.1 基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 2.2 函数构造 构造函数的常用方法（下面为了叙述简洁，设h(k) 表示关键字为k 的元素所对应的函数值）： a) 除余法： 选择一个适当的正整数p ，令h(k ) = k mod p ，这里，p 如果选取的是比较大 的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。 b) 数字选择法： 如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。 2.3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S ，则当h(k)已经存储了元素的时候，依次探查(h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 2.4 支持运算 哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(i nsert)、查找元素(member)。设插入的元素的关键字为x ，A 为存储的数组。初始化比较容易，例如： const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： 课程设计(论文)任务书 软件学院学院软件工程专业班 一、课程设计(论文)题目：通讯录管理系统的设计与实现——哈希表 二、课程设计(论文)工作自2016 年 1 月 4 日起至 2016 年 1 月 10 日止 三、课程设计(论文) 地点: 软件测试中心（北区测试二室） 四、课程设计(论文)内容要求： 1．本课程设计的目的 ⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识，编写程序求解指定问题； ⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能； ⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求： ⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求 ⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订； ⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等； ⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。 3）课程设计评分标准： ⑴学习态度：10分； ⑵系统设计：20分； ⑶编程调试：20分； ⑷回答问题：20分； ⑸论文撰写：30分。 课程设计题目哈希表及其应用 教学院计算机学院 专业 班级 姓名 指导教师 年月日 课程设计任务书 2010 ～2010 学年第 1 学期 一、课程设计题目哈希表及其应用 二、课程设计内容 建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。要求： 1.使用哈希查找表存储信息； 2.实现查找、插入、删除、统计、输出等功能； 三、进度安排 1．初步完成总体设计，搭好框架； 2．完成最低要求：尝试使用多种哈希函数和冲突解决方法，并通过实际运行测试给出自己的评价 四、基本要求 1．界面友好，函数功能要划分好 2．程序要加必要的注释 3．要提供程序测试方案 教研室主任签名： 年月日 1 概述 (4) 2 设计目的 (4) 3 设计功能说明 (4) 4 详细设计说明 (5) 5 流程图 (5) 6 程序代码 (6) 7 程序运行结果 (15) 8 总结 (19) 参考文献 (19) 成绩评定表 (20) 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁，只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实际动手能力。为学生后继课程的学习打下良好的基础。 2 设计目的 《数据结构》课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。 1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。 2.培养学生综合运用所学知识独立完成程序课题的能力。 3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 4．提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的基本素质。 5.培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。 3 设计功能分析 本设计的功能如下： 1、利用哈希函数来实现一个小型信息管理系统，其中信息包含用户名，地址，电话等。 2、能添加用户信息，并能保存该信息。 3、查询管理系统中的信息：可通过姓名查找，也可通过电话查找等两种方式。 /* （1）设计哈希表，该表应能够容纳50个英文单词。 （2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容 已经发到你邮箱里了enochwills@https://www.wendangku.net/doc/e25980517.html, */ #include 哈希表设计数据结构课程设计 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键 字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include Java哈希表及其应用 哈希表也称为散列表，是用来存储群体对象的集合类结构。 什么是哈希表 数组和向量都可以存储对象，但对象的存储位置是随机的，也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时，只能以某种顺序（如顺序查找或二分查找）与各个元素进行比较，当数组或向量中的元素数量很多时，查找的效率会明显的降低。 一种有效的存储方式，是不与其他元素进行比较，一次存取便能得到所需要的记录。这就需要在对象的存储位置和对象的关键属性（设为k）之间建立一个特定的对应关系（设为f），使每个对象与一个唯一的存储位置相对应。在查找时，只要根据待查对象的关键属性k 计算f(k)的值即可。如果此对象在集合中，则必定在存储位置f(k)上，因此不需要与集合中的其他元素进行比较。称这种对应关系f 为哈希（hash）方法，按照这种思想建立的表为哈希表。 Java 使用哈希表类（Hashtable）来实现哈希表，以下是与哈希表相关的一些概念： ?容量（Capacity）：Hashtable 的容量不是固定的，随对象的加入其容量也可以自动增长。?关键字（Key）：每个存储的对象都需要有一个关键字，key 可以是对象本身，也可以是对象的一部分（如某个属性）。要求在一个Hashtable 中的所有关键字都是唯一的。 ?哈希码（Hash Code）：若要将对象存储到Hashtable 上，就需要将其关键字key 映射到一个整型数据，成为key 的哈希码。 ?项（Item）：Hashtable 中的每一项都有两个域，分别是关键字域key 和值域value（存储的对象）。Key 和value 都可以是任意的Object 类型的对象，但不能为空。 ?装填因子（Load Factor）：装填因子表示为哈希表的装满程度，其值等于元素数比上哈希表的长度。 哈希表的使用 哈希表类主要有三种形式的构造方法： Hashtable(); //默认构造函数，初始容量为101，最大填充因子0.75 Hashtable(int capacity); 一、问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 二、基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 三、概要设计 1.构造结构体：typedef struct{}； 2.姓名表的初始化：void InitNameTable()； 3.建立哈希表：void CreateHashTable()； 4.显示姓名表：void DisplayNameTable()； 5.姓名查找：void FindName()； 6.主函数：void main() ； 四、详细设计 1.姓名表的初始化 void InitNameTable() { NameTable[0].py="louyuhong"; NameTable[1].py="shenyinghong"; NameTable[2].py="wangqi"; NameTable[3].py="zhuxiaotong"; NameTable[4].py="zhataotao"; NameTable[5].py="chenbinjie"; NameTable[6].py="chenchaoqun"; NameTable[7].py="chencheng"; NameTable[8].py="chenjie"; NameTable[9].py="chenweida"; NameTable[10].py="shanjianfeng"; NameTable[11].py="fangyixin"; NameTable[12].py="houfeng"; NameTable[13].py="hujiaming"; NameTable[14].py="huangjiaju"; NameTable[15].py="huanqingsong"; NameTable[16].py="jianghe"; NameTable[17].py="jinleicheng"; NameTable[18].py="libiao"; NameTable[19].py="liqi"; NameTable[20].py="lirenhua"; NameTable[21].py="liukai"; NameTable[22].py="louhanglin"; NameTable[23].py="luchaoming"; NameTable[24].py="luqiuwei"; NameTable[25].py="panhaijian"; NameTable[26].py="shuxiang"; NameTable[27].py="suxiaolei"; NameTable[28].py="sunyubo"; NameTable[29].py="wangwei"; for (i=0;i 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C 语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include 哈希表（hashtable） 注：哈希表为1.24及以上版本才有的功能，以下版本是无法使用的说~ （在1.24之前，游戏缓存（ganecache）+return bug起到了相同的作用，124之后它们即被哈希表取代， 并且return bug在1,24之后，被修复了） 本演示侧重于hashtable，仅仅会顺带提到hashtable与gamecache两种方式的等价代码转换~ ☆哈希表的特点与优势~ 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 当然这个概念可能过于深奥，我们不必了解那么深入，只需要了解它的功能以及如何使用~（当然有能力的童鞋，推荐去百度寻找详解） 先简单介绍下好了~hashtable就相当于一个存储数据的仓库，其具有容量大以及存储速度稳定的特点~ 使用hashtable与GetHandleId函数，能够非常轻易地实现一个技能的多人无冲突使用~ ☆先来认识下这货~ 首先，我们先来声明一个哈希表对象~ 由于哈希表通常起到全局范围内的数据存储以及传递~ 所以我们绝大多数情况（和所有基本没区别）都是将其作为一个全局变量来声明（几乎没有局部变量的 哈希表，只有在某些特殊需求下，才会罕见地出现；如果你明确知道自己创建局部hashtable的目的，并 且知道如何妥善掌控，那么是毫无问题的） jass globals hashtable ht=InitHashtable() //函数InitHashtable，无参数，返回一个新建的哈希表对象 //在向一个哈希表中存入数据之前，必须先通过此函数创建哈希表，否则无效（好比你无法往一个根本 不存在的容器中倒水一样的说~） endglobals 很简单，这样就创建了一个哈希表，你可以在地图中的任何地方（没错，任何地方）访问它~ Tips： （显式声明globals块（也就是上面）的方式，其实是Vjass才有的功能~如果你的编辑器UI没有这个，请 在T的变量管理器中，创建一个哈希表对象，但别忘了加上udg_前缀以及调用InitHashtable函数进行初 始化~） 然后我们可以试着，在其中存并且读取一些数据~ jass function Trig_Init_Actions takes nothing returns nothing local integer i=5 local integer ret//两个整数变量 #include } return -1; } //删除 void DeleteHT(HashTable ha,int p,int k,int n) { int adr; int adr2; adr2=k%p; typedef struct node { int val; node * next; }; //拉链法 node *pt,*r; adr=SearchHT(ha,p,k);//查找关键字 pt=(node*)adr; if(adr!=-1) { while(pt->val!=k) { r=pt; pt=pt->next; } if(pt->val==k) { if((int)pt==adr) { if(pt->next==NULL) ha[adr2].key=NULLKEY; else adr=(int)pt->next; } else r->next=pt->next; } ha[adr2].count--; } else printf("删除失败！"); } //插入 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名王东东 学号0804012030 专业班级08计本（2) 指导教师王昆仑、李贯虹 2010 年5 月 课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一， 是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到 理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和 数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并 用软件解决问题，培养良好的程序设计技能。 一、问题分析和任务定义 1、问题分析 要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1）如何定义一个包括电话号码、用户名、地址的节点。 （2）如何以电话号码和用户名为关键字建立哈希表。 （3）用什么方法解决冲突。 （4）如何查找并显示给定电话号码的记录。 （5）如何查找并显示给定用户名的记录。 2 任务定义 1、由问题分析知，本设计要求分别以电话号码和用户名为关键字建立哈希表，z在此基 础上实现查找功能。本实验是要我们分析怎么样很好的解决散列问题，从而建立一比较合理 的哈希表。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息 丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使 用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 根据问题分析，我们可以定义有3个域的节点，这三个域分别为电话号码char num[30]，姓名char name[30]，地址char address[30]。这种类型的每个节点对应链表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的创建。 二、数据结构的选择和概要设计 1、数据结构的选择 数据结构：散列结构。 散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系，并提供多 种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。 散列结构基本思想，是以所需存储的结点中的关键词作为自变量，通过某种确定的函 数H（称作散列函数或者哈希函数）进行计算，把求出的函数值作为该结点的存储地址，并 将该结点或结点地址的关键字存储在这个地址中。 散列结构法（简称散列法）通过在结点的存储地址和关键字之间建立某种确定的函数 关系H，使得每个结点（或关键字）都有一个唯一的存储地址相对应。 当需要查找某一指定关键词的结点时，可以很方便地根据待查关键字K计算出对应的“映像”H(K)，即结点的存储地址。从而一次存取便能得到待查结点，不再需要进行若干次的 比较运算，而可以通过关键词直接计算出该结点的所在位置。 哈希表操作 一目的 1.巩固和加深对哈希表的创建、查找、插入等方法理论知识的理解。 2.掌握建立哈希表的办法，本实验是采用的是除留余数法创建。 3.掌握哈希表解决冲突的办法，本实验用的是线性探测再散列的方法。 4.巩固对程序模块化设计的要求。 二需求分析 1.对于哈希表的基本操作首先是要创建一个哈希表,哈希表的创建思想是由哈希函 数得到,本实验就采用了除留余数法创建哈希表。 2.创建好哈希表就需要在哈希表中插入元素，本实验是需要插入单词，所以需要调 用string函数库，通过每个单词的地址数来进行下一步的查找计划。当插入单词地址已经存在时，就产生了冲突，因此需要采用线性探测再散列的方式来解决冲突。 3.当哈希表插入单词完成之后便可以显示哈希表的存储情况，因此需要输出整个哈 希表。 4.要想计算平均查找长度首先要对哈希表中的元素进行查找，当所有单词查找结 束，查找长度也得出。 5.要实现上诉需求，程序需要采用模块化进行设计。 三概要设计 1.基本操作： void Initwordlist(int n) 初始化哈希表 操作结果：以字符形式插入单词，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。 void Createhashlist(int n) 创建哈希表,并插入单词 操作结果： (1)用除留余数法构建哈希函数； (2)用线性探测再散列处理冲突。 void find() 查找哈希表中的单词 操作结果：在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度。 void printhash() 显示哈希表 操作结果：显示哈希表的存储情况：位置%d\t\t关键字%-6d\t\t单词%s\n。 float average() 操作结果：计算出平均查找长度。 void menu() 菜单函数设计 操作结果：显示格式： 1向哈希表中插入单词(<15)； 2查找哈希表中的单词； 3显示哈希表的存储情况； 4计算哈希表的平均查找长度； 5退出程序。 int main() 主程序设计 操作结果：通过调用各个函数操作得到结果。哈希表的设计与实现 课程设计报告
哈希表应用
数据结构课程设计哈希表设计问题复习过程
哈希表实现电话号码查询系统
散列表(哈希表)
数据结构课设-通讯录系统的设计与实现——哈希表
哈希表及其应用-课程设计
哈希表查询设计及实现
哈希表设计数据结构课程设计
Java哈希表及其应用
数据结构哈希表设计
哈希表设计-数据结构课程设计
哈希表
哈希表拉链法
哈希表的设计与实现-数据结构与算法课程设计报告
哈希表的操作
- 哈希表的设计与实现
- 数据结构课设-通讯录系统的设计与实现——哈希表
- 课程设计试验报告-哈希表的设计与实现
- 哈希表的实现及简单应用 数据结构课程设计 实训
- 设计哈希表实现电话号码查询系统
- 哈希表的设计与实现
- 课程设计试验报告-哈希表的设计与实现
- 哈希表《数据结构》课程设计
- 数据结构课设 通讯录系统的设计与实现 哈希表
- 【VIP专享】哈希表的设计与实现,含源代码
- 数据结构课设 通讯录系统的设计与实现 哈希表
- 散列表的设计与实现报告
- 数据结构课程设计散列表设计与实现
- 哈希表实现通讯录-数据结构与算法课程设计报告
- 数据结构设计报告--哈希查找与实现
- 哈希表课程设计--哈希表的实现与应用
- 哈希表课程设计报告
- 哈希表查询设计及实现
- 哈希表的设计与实现
- 课程设计试验报告-哈希表的设计与实现