加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

散列表的查找技术

(2013-08-24 17:25:52)
标签:

散列表

查找技术

it

分类: 数据结构

1、何谓散列表

散列表(哈希表)查找又称之为杂凑法。它的基本思想是:设置一个长度为m的表Table,用一个函数H把数据集合中n个记录的关键字唯一地转换成[0,m-1]范围内的数值,即对于集合中任意记录的关键字Ki存在关系:

             0《 H(Ki)《m-1           (1≤i≤n)

这样就可以利用函数H将数据集合中记录映射到表Table中,H(Ki)便是记录Ri在表中的存储位置。我们把建立表与记录关键字之间映射关系的函数H称为散列函数,Table称之为散列表。记录Ri在表中的存储位置H(Ki)称为散列地址(哈希地址)。

2、散列函数

选择散列函数的两个主要准则是:容易实现,而且计算速度快;在整个散列表中尽可能地均匀地存储数据记录。构造散列函数通常采取的方式是将关键字分成多个部分,采取各种方法将它们混合在一起,然后获得散列地址。

下面介绍几种常用的散列函数构造方法。

1 直接定址法

取关键字本身或关键字的某个线性函数作为散列地址。即

H(key)= key   或     H(key)= a*key + b

其中a,b为常数,调整 a与b的值可以使哈希地址取值范围与存储空间范围一致。

【例6-8】关键码集合为{100,300,500,700,800,900},假设选取的散列函数为Hash(key)=key/100,则存放如下:

                                9

 

100

 

300

 

500

 

700

800

900

 

直接定址法的特点是散列函数简单,并且对于不同关键字不会产生冲突。但在实际问题中,关键字集合中元素很少是连续的,该方法产生的散列表会造成空间浪费。因此,这种确定散列地址的方法很少使用。

2 质数除余法

取关键字被某个不大于散列表表长n的质数p整除后所得余数为散列地址。即

