Chinaunix首页 | 论坛 | 博客
  • 博客访问: 6270038
  • 博文数量: 2759
  • 博客积分: 1021
  • 博客等级: 中士
  • 技术积分: 4091
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-11 14:14
文章分类

全部博文(2759)

文章存档

2019年(1)

2017年(84)

2016年(196)

2015年(204)

2014年(636)

2013年(1176)

2012年(463)

分类:

2012-05-06 04:04:30

原文地址:哈希表线性探测举例 作者:sillyboytao

利用线性探测法构造哈希表

      已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
  解答:为了减少冲突,通常令装填因子α     由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。
     前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[0],T[10),T[2],T[12]和T[5]中。
     当插入第6个关键字15时,其散列地址2(即h(15)=15%13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)%13=3,此地址开放,所以将15放入T[3]中。
     当插入第7个关键字68时,其散列地址3已被非同义词15先占用,故将其插入到T[4]中。
     当插入第8个关键字12时,散列地址12已被同义词38占用,故探查hl=(12+1)%13=0,而T[0]亦被26占用,再探查h2=(12+2)%13=1,此地址开放,可将12插入其中。
     类似地,第9个关键字06直接插入T[6]中;而最后一个关键字51插人时,因探查的地址12,0,1,…,6均非空,故51插入T[7]中。

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