问题描述：
数据结构 哈希表建立
问题解答：
我来补答
有些图打不上去.如果想要完整的资料告诉我邮箱,我发给你 .
哈希表及其应用
一、定义
二、基本原理
哈希表的基本原理是：使用一个下标范围比较大的数组A来存储元素,设计一个函数h,对于要存储的线性表的每个元素node,取一个关键字key,算出一个函数值h(key),把h(key)作为数组下标,用A[h(key)]这个数组单元来存储node.也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方（这一过程称为“直接定址”）.
但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中.例如,假设一个结点的关键码值为key,把它存入哈希表的过程是：根据确定的函数h计算出h(key)的值,如果以该值为地址的存储空间还没有被占用,那么就把结点存入该单元；如果此值所指单元里已存了别的结点（即发生了冲突）,那么就再用另一个函数I进行映象算出I(h(key)),再看用这个值作为地址的单元是否已被占用了,若已被占用,则再用I映象,……,直到找到一个空位置将结点存入为止.当然这只是解决“冲突”的一种简单方法,如何避免、减少和处理“冲突”是使用哈希表的一个难题.
在哈希表中查找的过程与建立哈希表的过程相似,首先计算h(key)的值,以该值为地址到基本区域中去查找.如果该地址对应的空间未被占用,则说明查找失败,否则用该结点的关键码值与要找的key比较,如果相等则检索成功,否则要继续用函数I计算I(h(key))的值,…….如此反复到某步或者求出的某地址空间未被占用（查找失败）或者比较相等（查找成功）为止.
三、基本概念和简单实现
1、两个集合：U是所有可能出现的关键字集合；K是实际存储的关键字集合.
2、函数h将U映射到表T[0..m-1]的下标上,可以表示成 h：U→{0,1,2,...,m-1},通常称h为“哈希函数(Hash Function)”,其作用是压缩待处理的下标范围,使待处理的|U|个值减少到m个值,从而降低空间开销（注：|U|表示U中关键字的个数,下同）.
3、将结点按其关键字的散列地址存储到哈希表（散列表）中的过程称为“散列(Hashing)”.方法称为“散列法”.
4、h(Ki)(Ki∈U)是关键字为Ki的结点的“存储地址”,亦称散列值、散列地址、哈希地址.
5、用散列法存储的线性表称为“哈希表（Hash Table）”,又称散列表.图中T即为哈希表.在散列表里可以对结点进行快速检索（查找）.
6、对于关键字为key的结点,按照哈希函数h计算出地址h(key),若发现此地址已被别的结点占用,也就是说有两个不同的关键码值key1和key2对应到同一个地址,即h(key1)=h(key2),这个现象叫做“冲突（碰撞）”.碰撞的两个（或多个）关键码称为“同义词”（相对于函数h而言）.如图1中的关键字k2和k5,h(k2)=h(k5),即发生了“冲突”,所以k2和k5称为“同义词”.假如先存了k2,则对于k5,我们可以存储在h(k2)+1中,当然h(k2)+1要为空,否则可以逐个往后找一个空位存放.这是另外一种简单的解决冲突的方法.
发生了碰撞就要想办法解决,必须想办法找到另外一个新地址,这当然要降低处理效率,因此我们希望尽量减少碰撞的发生.这就需要分析关键码集合的特性,找适当的哈希函数h使得计算出的地址尽可能“均匀分布”在地址空间中.同时,为了提高关键码到地址转换的速度,也希望哈希函数“尽量简单”.然而对于各种取值的关键码而言,一个好的哈希函数通常只能减少碰撞发生的次数,无法保证绝对不产生碰撞.因此散列除去要选择适当的哈希函数以外,还要研究发生碰撞时如何解决,即用什么方法存储同义词.
7、负载因子
我们把h(key)的值域所对应到的地址空间称为“基本区域”,发生碰撞时,同义词可以存放在基本区域还没有被占用的单元里,也可以放到基本区域以外另开辟的区域中（称为“溢出区”）.下面引入散列的一个重要参数“负载因子或装填因子(Load Factor)”,它定义为：
а=
负载因子的大小对于碰撞的发生频率影响很大.直观上容易想象,а越大,散列表装得越满,则再要载入新的结点时碰上已有结点的可能性越大,冲突的机会也越大.特别当а＞1时碰撞是不可避免的.一般总是取а＜1,即分配给散列表的基本区域大于所有结点所需要的空间.当然分配的基本区域太大了也是浪费.例如,某校学生干部的登记表,每个学生干部是一个结点,用学号做关键码,每个学号用7位数字表示,如果分配给这个散列表的基本区域为107个存储单元,那么散列函数就可以是个恒等变换,学号为7801050的学生结点就存入相对地址为7801050的单元,这样一次碰撞也不会发生,但学校仅几百个学生干部,实际仅需要几百个单元的空间,如果占用了107个存储单元,显然太浪费了,所以这是不可取的.负载因子的大小要取得适当,使得既不过多地增加碰撞,有较快的检索速度,也不浪费存储空间.
下面结合引例说明一下上面的思想和方法.
【例1】用散列存储线性表：A=（18,75,60,43,54,90,46）.
分析：
假定选取的散列函数为：h(K)=K mod m,K为元素的关键字,m为散列表的长度,用余数作为存储该元素的散列地址.这里假定K和m均为正整数,并且m要大于等于线性表的长度n.此例n=7,故假定取m=13,则得到的每个元素的散列地址为：
h(18)=18 mod 13=5 h(75)=75 mod 13 =10 h(60)=60 mod 13=8
h(43)=43 mod 13=4 h(54)=54 mod 13=2 h(90)=90 mod 13=12
h(46)=46 mod 13=7
根据散列地址按顺序把元素存储到散列表H（0：m-1）中,存储映象为：
0 1 2 3 4 5 6 7 8 9 10 11 12
54 43 18 46 60 75 90
当然这是一个比较理想的情况.假如再往表中插入第8个元素30,h(30)=30 mod 13=4,我们会发现H[4]已经存了43,此时就发生了冲突.我们可以从H[4]往后按顺序找一个空位置存放30,即可以把它插入到H[6]中.
四、哈希函数的构造方法
选择适当的哈希函数是实现散列的重中之重,构造哈希函数有两个标准：简单和均匀.简单是指哈希函数的计算要简单快速；均匀是指对于关键字集合中的任一关键字,哈希函数能以等概率将其映射到表空间的任何一个位置上.也就是说,哈希函数能将子集K随机均匀地分布在表的地址集{0,1,...,m-1}上,以使冲突最小化.
为简单起见,假定关键码是定义在自然数集合上,常见的哈希函数构造方法有：
1、直接定址法
以关键字Key本身或关键字加上某个数值常量C作为散列地址的方法.散列函数为：h(Key)= Key+C,若C为0,则散列地址就是关键字本身.
2、除余法
选择一个适当的正整数m,用m去除关键码,取其余数作为地址,即：h(Key)= Key mod m,这个方法应用的最多,其关键是m的选取,一般选m为小于某个区域长度n的最大素数（如例1中取m=13）,为什么呢?就是为了尽力避免冲突.假设取m=1000 ,则哈希函数分类的标准实际上就变成了按照关键字末三位数分类,这样最多1000类,冲突会很多.一般地说,如果 m 的约数越多,那么冲突的几率就越大.
简单的证明：假设m是一个有较多约数的数,同时在数据中存在q满足gcd(m,q)=d >1 ,即有m=a*d,q=b*d,则有以下等式：q mod m= q – m* [q div m] =q – m*[b div a] .
其中,[b div a]的取值范围是不会超过[0,b]的正整数.也就是说,[b div a]的值只有b+1种可能,而m是一个预先确定的数.因此上式的值就只有b+1种可能了.这样,虽然mod 运算之后的余数仍然在[0,m-1]内,但是它的取值仅限于等式可能取到的那些值.也就是说余数的分布变得不均匀了.容易看出,m的约数越多,发生这种余数分布不均匀的情况就越频繁,冲突的几率越高.而素数的约数是最少的,因此我们选用大素数.记住“素数是我们的得力助手”.
3、数字分析法
常有这样的情况：关键码的位数比存储区域的地址的位数多,在这种情况下可以对关键码的各位进行分析,丢掉分布不均匀的位留下分布均匀的位作为地址.
本方法适用于所有关键字已知,并对关键字中每一位的取值分布情况作出了分析.
【例2】对下列关键码集合（表中左边一列）进行关键码到地址的转换,要求用三位地址.
Key H(Key)
000319426 326
000718309 709
000629443 643
000758615 715
000919697 997
000310329 329
分析：
关键码是9位的,地址是3位的,需要经过数字分析丢掉6位.丢掉哪6位呢?显然前3位是没有任何区分度,第5位1太多、第6位基本都是8和9、第7位都是3、4、5,这几位的区分度都不好,而相对来说,第4、8、9位分布比较均匀,所以留下这3位作为地址（表中右边一列）.
4、平方取中法
将关键码的值平方,然后取中间的几位作为散列地址.具体取多少位视实际要求而定,取哪几位常常结合数字分析法.
【例3】将一组关键字(0100,0110,1010,1001,0111)平方后得(0010000,0012100,1020100,1002001,0012321),若取表长为1000,则可取中间的三位数作为散列地址集：
(100,121,201,020,123).
5、折叠法
如果关键码的位数比地址码的位数多,而且各位分布较均匀,不适于用数字分析法丢掉某些数位,那么可以考虑用折叠法.折叠法是将关键码从某些地方断开,分关键码为几个部分,其中有一部分的长度等于地址码的长度,然后将其余部分加到它的上面,如果最高位有进位,则把进位丢掉.
一般是先将关键字分割成位数相同的几段（最后一段的位数可少一些）,段的位数取决于散列地址的位数,由实际需要而定,然后将它们的对应位叠加和（舍去最高位进位）作为散列地址.
【例4】如关键码Key=58422241,要求转换为3位的地址码.
分析：分如下3段：5 8 4 | 2 2 2 | 4 1,则相加：
5 8 4
2 2 2
4 1
8 4 7
h(Key)=847
6、基数转换法
将关键码值看成在另一个基数制上的表示,然后把它转换成原来基数制的数,再用数字分析法取其中的几位作为地址.一般取大于原来基数的数作转换的基数,并且两个基数要是互质的.如：key=(236075)10是以10为基数的十进制数,现在将它看成是以13为基数的十三进制数(236075)13,然后将它转换成十进制数.
（236075）13=2*135+3*134+6*133+7*13+5
=(841547)10
再进行数字分析,比如选择第2,3,4,5位,于是h(236075)=4154
五、哈希表支持的运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member).设插入元素的关键字为 x ,A 为哈希表,则各种运算过程如下：
1、初始化比较容易,例如：
const empty=maxlongint; {用非常大的整数代表这个位置没有存储元素}
p=9997; {根据需要设定的表的大小}
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do A[i]:=empty;
End;
2、哈希函数值的运算,根据函数的不同而变化,例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
3、我们注意到,插入和查找首先都需要对这个元素定位,因此加入一个定位的函数 locate：
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i
哈希表及其应用
一、定义
二、基本原理
哈希表的基本原理是：使用一个下标范围比较大的数组A来存储元素,设计一个函数h,对于要存储的线性表的每个元素node,取一个关键字key,算出一个函数值h(key),把h(key)作为数组下标,用A[h(key)]这个数组单元来存储node.也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方（这一过程称为“直接定址”）.
但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中.例如,假设一个结点的关键码值为key,把它存入哈希表的过程是：根据确定的函数h计算出h(key)的值,如果以该值为地址的存储空间还没有被占用,那么就把结点存入该单元；如果此值所指单元里已存了别的结点（即发生了冲突）,那么就再用另一个函数I进行映象算出I(h(key)),再看用这个值作为地址的单元是否已被占用了,若已被占用,则再用I映象,……,直到找到一个空位置将结点存入为止.当然这只是解决“冲突”的一种简单方法,如何避免、减少和处理“冲突”是使用哈希表的一个难题.
在哈希表中查找的过程与建立哈希表的过程相似,首先计算h(key)的值,以该值为地址到基本区域中去查找.如果该地址对应的空间未被占用,则说明查找失败,否则用该结点的关键码值与要找的key比较,如果相等则检索成功,否则要继续用函数I计算I(h(key))的值,…….如此反复到某步或者求出的某地址空间未被占用（查找失败）或者比较相等（查找成功）为止.
三、基本概念和简单实现
1、两个集合：U是所有可能出现的关键字集合；K是实际存储的关键字集合.
2、函数h将U映射到表T[0..m-1]的下标上,可以表示成 h：U→{0,1,2,...,m-1},通常称h为“哈希函数(Hash Function)”,其作用是压缩待处理的下标范围,使待处理的|U|个值减少到m个值,从而降低空间开销（注：|U|表示U中关键字的个数,下同）.
3、将结点按其关键字的散列地址存储到哈希表（散列表）中的过程称为“散列(Hashing)”.方法称为“散列法”.
4、h(Ki)(Ki∈U)是关键字为Ki的结点的“存储地址”,亦称散列值、散列地址、哈希地址.
5、用散列法存储的线性表称为“哈希表（Hash Table）”,又称散列表.图中T即为哈希表.在散列表里可以对结点进行快速检索（查找）.
6、对于关键字为key的结点,按照哈希函数h计算出地址h(key),若发现此地址已被别的结点占用,也就是说有两个不同的关键码值key1和key2对应到同一个地址,即h(key1)=h(key2),这个现象叫做“冲突（碰撞）”.碰撞的两个（或多个）关键码称为“同义词”（相对于函数h而言）.如图1中的关键字k2和k5,h(k2)=h(k5),即发生了“冲突”,所以k2和k5称为“同义词”.假如先存了k2,则对于k5,我们可以存储在h(k2)+1中,当然h(k2)+1要为空,否则可以逐个往后找一个空位存放.这是另外一种简单的解决冲突的方法.
发生了碰撞就要想办法解决,必须想办法找到另外一个新地址,这当然要降低处理效率,因此我们希望尽量减少碰撞的发生.这就需要分析关键码集合的特性,找适当的哈希函数h使得计算出的地址尽可能“均匀分布”在地址空间中.同时,为了提高关键码到地址转换的速度,也希望哈希函数“尽量简单”.然而对于各种取值的关键码而言,一个好的哈希函数通常只能减少碰撞发生的次数,无法保证绝对不产生碰撞.因此散列除去要选择适当的哈希函数以外,还要研究发生碰撞时如何解决,即用什么方法存储同义词.
7、负载因子
我们把h(key)的值域所对应到的地址空间称为“基本区域”,发生碰撞时,同义词可以存放在基本区域还没有被占用的单元里,也可以放到基本区域以外另开辟的区域中（称为“溢出区”）.下面引入散列的一个重要参数“负载因子或装填因子(Load Factor)”,它定义为：
а=
负载因子的大小对于碰撞的发生频率影响很大.直观上容易想象,а越大,散列表装得越满,则再要载入新的结点时碰上已有结点的可能性越大,冲突的机会也越大.特别当а＞1时碰撞是不可避免的.一般总是取а＜1,即分配给散列表的基本区域大于所有结点所需要的空间.当然分配的基本区域太大了也是浪费.例如,某校学生干部的登记表,每个学生干部是一个结点,用学号做关键码,每个学号用7位数字表示,如果分配给这个散列表的基本区域为107个存储单元,那么散列函数就可以是个恒等变换,学号为7801050的学生结点就存入相对地址为7801050的单元,这样一次碰撞也不会发生,但学校仅几百个学生干部,实际仅需要几百个单元的空间,如果占用了107个存储单元,显然太浪费了,所以这是不可取的.负载因子的大小要取得适当,使得既不过多地增加碰撞,有较快的检索速度,也不浪费存储空间.
下面结合引例说明一下上面的思想和方法.
【例1】用散列存储线性表：A=（18,75,60,43,54,90,46）.
分析：
假定选取的散列函数为：h(K)=K mod m,K为元素的关键字,m为散列表的长度,用余数作为存储该元素的散列地址.这里假定K和m均为正整数,并且m要大于等于线性表的长度n.此例n=7,故假定取m=13,则得到的每个元素的散列地址为：
h(18)=18 mod 13=5 h(75)=75 mod 13 =10 h(60)=60 mod 13=8
h(43)=43 mod 13=4 h(54)=54 mod 13=2 h(90)=90 mod 13=12
h(46)=46 mod 13=7
根据散列地址按顺序把元素存储到散列表H（0：m-1）中,存储映象为：
0 1 2 3 4 5 6 7 8 9 10 11 12
54 43 18 46 60 75 90
当然这是一个比较理想的情况.假如再往表中插入第8个元素30,h(30)=30 mod 13=4,我们会发现H[4]已经存了43,此时就发生了冲突.我们可以从H[4]往后按顺序找一个空位置存放30,即可以把它插入到H[6]中.
四、哈希函数的构造方法
选择适当的哈希函数是实现散列的重中之重,构造哈希函数有两个标准：简单和均匀.简单是指哈希函数的计算要简单快速；均匀是指对于关键字集合中的任一关键字,哈希函数能以等概率将其映射到表空间的任何一个位置上.也就是说,哈希函数能将子集K随机均匀地分布在表的地址集{0,1,...,m-1}上,以使冲突最小化.
为简单起见,假定关键码是定义在自然数集合上,常见的哈希函数构造方法有：
1、直接定址法
以关键字Key本身或关键字加上某个数值常量C作为散列地址的方法.散列函数为：h(Key)= Key+C,若C为0,则散列地址就是关键字本身.
2、除余法
选择一个适当的正整数m,用m去除关键码,取其余数作为地址,即：h(Key)= Key mod m,这个方法应用的最多,其关键是m的选取,一般选m为小于某个区域长度n的最大素数（如例1中取m=13）,为什么呢?就是为了尽力避免冲突.假设取m=1000 ,则哈希函数分类的标准实际上就变成了按照关键字末三位数分类,这样最多1000类,冲突会很多.一般地说,如果 m 的约数越多,那么冲突的几率就越大.
简单的证明：假设m是一个有较多约数的数,同时在数据中存在q满足gcd(m,q)=d >1 ,即有m=a*d,q=b*d,则有以下等式：q mod m= q – m* [q div m] =q – m*[b div a] .
其中,[b div a]的取值范围是不会超过[0,b]的正整数.也就是说,[b div a]的值只有b+1种可能,而m是一个预先确定的数.因此上式的值就只有b+1种可能了.这样,虽然mod 运算之后的余数仍然在[0,m-1]内,但是它的取值仅限于等式可能取到的那些值.也就是说余数的分布变得不均匀了.容易看出,m的约数越多,发生这种余数分布不均匀的情况就越频繁,冲突的几率越高.而素数的约数是最少的,因此我们选用大素数.记住“素数是我们的得力助手”.
3、数字分析法
常有这样的情况：关键码的位数比存储区域的地址的位数多,在这种情况下可以对关键码的各位进行分析,丢掉分布不均匀的位留下分布均匀的位作为地址.
本方法适用于所有关键字已知,并对关键字中每一位的取值分布情况作出了分析.
【例2】对下列关键码集合（表中左边一列）进行关键码到地址的转换,要求用三位地址.
Key H(Key)
000319426 326
000718309 709
000629443 643
000758615 715
000919697 997
000310329 329
分析：
关键码是9位的,地址是3位的,需要经过数字分析丢掉6位.丢掉哪6位呢?显然前3位是没有任何区分度,第5位1太多、第6位基本都是8和9、第7位都是3、4、5,这几位的区分度都不好,而相对来说,第4、8、9位分布比较均匀,所以留下这3位作为地址（表中右边一列）.
4、平方取中法
将关键码的值平方,然后取中间的几位作为散列地址.具体取多少位视实际要求而定,取哪几位常常结合数字分析法.
【例3】将一组关键字(0100,0110,1010,1001,0111)平方后得(0010000,0012100,1020100,1002001,0012321),若取表长为1000,则可取中间的三位数作为散列地址集：
(100,121,201,020,123).
5、折叠法
如果关键码的位数比地址码的位数多,而且各位分布较均匀,不适于用数字分析法丢掉某些数位,那么可以考虑用折叠法.折叠法是将关键码从某些地方断开,分关键码为几个部分,其中有一部分的长度等于地址码的长度,然后将其余部分加到它的上面,如果最高位有进位,则把进位丢掉.
一般是先将关键字分割成位数相同的几段（最后一段的位数可少一些）,段的位数取决于散列地址的位数,由实际需要而定,然后将它们的对应位叠加和（舍去最高位进位）作为散列地址.
【例4】如关键码Key=58422241,要求转换为3位的地址码.
分析：分如下3段：5 8 4 | 2 2 2 | 4 1,则相加：
5 8 4
2 2 2
4 1
8 4 7
h(Key)=847
6、基数转换法
将关键码值看成在另一个基数制上的表示,然后把它转换成原来基数制的数,再用数字分析法取其中的几位作为地址.一般取大于原来基数的数作转换的基数,并且两个基数要是互质的.如：key=(236075)10是以10为基数的十进制数,现在将它看成是以13为基数的十三进制数(236075)13,然后将它转换成十进制数.
（236075）13=2*135+3*134+6*133+7*13+5
=(841547)10
再进行数字分析,比如选择第2,3,4,5位,于是h(236075)=4154
五、哈希表支持的运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member).设插入元素的关键字为 x ,A 为哈希表,则各种运算过程如下：
1、初始化比较容易,例如：
const empty=maxlongint; {用非常大的整数代表这个位置没有存储元素}
p=9997; {根据需要设定的表的大小}
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do A[i]:=empty;
End;
2、哈希函数值的运算,根据函数的不同而变化,例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
3、我们注意到,插入和查找首先都需要对这个元素定位,因此加入一个定位的函数 locate：
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i
展开全文阅读