哈希表的地址区间为0～17，哈希函数为h(key)=K%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18,59}依次存储到哈希表中，则在哈希表中查找元素59需要搜索的次数为( )

首先，我们按照哈希函数 $h(key)=key\mod 17$ 将关键字序列依次插入哈希表中，得到的哈希表如下：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|----|
| | | | | 38| | 18| | 8 | 59| | | | | 72 | 25 | 26 |

其中，冲突的关键字按照线性探测法依次存储在下一个空闲的位置上。

现在，我们来查找关键字 59，按照哈希函数计算出它在哈希表中的位置为 $h(59)=59\mod 17=8$，因此，我们首先检查哈希表的第8个位置，发现存储的关键字为 8，不是我们要查找的关键字 59。

接着，我们按照线性探测法，依次检查哈希表的下一个位置，即第9个位置，发现存储的关键字为 59，找到了要查找的元素。

因此，在哈希表中查找元素 59 需要搜索的次数为 2 次。

相关问题

设哈希表的地址范围为0～17，哈希函数为：h（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列

### 回答1：
问题：

1. 哈希表中哪些位置被占用了？

答：哈希表中被占用的位置为：、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16。

2. 哈希表中哪些位置发生了冲突？

答：哈希表中发生冲突的位置为：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16。

3. 哈希表中每个关键字的存储位置是什么？

答：关键字10存储在位置10，关键字24存储在位置8，关键字32存储在位置，关键字17存储在位置1，关键字31存储在位置15，关键字30存储在位置14，关键字46存储在位置14（线性探测法向后查找），关键字47存储在位置15（线性探测法向后查找），关键字40存储在位置8（线性探测法向后查找），关键字63存储在位置15（线性探测法向后查找），关键字49存储在位置1（线性探测法向后查找）。

4. 哈希表中是否存在空闲位置？

答：哈希表中不存在空闲位置。

### 回答2：
1. 哈希表的长度是多少？
哈希表的长度为18，地址范围是0~17。

2. 如何计算关键字10的哈希值？
根据哈希函数h(key) = key % 18，把关键字10带入计算是h(10) = 10 % 18 = 10。

3. 插入关键字10时，哈希表的对应位置是否已经被占用？
插入关键字10时，哈希表的位置10还没有被占用。

4. 插入关键字10时，哈希表的位置10是否是其最终位置？
插入关键字10时，哈希表的位置10是其最终位置。

5. 插入关键字24时，哈希表的对应位置是否已经被占用？
插入关键字24时，哈希表的位置6还没有被占用。

6. 插入关键字24时，哈希表的位置6是否是其最终位置？
插入关键字24时，哈希表的位置6是其最终位置。

7. 插入关键字32时，哈希表的对应位置是否已经被占用？
插入关键字32时，哈希表的位置14还没有被占用。

8. 插入关键字32时，哈希表的位置14是否是其最终位置？
插入关键字32时，哈希表的位置14是其最终位置。

9. 插入关键字17时，哈希表的对应位置是否已经被占用？
插入关键字17时，哈希表的位置17还没有被占用。

10. 插入关键字17时，哈希表的位置17是否是其最终位置？
插入关键字17时，哈希表的位置17是其最终位置。

11. 插入关键字31时，哈希表的对应位置是否已经被占用？
插入关键字31时，哈希表的位置13还没有被占用。

12. 插入关键字31时，哈希表的位置13是否是其最终位置？
插入关键字31时，哈希表的位置13是其最终位置。

13. 哈希表中最终插入了几个关键字？
哈希表中最终插入了11个关键字。

14. 哈希表中位置为40的槽是否被占用？
哈希表中位置为40的槽没有被占用。

15. 哈希表中位置为40的槽是否可以插入关键字？
哈希表中位置为40的槽可以插入关键字。

16. 哈希表中位置为49的槽是否被占用？
哈希表中位置为49的槽没有被占用。

17. 哈希表中位置为49的槽是否可以插入关键字？
哈希表中位置为49的槽可以插入关键字。

18. 构造的哈希表如下：
0: 空
1: 空
2: 空
3: 空
4: 空
5: 空
6: 24
7: 空
8: 空
9: 10
10: 40
11: 空
12: 30
13: 31
14: 32
15: 17
16: 空
17: 63
18: 46
19: 47
20: 49

