设哈希函数H(K)=3 K mod 11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按线性探测解决冲突的方法构造哈希表,将下表中缺失的内容补齐。并求出等概率下查找成功时的平均查找长度ASLsucc填入第10空中(用小数表示)。
时间: 2024-05-18 10:12:37 浏览: 162
Hash表存储数据,用再散列来解决地址冲突问题,计算平均查找长度,还可以通过Key值查找对应的value
按照线性探测的方法,当哈希函数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空中。
阅读全文