散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?

admin2009-07-15  43

问题 散列表是一种重要的存储方式,在散列表里可快速进行检索。
(1)散列表的基本思想是什么?
(2)常用的散列函数有哪些,请举例说明(至少三个)。
(3)怎样用拉链法和开地址法处理碰撞?

选项

答案(1)散列表的基本思想是;由结点的关键码值决定结点的存储地址。即以关键码值k为自变量,通过一定的函数关系H(称为散列函数),计算出对应的函数值H(k)来,把这个值解释为结点的存储地址,将结点存入该地址中去,检索时,按同样的方法计算出结点的地址,然后到相应的地址中取结点即可。 (2)常用的散列函数有: ①除余法:即选择一个适当的正整数p(通常选p为小散列表存储区域大小的最大素数),用p去除关键码值,取其余数作为地址。 ②折叠法:即将关键码值从某些地方断开,分为几段,折叠相加,作为地址。 ③中平方法:即将关键码值平方,取中间的几位数作为地址。 (3)用拉链法处理碰撞就是给散列表的每个结点增加一个link字段,当碰撞发生时利用link字段拉链,建立链接方式的同义词子表。每个同义词子表的第一个元素都在散列表基本区域中,同义词子表的其他元素的存储又有两种解决方法,一种是建立溢出区,存放各同义词子表的其他元素,另一种是不建立溢出区,同义词子表的其他元素就存放在散列表中没有占用的单元中, 用开地址法处理碰撞就是当碰撞发生时形成一个探查序列,沿着这个序列逐个地址探查,直到找到一个未被占用的地址,将发生碰撞的关键码值存入该地址中。最简单的探查序列是线性探查,即若发生碰撞的地址为d,则探查的地址序列为; d+1,d+2,…,m-1,0,1,…,d-1 其中,m是散列表存储区域的大小,另一种效果更好的探查序列是再散列探查,即用第二个散列函数H2来确定探查序列,若发生碰撞的地址为d,则探查的地址序列为: (d+H2(k))mod m,(d+2H2(k))mod m,(d+3H2(k))mod m,…

解析
转载请注明原文地址:https://kaotiyun.com/show/mRNZ777K
0

最新回复(0)