Chinaunix首页 | 论坛 | 博客
  • 博客访问: 924029
  • 博文数量: 376
  • 博客积分: 154
  • 博客等级: 入伍新兵
  • 技术积分: 1558
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-13 08:42
文章分类

全部博文(376)

文章存档

2014年(11)

2013年(88)

2012年(260)

2011年(17)

分类: C/C++

2013-09-17 09:23:14

原文地址:散列表 作者:tianchunlong

散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作,采用直接寻址技术。在理想情况下,无须任何比较就可以找到待查关键字,查找的期望时间为O(1)。

散列表的概念

1、散列表

     设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K(|K|比|U|小得多)。
     散列方法是使用函数h将U映射到表T[0..m-1]的下标上(m=O(|U|))。这样以U中关键字为自变量,以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。
  其中:
     ① h:U→{0,1,2,…,m-1} ,通常称h为散列函数(Hash Function)。散列函数h的作用是压缩待处理的下标范围,使待处理的|U|个值减少到m个值,从而降低空间开销。
     ② T为散列表(Hash Table)。
     ③ h(Ki)(Ki∈U)是关键字为Ki结点存储地址(亦称散列值或散列地址)。
     ④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing)
  

3、散列表的冲突现象
(1)冲突
     两个不同的关键字,由于散列函数值相同,因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。
   【例】上图中的k2≠k5,但h(k2)=h(k5),故k2和K5所在的结点的存储地址相同。

(2)安全避免冲突的条件
     最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件:
①其一是|U|≤m
②其二是选择合适的散列函数。
     这只适用于|U|较小,且关键字均事先已知的情况,此时经过精心设计散列函数h有可能完全避免冲突。

(3)冲突不可能完全避免
     通常情况下,h是一个压缩映像。虽然|K|≤m,但|U|>m,故无论怎样设计h,也不可能完全避免冲突。因此,只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法,使发生冲突的同义词能够存储到表中。

(4)影响冲突的因素
     冲突的频繁程度除了与h相关外,还与表的填满程度相关。
     设m和n分别表示表长和表中填人的结点数,则将α=n/m定义为散列表的装填因子(Load Factor)。α越大,表越满,冲突的机会也越大。通常取α≤1。
 

散列函数的构造方法

1、散列函数的选择有两条标准:简单和均匀。

     简单指散列函数的计算简单快速;
     均匀指对于关键字集合中的任一关键字,散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说,散列函数能将子集K随机均匀地分布在表的地址集{0,1,…,m-1}上,以使冲突最小化。

2、常用散列函数
     为简单起见,假定关键字是定义在自然数集合上。

(1)平方取中法
     具体方法:先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关,所以由此产生的散列地址较为均匀。
   【例】将一组关键字(0100,0110,1010,1001,0111)平方后得
    (0010000,0012100,1020100,1002001,0012321)
   若取表长为1000,则可取中间的三位数作为散列地址集:
    (100,121,201,020,123)。
相应的散列函数用C实现很简单:
int Hash(int key){ //假设key是4位整数
  key*=key; key/=100; //先求平方值,后去掉末尾的两位数
  return key%1000; //取中间三位数作为散列地址返回
 }

(2)除余法

     该方法是最为简单常用的一种方法。它是以表长m来除关键字,取其余数作为散列地址,即 h(key)=key%m
     该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。
   【例】若选m是关键字的基数的幂次,则就等于是选择关键字的最后若干位数字作为地址,而与高位无关。于是高位不同而低位相同的关键字均互为同义词。
   【例】若关键字是十进制整数,其基为10,则当m=100时,159,259,359,…,等均互为同义词。

(3)相乘取整法
     该方法包括两个步骤:首先用关键字key乘上某个常数A(0         
     该方法最大的优点是选取m不再像除余法那样关键。比如,完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用,但对某些值效果会更好。Knuth建议选取
             
     该函数的C代码为:
int Hash(int key){
  double d=key *A; //不妨设A和m已有定义
  return (int)(m*(d-(int)d));//(int)表示强制转换后面的表达式为整数
 }

(4)随机数法
     选择一个随机函数,取关键字的随机函数值为它的散列地址,即
         h(key)=random(key)
   其中random为伪随机函数,但要保证函数值是在0到m-1之间。

处理冲突的方法

     通常有两类方法处理冲突:开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中;后者通常是将互为同义词的结点链成一个单链表,而将此链表的头指针放在散列表T[0..m-1]中。

1、开放定址法
(1)开放地址法解决冲突的方法
     用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的地址则表明表中无待查的关键字,即查找失败。
  注意:
 ①用开放定址法建立散列表时,建表前须将表中所有单元(更严格地说,是指单元中存储的关键字)置空。
 ②空单元的表示与具体的应用相关。
【例】关键字均为非负数时,可用"-1"来表示空单元,而关键字为字符串时,空单元应是空串。
     总之:应该用一个不会出现的关键字来表示空单元。

(2)开放地址法的一般形式
     开放定址法的一般形式为: hi=(h(key)+di)%m 1≤i≤m-1 
其中:
     ①h(key)为散列函数,di为增量序列,m为表长。
     ②h(key)是初始的探查位置,后续的探查位置依次是hl,h2,…,hm-1,即h(key),hl,h2,…,hm-1形成了一个探查序列。
     ③若令开放地址一般形式的i从0开始,并令d0=0,则h0=h(key),则有:
          hi=(h(key)+di)%m 0≤i≤m-1 
       探查序列可简记为hi(0≤i≤m-1)。

(3)开放地址法堆装填因子的要求
     开放定址法要求散列表的装填因子α≤l,实用中取α为0.5到0.9之间的某个值为宜。

(4)形成探测序列的方法
     按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
①线性探查法(Linear Probing)
该方法的基本思想是:

     将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为:
        d,d+l,d+2,…,m-1,0,1,…,d-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

散列表上的运算

     散列表上的运算有查找、插入和删除。其中主要是查找,这是因为散列表的目的主要是用于快速查找,且插入和删除均要用到查找操作。

1、散列表类型说明:
#define NIL -1 //空结点标记依赖于关键字类型,本节假定关键字均为非负整数
#define M 997 //表长度依赖于应用,但一般应根据。确定m为一素数
typedef struct{ //散列表结点类型
  KeyType key;
  InfoType otherinfo; //此类依赖于应用
 }NodeType;
typedef NodeType HashTable[m]; //散列表类型

2、基于开放地址法的查找算法
     散列表的查找过程和建表过程相似。假设给定的值为K,根据建表时设定的散列函数h,计算出散列地址h(K),若表中该地址单元为空,则查找失败;否则将该地址中的结点与给定值K比较。若相等则查找成功,否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去,直到某个地址单元为空(查找失败)或者关键字比较相等(查找成功)为止。

(1)开放地址法一般形式的函数表示
  int Hash(KeyType k,int i)
   { //求在散列表T[0..m-1]中第i次探查的散列地址hi,0≤i≤m-1
    //下面的h是散列函数。Increment是求增量序列的函数,它依赖于解决冲突的方法
     return(h(K)+Increment(i))%m; //Increment(i)相当于是di
   }
    若散列函数用除余法构造,并假设使用线性探查的开放定址法处理冲突,则上述函数中的h(K)和Increment(i)可定义为:
  int h(KeyType K){ //用除余法求K的散列地址
    return K%m;
  }

  int Increment(int i){//用线性探查法求第i个增量di
    return i; //若用二次探查法,则返回i*i
   }

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