设哈希函数H(K)=3 K mod 11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按线性探测解决冲突的方法构造哈希表,将下表中缺失的内容补齐。并求出等概率下查找成功时的平均查找长度ASLsucc填入第10空中(用小数表示)。
时间: 2024-05-18 07:12:37 浏览: 45
按照线性探测的方法,当哈希函数H(K)的值为i时发生了冲突,就检查H(K)+1,H(K)+2,...,直到找到一个空闲位置为止。下面是构造哈希表的过程:
|地址|关键字|是否占用|
|:-:|:-:|:-:|
|0|21|1|
|1|4|1|
|2|32|1|
|3|13|1|
|4|24|1|
|5|38|1|
|6||0|
|7||0|
|8||0|
|9|49|1|
|10|12|1|
因为哈希函数H(K)=3 K mod 11,所以我们将关键字32放在地址2,关键字13放在地址3,关键字49放在地址9,关键字24放在地址4,关键字38放在地址5,关键字21放在地址0,关键字4放在地址1,关键字12放在地址10。
根据构造出的哈希表,查找成功时的平均查找长度ASLsucc为:ASLsucc = (1/8)*(1+2+3+4+5+6+7+8) = 4.5
所以,将4.5填入第10空中。
相关问题
3.设哈希函数H(K)+=3K+mod+11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按线性探测法解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和
按照线性探测法解决冲突的方法构造哈希表的步骤如下:
1. 初始化哈希表,将所有位置都置为空。
2. 对于关键字序列中的每一个关键字,计算其哈希地址。
3. 如果该地址为空,则将该关键字存入该地址中;否则,使用线性探测法解决冲突,即依次检查该地址后面的位置,直到找到一个空位置为止,将该关键字存入该位置中。
4. 如果哈希表已满,则无法再插入新的关键字。
对于关键字序列(32,13,49,24,38,21,4,12),按照上述方法构造哈希表的过程如下:
|地址|关键字|
|----|----|
|0 | |
|1 | |
|2 | |
|3 | |
|4 |32 |
|5 |13 |
|6 |49 |
|7 |24 |
|8 |38 |
|9 |21 |
|10 |4 |
其中,哈希地址的计算公式为:H(K) = (3K + mod) % 11,mod为一个常数,这里取1。
等概率情况下查找成功的查找长度为:(1+2+3+4+5+6+7+8)/8 = 4.5。
设哈希函数h(k)=3 k mod 11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失
败时的平均查找长度。
方法一:线性探测法
构造哈希表:
哈希地址 1 2 3 4 5 6 7 8 9 10
关键字 - - - - 32 13 49 24 38 21 4
平均查找长度:
查找成功时:(1/11)*(1+2+3+4+5+6+7+8+9+10+11) = 6
查找失败时:(1/11)*(1+2+3+4+5+6+7+8+9+10+11) = 6
方法二:链地址法
构造哈希表:
哈希地址 1 2 3 4 5 6 7 8 9 10
关键字 - - - - 32 13 49 24 38 21 4
平均查找长度:
查找成功时:(1/11)*(1+1+1+1+2+2+1+2+2+2+1) = 1.45
查找失败时:(1/11)*(1+2+2+2+3+3+3+3+3+3+3) = 2.45