酱坛子

专注C++技术 在这里写下自己的学习心得 感悟 和大家讨论 共同进步(欢迎批评!!!)

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  66 Posts :: 16 Stories :: 236 Comments :: 0 Trackbacks

公告

王一伟 湖南商学院毕业 电子信息工程专业

常用链接

留言簿(19)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 382164
  • 排名 - 63

最新随笔

最新评论

阅读排行榜

评论排行榜

哈希表与哈希函数
  哈希查找因使用哈希 (Hash) 函数而得名,哈希函数又叫散列函数,它是一种能把关键字映射成记录存贮地址的函数。
1.哈希表
①它是一种能把关键字映射成记录存贮地址的函数。
②假定数组 HT[0 ~ m-1] 为存贮记录的地址空间, m 为表长,哈希函数 H 以记录的关键字 K 为自变量,计算出对应的函数值 H(K) ,并以它作为关键字 K 所标识的记录在表 HT 中的 ( 相对 ) 地址或索引号,这样产生的记录表 HT 叫做对应于哈希函数 H 的哈希表
③简言之,在哈希表中,关键字为 K 的记录,存贮在 HT[H(K)] 位置。
④哈希函数值 H(K) 称为 K 的哈希地址或散列地址。
    
3、哈希表的冲突现象
(1)冲突
     不同的关键字值,具有相同的哈希地址,因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。
   【例】上图中的k2≠k5,但h(k2)=h(k5),故k2和K5所在的结点的存储地址相同。

(2)安全避免冲突的条件
    如何避免冲突发生,则取决于哈希函数的构造。
    使散列地址均匀地分布在哈希表的整个地址区间内,这样可以避免或减少发生冲突。
    哈希函数的构造,与关键字的长度、哈希表的大小、关键字的实际取值状况等许多因素有关,而且有的因素事前不能确定。所以,避免冲突这并非是件容易做到的事。

(3)冲突不可能完全避免
     由于关键字的值域往往比哈希表的个数大的多,所以哈希函数是一种压缩映射,碰撞是难免的。
   【例】存贮 100 个学生记录,尽管安排 120 个地址空间,但由于学生名 ( 假设不超过 10 个英文字母 ) 的理论个数超过 2610 ,要找到一个哈希函数把 100 个任意的学生名映射成 [0 , 119] 内的不同整数,实际上是不可能的。
   注意:问题在于一旦发生了冲突应如何处理。


构造哈希表
  构造哈希函数的方法很多,这里只介绍一些常用的,计算简便的方法。
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 直接转换成存储地址了。

3.数字分析法
  对各个关键字内部代码的各个码位进行分析。假设有 n 个 d 位的关键字,使用 s 个不同的符号 ( 如,对于十进制数,每一位可能出现的符号有 10 个,即 0 、 1 、 2 、…、 9) ,这 s 个不同的符号在各位上出现的频率不一定相同,它们可能在某些位上分布比较均匀,即每一个符号出现的次数都接近 n/s 次;而在另一些位上分布不均匀。这时,选取其中分布比较均匀的某些位作为哈希函数值 ( 散列地址 ) ,所选取的位数应视存储区地址范围而定,这就是数字分析法。
注意:
  这种方法适合于关键字值中各位字符分布为已知的情况。
例如,给定一组关键字:
K 1 : 542482241
K 2 : 542813678
K 3 : 532228171
K 4 : 542389671
K 5 : 542541577
K 6 : 542985376
K 7 : 542193552

  这里 n = 7 ; d = 9 ; s = 10 。为了衡量各位上 s 个字符分布的均匀度,可采用度量标准: 式中 a ik 表示第 i 个字符在第 k 位上出现的 (k = 1 , 2 ,…, d) 次数。λ k 值越小,可认为分布越均匀。这里,自左向右,各位上字符的分布均匀度为:
λ 1 = (7 - 7/10) 2 + 9 × (0 - 7/10) 2 = 44.1
λ 2 = 44.1
λ 3 = 44.1
λ 4 = 7 × (1-7/10) 2 + 3 × (0 - 7/10) 2 = 2.1
λ 5 = 4 × (1-7/10) 2 + (3 - 7/10) 2 + 5 × (0-7/10) 2 = 8.1
λ 6 = 5 × (1-7/10) 2 + (2 - 7/10) 2 + 4 × (0-7/10) 2 = 4.1
λ 7 = 3 × (1-7/10) 2 + 2 × (2 - 7/10) 2 + 5 × (0-7/10) 2 = 6.1
λ 8 = 2 × (1-7/10) 2 + (5 - 7/10) 2 + 7 × (0-7/10) 2 = 22.1
λ 9 = 4 × (1-7/10) 2 + (3 - 7/10) 2 + 5 × (0-7/10) 2 = 8.1
  假定存储区地址为 000 ~ 999 ,则应取关键字的第 4 、 6 、 7 位作为哈希函数值 ( 散列地址 ) ,它们分别为 422 、 836 、 281 、 396 、 515 、 953 和 135 。由于数字分析法需预先知道各位上字符的分布情况,这就大大限制了它的实用性。

   构造哈希函数除了上面介绍的几种常用方法外,还有截段法,即截取关键字中的某一段数码作为哈希函数;分段迭加法,即把关键字的机内代码分成几段,再进行迭加 ( 可以是算术加,也可以是按位加 ) 得到哈希函数值。对于各种构造哈希函数的方法,很难一概而论地评价其优劣,任何一种哈希函数都应当用实际数据去测试它的均匀性,才能做出正确的判断和结论。


解决冲突的主要方法
  虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是哈希技术中的两个重要问题。
1、开放定址法
     用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的地址则表明表中无待查的关键字,即查找失败。
  注意:
 ①用开放定址法建立散列表时,建表前须将表中所有单元(更严格地说,是指单元中存储的关键字)置空。
 ②空单元的表示与具体的应用相关。
     按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
(1)线性探查法(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
用线性探测法处理冲突,思路清晰,算法简单,但存在下列缺点:
  ① 处理溢出需另编程序。一般可另外设立一个溢出表,专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表,查找方法可用顺序查找。
  ② 按上述算法建立起来的哈希表,删除工作非常困难。假如要从哈希表 HT 中删除一个记录,按理应将这个记录所在位置置为空,但我们不能这样做,而只能标上已被删除的标记,否则,将会影响以后的查找。
  ③ 线性探测法很容易产生堆聚现象。所谓堆聚现象,就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突,如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ,则当新的记录加入该表时,与这个序列发生冲突的可能性愈大。因此,哈希地址的较长连续序列比较短连续序列生长得快,这就意味着,一旦出现堆聚 ( 伴随着冲突 ) ,就将引起进一步的堆聚。
posted on 2007-12-13 17:53 @王一伟 阅读(2281) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理