使用散列函数H(x)=x mod 11把一个整数值转换成散列表下标,现要把数据1,13,12,34,38,33,27,22插入到散列表中。使用线性探测再散列处理冲突,画出构造的散列表,并计算在等概率的情况下,查找成功时的平均查找长度。
时间: 2023-11-14 20:07:02 浏览: 173
Hash表存储数据,用再散列来解决地址冲突问题,计算平均查找长度,还可以通过Key值查找对应的value
好的,我可以回答你的问题。
首先,我们使用散列函数 $H(x) = x \mod 11$ 将数据插入散列表中。如果发生冲突,我们使用线性探测再散列法解决冲突。具体地,如果散列到的位置已经被占用,就依次向后查找,直到找到一个空位置为止。再次散列时,我们使用另一个散列函数 $H'(x) = (x+1) \mod 11$。
按照上述方法,将数据插入散列表中,得到的散列表如下所示:
```
散列值 数据
0 33
1 34
2 13
3 12
4 38
5 27
6 22
7 1
8 -
9 -
10 -
```
其中,空位置用“-”表示。
接下来,我们计算在等概率的情况下,查找成功时的平均查找长度。由于散列表的大小为11,因此查找成功的概率为 $p = 1/8$。查找成功时的平均查找长度为:
$$
ASL = \frac{1}{p} \sum_{i=1}^{8} i \cdot p_i = 8\left(\frac{1}{8}\cdot1 + \frac{1}{8}\cdot2 + \frac{1}{8}\cdot3 + \frac{1}{8}\cdot4\right) = 2.5
$$
其中,$p_i$ 表示查找成功时,需要查找 $i$ 个位置的概率。
因此,在等概率的情况下,查找成功时的平均查找长度为2.5。
阅读全文