设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key 00000000% 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程在0到18的散列地址空间中
时间: 2023-06-20 14:08:13 浏览: 80
Hash表存储数据,用再散列来解决地址冲突问题,计算平均查找长度,还可以通过Key值查找对应的value
首先,我们需要创建一个长度为 19 的散列表(0 到 18 的散列地址空间)。
然后,根据散列函数 H(key)=key 00000000% 17,我们可以计算出每个关键字的散列地址:
- 29 -> 13
- 01 -> 1
- 13 -> 13 (冲突,使用线性探测法)
- 15 -> 15
- 56 -> 4
- 20 -> 3
- 87 -> 5
- 27 -> 10
- 69 -> 4 (冲突,使用线性探测法)
- 9 -> 9
- 10 -> 10 (冲突,使用线性探测法)
- 74 -> 8
冲突的关键字按照线性探测法依次向后查找,直到找到空闲的散列地址。
现在,散列表中的数据如下所示:
|散列地址|关键字|
|-|-|
|0||
|1|01|
|2||
|3|20|
|4|56|
|5|87|
|6||
|7||
|8|74|
|9|9|
|10|27|
|11||
|12||
|13|29, 13|
|14||
|15|15|
|16||
|17||
|18||
平均查找度是指查找一个关键字时需要访问的散列单元数的期望值。对于线性探测法,平均查找度可以通过以下公式计算:
- ASL = (1 + 1/2 + 1/3 + ... + 1/n) * (查找成功的关键字数 / 散列表长度)
其中,n 表示散列表长度,查找成功的关键字数为 12,散列表长度为 19。
计算得出 ASL 约为 1.579。
因此,成功查找的平均查找度为 1.579。
阅读全文