H(key)=key % p (p

质数除余法计算简单,但是整数p的选择很重要,如果选择不当,会产生较多同义词,使散列表中有较多的冲突。请看下面例子。

假设取标识符在计算机中的二进制表示为它的关键字(标识符中每个字母均用两位八进制数表示),然后对p=26取模。这个运算在计算机中只要移位便可实现,将关键字左移直至只留下最低的6位二进制数。这等于将关键字的所有高位值都忽略不计。因而使得所有最后一个字符相同的标识符,如at,cat,fat等均成为同义词。

一般选择p为小于散列表长度n的最大素数比较好,例如:

            n = 8,16,32,64,128,256,512,1024

            p = 7,13,31,61,127,251,503,1019

3 平方取中法

取关键字平方后的中间几位为散列地址。由于平方后的中间几位数与原关键字的每一位数字都相关,只要原关键字的分布是随机的,以平方后的中间几位数作为散列地址一定也是随机分布。

【例6-9】假设5位的关键字值key = 42016,利用平方取中法求散列地址的过程:

①求平方得:

                 (key)2 = 1765344256

②取中间的3位作为地址,即h(key)=344。

4折叠法

把关键字折叠成位数相同的几部分,然后取这几部分的叠加作为散列地址。在关键字位数较多,且每一位上数字的分布基本均匀时,采用折叠法,得到的散列地址比较均匀。折叠的方法有移位法和间界叠加法。移位法就是将各部分的最后一位对齐相加。间界叠加法是从一端向另一端沿各部分分界来回折叠后,最后一位对齐相加。

例6-10】一个关键字值用不同的方法分段、折叠、相加,得出不同的地址码。假设关键字key = 582422241,要求转换为4位的地址码。

58︱2422︱241       58︱2422︱241      582︱4222︱41

 


移位折叠相加          移位相加           移位相加

8 5                      5 8                  4 1

 1 4 2                  2 4 1                 5 8 2

2 4 2 2                2 4 2 2                4 2 2 2

h(k) =1 0 6 4                2 7 2 1                4 8 4 5    

5 数字分析法

假设关键字是以r为基的数(如以10为基的十进制数),并且散列表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成散列地址。

例6-11】有8个记录,其关键字为8位十进制数。假设哈希表的表长为1000l0,则可取三位十进制数组成散列地址。取哪三位?原则是使得到的散列地址尽量避免产生冲突,则需从分析这8个关键字着手。假设这8个关键字如下:

K1

0

0

3

1

9

4

2

6

K2

0

0

7

1

8

3

0

9

K3

0

0

6

2

9

4

4

3

K4

0

0

7

5

8

6

1

5

K5

0

0

9

1

9

6

9

7

K6

0

0

3

1

0

3

2

9

K7

0

0

4

5

0

4

5

2

K8

0

0

5

2

7

3

6

8

 

      

 

 

 

 

 

 

 

 

 

分析所有关键字的各位的值,发现第①、②位只出现0;第③位中4、5、6、9各出现1次,3、7各出现2次;第④位中1出现4次,5、2各出现2次;第⑤位中9出现3次,8、0各出现2次;第⑥位中4、3各出现3次,6出现2次;第⑦位中0、1、4、5、6、9均出现1次,2出现2次;第⑧位中6、3、5、7、2、8各出现1次,9出现2次。因此,可以选取关键字的第③、⑦、⑧位组成的值作为其散列地址,得到如下的结果:

H(K1)=326,H(K2)=709,H(K3)=643,H(K4)=715

H(K5)=997,H(K6)=329,H(K7)=452,H(K8)=568

3、冲突解决方案

处理冲突的方法基本上有两类:一类叫做拉链法(或链地址法),另一种方法叫开放定址法。下面分别介绍这两种处理的具体做法。

1 拉链法(链地址法)

所谓拉链法,即通过建立相应的链表解决产生的冲突。若n个关键字映射到基本散列表的m个存储单元上,最多可以建立m个子表,每个关键字的同义词存放在以m个单元为首结点链接的子表中。设基本散列表为A[0,m-1],将所有具有相同散列地址的记录放在同一单链表中,散列表的第i个元素A[i]存放散列地址为i的记录组成的单链表的头指针。

同义词链表建立在什么地方?一种方法是在基本存储区外开辟一个溢出区存储同义词链表。另一种方法是把同义词链表就存放在基本存储区中目前还没有被占用的存储单元中。例如,在基本存储区内从后往前找空单元,找到空单元后就把同义词存进去,并把它链接到同义词链表。

2 开放定址法

开放定址法的基本思想是在冲突产生时,用某种方法在散列表的存储区域内形成一个探测序列,沿这个探测序列逐个单元地查找,直到找到一个开放的地址(没有存储关键字的空单元),然后在该开放地址上插入同义词。找开放地址方法很多,下面介绍三种:

(1)线性探测法

    我们用下式描述:

        Hi (key)=(Hash(key)+di)mod m   

图6-21 拉链法处理冲突时的散列表

   ( 1≤i < m )

其中:Hash(key)为哈希函数,m为哈希表长度,di 为增量序列 1,2,……,m-1,且di = i。

例6-13】设关键码集为 {47,7,29,11,16,92,22,8,3},散列表表长为11,

 Hash(key)= key mod 11,用线性探测法处理冲突,建立的散列表如图6-22所示。

         10

11

22

 

47

92

16

3

7

29

8

 

                   △                  ▲      △ 

图6-22利用线性探测处理冲突时的散列表

其中,47、7、11、16、92均是由散列函数得到的没有冲突的散列地址而直接存入的;对于关键字29,由于Hash(29)=7,与关键字7的散列地址冲突,需寻找下一个空的散列地址:根据H1=(Hash(29)+1) mod 11=8,散列地址8为空,则将29存入。另外,22、8同样在散列地址上也有冲突,也是由H1找到空的散列地址的。我们用空心三角表示经过一次探测的关键字。而对于关键字3,由于Hash(3)=3,散列地址上冲突,再求散列地址H1=(Hash(3)+1) mod 11=4,仍然冲突;第三次求出的散列地址H2=(Hash(3)+2) mod 11=5,仍然冲突;第四次散列H3=(Hash(3)+3) mod 11=6,找到空的散列地址,存入。

    线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址,这样本应存入第i+1个散列地址的元素变成了第i+2个散列地址的同义词,……,因此,可能出现很多元素在相邻的散列地址上“堆积”起来,大大降低了查找效率。为此,可采用二次探测法,或双散列函数探测法,以改善“堆积”问题。

(2)二次探测法

二次探测法与线性探测法的主要区别在于增量序列不同。在二次探测法中,di = 12,-12,22,-22,……,k2,-k2且k≤m/2。

例6-13用二次探测法来处理冲突,则建立散列表如图6-23所示。

对关键码寻找空的散列地址只有3这个关键码与线性探测不同,具体分析如下:按照Hash(3)=3,散列地址上冲突;第一次探测,散列地址为H1=(Hash(3)+12) mod 11=4,仍然冲突;第二次探测,散列地址为H2=(Hash(3)-12) mod 11=2 ,这是一个空的散列地址,则将关键字3存入。

                        10

11

22

3

47

92

16

 

7

29

8

 

                   △  ▲                      △ 

图6-23 二次探测处理冲突示例

(3)双哈希函数探测法

        Hi=(Hash(key)+i * Hashre(key))mod m        (i=1,2,……,m-1)

其中:

           Hash(key),Hashre(key)是两个哈希函数,

           m为哈希表长度

    双哈希函数探测法,先用第一个函数Hash(key)对关键码计算哈希地址,一旦产生地址冲突,再用第二个函数Hashre(key)确定移动的步长因子,最后,通过步长因子序列由探测函数寻找空的哈希地址。

    比如,Hash(key)=a时产生地址冲突,就计算Hashre(key)=b,则探测的地址序列为

         H1=(a+b) mod m,H2=(a+2b) mod m,……,Hm-1=(a+(m-1)b) mod m

 

4、散列表查找及性能分析

从散列表的查找过程可见,虽然散列表在关键字与记录的存储位置之间建立了直接映射关系,但由于“冲突”产生,冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对哈希表查找效率的量度,依然用平均查找长度来衡量。

    查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:哈希函数是否均匀;处理冲突的方法;哈希表的装填因子。

分析这三个因素,尽管哈希函数的“好坏”直接影响冲突产生的频度,但一般情况下,我们总认为所选的哈希函数是“均匀的”,因此,可不考虑哈希函数对平均查找长度的影响。就线性探测法和二次探测法处理冲突的例子看,相同的关键码集合、同样的哈希函数,但在数据元素查找等概率情况下,它们的平均查找长度却不同。例如图6-22和图6-23中的两个散列表,线性探测法的平均查找长度

 ASL=(5×1+3×2+1×4)/9=5/3

二次探测法的平均查找长度

ASL=(5×1+3×2+1×3)/9=14/9

在一般情况下,冲突处理方法相同的散列表,其平均查找长度依赖于散列表的装填因子(Load Factor)。令n为散列表中存储的记录数目,散列表的存储单元个数为t。散列表的装填因子 λ=n/t。这样λ=0表示散列表为空;λ=0.5表示散列表处于半满状态。

散列表的装填因子a=填入表中的记录个数/散列表的长度  

装填因子a标志着散列表装满的程度。

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有