设哈希表的地址范围为 0~17,哈希函数为:H(k) = k %16。用线性探测法处理冲突, 说明对输入关键字序列{10,24,32,17,31,30,46,47,40,63,49}的哈希造表及查找过 程
时间: 2023-06-18 08:07:24 浏览: 248
首先,我们需要创建一个大小为18的哈希表,其中有17个槽位(地址范围为0~17),每个槽位可以存储一个关键字。
然后,我们使用哈希函数H(k) = k % 16来确定每个关键字的位置。例如,关键字10的哈希值为10 % 16 = 10,因此它应该存储在哈希表的第10个槽位中。
如果一个关键字要插入到哈希表中,但是该槽位已经被占用了,则我们需要使用线性探测法来解决冲突。具体来说,我们从该槽位开始,逐个往后查找,直到找到一个空的槽位为止。例如,当关键字24要插入到哈希表中时,它的哈希值为24 % 16 = 8,但是第8个槽位已经被关键字10占用了。因此,我们需要往后查找,直到找到一个空的槽位。在本例中,我们会发现第9个槽位是空的,因此关键字24应该存储在第9个槽位中。
对于给定的输入关键字序列{10,24,32,17,31,30,46,47,40,63,49},我们可以按照上述方法依次将它们插入到哈希表中。下面是哈希表在插入所有关键字之后的样子:
0 | 40
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 | 10
9 | 24
10 | 32
11 | 17
12 |
13 | 31
14 | 30
15 | 46
16 | 47
17 | 63
现在,如果我们要查找关键字31,我们首先计算它的哈希值为31 % 16 = 15,然后在第15个槽位中查找。我们发现该槽位中存储的是关键字46,因此我们需要往后查找,直到找到关键字31或者遇到一个空的槽位为止。在本例中,我们会发现第16个槽位中存储的是关键字47,第17个槽位中存储的是关键字63,但是第0个槽位中存储的是关键字40,所以我们需要继续往后查找。最终,我们会在第13个槽位中找到关键字31,因此查找成功。