假定对线性表(38,25,74,52,48)进行哈希存储,采用H(K)=K % 7作为哈希函数,采用线性探测法处理冲突,则平均查找长度为________。
时间: 2024-02-26 13:57:18 浏览: 93
根据题目描述,将线性表中的元素存储到哈希表中,哈希函数为 $H(K) = K \mod 7$,采用线性探测法处理冲突。
首先,我们将哈希表初始化为空表,如下图所示:
```
0 1 2 3 4 5 6
-------------
| | | | | | | |
-------------
```
接下来,我们将线性表中的元素按照哈希函数的结果存储到哈希表中。如果存储到的位置已经被占用了,则采用线性探测法向后查找,直到找到一个空闲的位置。具体地,对于第一个元素 38,其哈希函数的结果为 3,因此存储到哈希表的第 3 个位置。对于第二个元素 25,其哈希函数的结果为 4,因此存储到哈希表的第 4 个位置。对于第三个元素 74,其哈希函数的结果为 4,但是哈希表的第 4 个位置已经被占用了,因此采用线性探测法向后查找。发现哈希表的第 5 个位置为空闲的,因此将 74 存储到哈希表的第 5 个位置。对于第四个元素 52,其哈希函数的结果为 3,但是哈希表的第 3 个位置已经被占用了,因此采用线性探测法向后查找。发现哈希表的第 4 和第 5 个位置都被占用了,因此继续向后查找。发现哈希表的第 6 个位置为空闲的,因此将 52 存储到哈希表的第 6 个位置。对于最后一个元素 48,其哈希函数的结果为 6,因此存储到哈希表的第 6 个位置。最终得到的哈希表如下所示:
```
0 1 2 3 4 5 6
-------------
| | | |38|25|74|
-------------
|52| | | | |48|
-------------
```
因此,平均查找长度为:
$$
ASL=\frac{1}{5}(1+1+2+2+1)=\frac{7}{5}=1.4
$$
因此,平均查找长度为 1.4。
阅读全文