Chinaunix首页 | 论坛 | 博客
  • 博客访问: 12033
  • 博文数量: 4
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 12
  • 用 户 组: 普通用户
  • 注册时间: 2015-04-24 20:31
文章分类
文章存档

2016年(1)

2015年(3)

我的朋友
最近访客

分类: C/C++

2015-09-23 22:07:44

原文地址:哈希表与哈希函数 作者:zhenhuaqin

  哈希查找因使用哈希 (Hash) 函数而得名,哈希函数又叫散列函数,它是一种能把关键字映射成记录存贮地址的函数。
.哈希表

它是一种能把关键字映射成记录存贮地址的函数。
假定数组 HT[0 m-1] 为存贮记录的地址空间, m 为表长,哈希函数 H 以记录的关键字 K 为自变量,计算出对应的函数值 H(K) ,并以它作为关键字 K 所标识的记录在表 HT 中的 ( 相对 ) 地址或索引号,这样产生的记录表 HT 叫做对应于哈希函数 H 哈希表
简言之,在哈希表中,关键字为 K 的记录,存贮在 HT[H(K)] 位置。
哈希函数值 H(K) 称为 K 的哈希地址或散列地址。

二.构造哈希表
  构造哈希函数的方法很多,这里只介绍一些常用的,计算简便的方法。

1.
平方取中法
  算出关键字值的平方,再取其中若干位作为哈希函数值 ( 散列地址 )
【例】假定表中各关键字是由字母组成的,用二位数字的整数 01 26 表示对应的 26 个英文字母在计算机中的内部编码,则使用平方取中法计算 KEYA KEYB AKEY BKEY 的散列地址可得:
关键字 K     K 的内部编码            K 2           H(K)
 KEYA         11052501       122157778355001      778
 KEYB         11052502       122157800460004      800
 AKEY         01110525       001233265775625      265
 BKEY         02110525       004454315775625      315
平方之后,取左起第 7 9 位作为散列地址。


2.
除留余数法
    
这种方法是用模运算 (%) 得到的。设给出的关键字值为 K ,存储区单元数为 m ,则用一个小于 m 的质数 P 去除 K ,得到的余数为 R ,即: R K % P 。如果 R 落在存储区地址范围内,则 R 就取为哈希函数值 ( 散列地址 ) ;否则,再用一个线性数求出哈希函数值。
【例】有一组关键字从 000001 859999 ,指定的存储区地址为 1000000 1005999 ,即 m 6000 ,可选 P 599 ,若要转换关键字 K 172148 ,则有:
                R
172148 % 599 4176
R 不在指定的地址范围内,所以,取哈希函数为:

                  H(K)
1000000 R
故有:

                H(K)
H(172148) 1004176
这样就把关键字 K 直接转换成存储地址了。

三.可能产生的冲突:

1)冲突
   
 不同的关键字值,具有相同的哈希地址,因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。
 
 【例】上图中的k2≠k5,但h(k2)=h(k5),故k2K5所在的结点的存储地址相同。

2)安全避免冲突的条件
   
如何避免冲突发生,则取决于哈希函数的构造。
   
使散列地址均匀地分布在哈希表的整个地址区间内,这样可以避免或减少发生冲突。

   
哈希函数的构造,与关键字的长度、哈希表的大小、关键字的实际取值状况等许多因素有关,而且有的因素事前不能确定。所以,避免冲突这并非是件容易做到的事。
3)冲突不可能完全避免
   
 由于关键字的值域往往比哈希表的个数大的多,所以哈希函数是一种压缩映射,碰撞是难免的。
   
【例】存贮 100 个学生记录,尽管安排 120 个地址空间,但由于学生名 ( 假设不超过 10 个英文字母 ) 的理论个数超过 2610 ,要找到一个哈希函数把 100 个任意的学生名映射成 [0 119] 内的不同整数,实际上是不可能的。
   
注意:问题在于一旦发生了冲突应如何处理。

四.解决冲突的主要方法
  虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是哈希技术中的两个重要问题。

1
、开放定址法
   
 用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查()序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的地址则表明表中无待查的关键字,即查找失败。
 
注意:
 ①
用开放定址法建立散列表时,建表前须将表中所有单元(更严格地说,是指单元中存储的关键字)置空。
 ②
空单元的表示与具体的应用相关。
   
 按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
1)线性探查法(Linear Probing)
该方法的基本思想是:
     将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(h(key)=d),则最长的探查序列为:
        d
d+ld+2m-101d-1
   
 即:探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],直到T[m-1],此后又循环到T[0]T[1],直到探查到T[d-1]为止。

探查过程终止于三种情况:
   
 (1)若当前探查的单元为空,则表示查找失败(若是插入则将key写入其中);
     (2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败;
   
 (3)若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)
利用开放地址法的一般形式,线性探查法的探查序列为:
        hi=(h(key)+i)
m 0≤i≤m-1 //di=i
用线性探测法处理冲突,思路清晰,算法简单,但存在下列缺点:

  处理溢出需另编程序。一般可另外设立一个溢出表,专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表,查找方法可用顺序查找。
  按上述算法建立起来的哈希表,删除工作非常困难。假如要从哈希表 HT 中删除一个记录,按理应将这个记录所在位置置为空,但我们不能这样做,而只能标上已被删除的标记,否则,将会影响以后的查找。
  线性探测法很容易产生堆聚现象。所谓堆聚现象,就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突,如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ,则当新的记录加入该表时,与这个序列发生冲突的可能性愈大。因此,哈希地址的较长连续序列比较短连续序列生长得快,这就意味着,一旦出现堆聚 ( 伴随着冲突 ) ,就将引起进一步的堆聚。

2)线性补偿探测法
线性补偿探测法的基本思想是:

  将线性探测的步长从 1 改为 Q ,即将上述算法中的 j (j 1) % m 改为: j (j Q) % m ,而且要求 Q m 是互质的,以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表,就采用此方法来解决冲突,所用表长 m 1321 ,选用 Q 25

3)随机探测
随机探测的基本思想是:

  将线性探测的步长从常数改为随机数,即令: j (j RN) % m ,其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列,将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序,从而可以避免或减少堆聚。基于与线性探测法相同的理由,在线性补偿探测法和随机探测法中,删除一个记录后也要打上删除标记。
2
、拉链法
1)拉链法解决冲突的方法
   
 拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1

2)拉链法的优点
与开放定址法相比,拉链法有如下几个优点:
  拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
  由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
  开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
  在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

3)拉链法的缺点
   
 拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。
    

 

阅读(663) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~