注意：这个哈希表是在处理冲突时使用线性探测法构建的，所以有的位置可能不是最初计算的哈希值，而是后续线性探测的结果。

### 回答3：
1. 构造哈希表的过程为：

初始时，将哈希表中所有的地址都设为空。

首先，将关键字10插入哈希表中，由于h(10)=10，在哈希表中的地址10为空，所以将10插入该地址。

接下来，插入关键字24，由于h(24)=24，地址24为空，将24插入该地址。

再插入关键字32，h(32)=32，地址32为空，将32插入。

对于关键字17，h(17)=17，但地址17不为空，发生冲突。根据线性探测法，从地址17开始逐个往后探测，直到找到一个空的地址，插入关键字17。

依次插入关键字31、30、46、47、40、63、49，根据哈希函数计算地址，并遇到冲突时使用线性探测法将关键字插入对应的地址。最终构造出的哈希表为：

0: 40
1: 63
2: 32
3: 17
4: 47
5: 30
6: 10
7: 49
8:
9:
10: 24
11: 46
12:
13:
14: 31
15:
16:
17:

2. 这个哈希表中有多少个关键字？

根据构造的哈希表，可以看到有11个关键字已经插入成功。

3. 使用线性探测法处理冲突时，最多需要探测几次？

由于哈希表的地址范围是0～17，而输入的关键字序列中最大的关键字是63，所以最多需要探测的次数为17次。

4. 如果输入的关键字序列中有关键字73，应该将其插入哈希表的哪个位置？

根据哈希函数h(key)=key%18，可计算出关键字73对应的地址为73%18=1。因此，将关键字73插入哈希表的位置为地址1。但由于该地址已经被关键字63占用，发生冲突。根据线性探测法，需要从地址1开始逐个往后探测，直到找到一个空的地址，插入关键字73。

设散列表的地址范围为0~17散列函数为H（key）=key%16，用线性探测法处理冲突输入关键字序列（10,24,32,17,31,30,46,47,40,63,49）画出线性探测，链地址法，哈希表三个图

好的，我会根据你的要求进行处理。首先，我们来看一下线性探测法处理冲突的过程。

1. 散列函数 H(key) = key % 16

2. 输入关键字序列（10,24,32,17,31,30,46,47,40,63,49）

3. 用线性探测法进行处理，发生冲突的关键字在散列表中依次向后查找，直到找到一个空的位置为止。

下面是线性探测法处理冲突的图示：

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
----------------------------------------------------------------------------
0 |10|24|32|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
1 |17|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
2 |31|30|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
3 |46|47|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
4 |40|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
5 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
6 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
7 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
8 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
9 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
10|   |   |   |   |   |   |   |   |   |   |49 |   |   |   |   |   |   |63 |
----------------------------------------------------------------------------

接下来，我们再来看一下链地址法处理冲突的过程。

1. 散列函数 H(key) = key % 16

2. 输入关键字序列（10,24,32,17,31,30,46,47,40,63,49）

3. 用链地址法进行处理，发生冲突的关键字在散列表中的位置上形成一个链表，每个链表节点存储一个关键字。

下面是链地址法处理冲突的图示：

0 -> 10 -> 40
1 -> 17
2 -> 32 -> 47
3 -> 63
4
5 -> 30 -> 46
6
7 -> 31
8
9 -> 24
10
11
12
13
14
15
16
17

最后，我们再来看一下哈希表处理冲突的过程。

1. 散列函数 H(key) = key % 16

2. 输入关键字序列（10,24,32,17,31,30,46,47,40,63,49）

3. 用哈希表进行处理，发生冲突的关键字在散列表中的位置上形成一个链表，每个链表节点存储一个关键字。

下面是哈希表处理冲突的图示：

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
----------------------------------------------------------------------------
0 |10|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
1 |   |   |32|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
2 |   |   |   |   |   |30 |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
3 |   |   |   |17 |   |   |46 |47 |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
4 |   |   |   |   |31 |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
5 |   |24 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
6 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
7 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
8 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
9 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
----------------------------------------------------------------------------
10|   |   |   |   |   |   |   |   |   |49 |   |   |   |   |   |40 |   |63 |
----------------------------------------------------------------------------