已知一组关键字为(16,74,60,43,90,46,31,29,88,77,66,09,地址空间为0至12,哈希函数取H(key)=key%13 (1)写出用链地址处理冲突构造哈希表 (2)写出用线性探测再散列处理冲突构造哈希表

(1) 使用链地址处理冲突构造哈希表的方法：

首先，创建一个大小为13的空哈希表，用于存储关键字。

接下来，对于每个关键字，计算其哈希值（使用哈希函数H(key)=key%13），并将其插入到哈希表中对应的链表中。

如果哈希表中对应位置已经存在其他关键字，则将该关键字添加到链表的末尾。

最终，哈希表的结构如下：

0: 60 -> 29
1:
2: 16 -> 90
3: 43 -> 77
4: 74 -> 88
5: 46
6: 31
7:
8:
9: 66 -> 09
10:
11:
12:

(2) 使用线性探测再散列处理冲突构造哈希表的方法：

首先，创建一个大小为13的空哈希表，用于存储关键字。

对于每个关键字，计算其哈希值（使用哈希函数H(key)=key%13）。

如果哈希表中对应位置为空，则将该关键字插入到该位置。

如果哈希表中对应位置已经存在其他关键字，则使用线性探测的方法，依次检查下一个位置是否为空，直到找到一个空位置为止，并将该关键字插入到该位置。

如果哈希表中已经没有更多的空位置，则需要进行再散列操作。在再散列操作中，首先创建一个更大的哈希表，并将所有已经插入的关键字重新插入到新哈希表中。

最终，哈希表的结构如下：

0: 60
1: 16
2: 74
3: 43 -> 46
4: 90
5: 31 -> 77
6: 29 -> 88
7:
8:
9: 66
10:09
11:
12:

相关问题

.已知一组关键字为(15,28,33,47,52,66,78),采用链地址法处理中卖,暂麦是一个下以d

链地址法是一种常见的哈希表处理冲突的方法。在链地址法中，我们使用一个数组来存储关键字的哈希值，并将哈希值相同的关键字存储在同一个链表中。

对于给定的关键字组(15,28,33,47,52,66,78)，我们可以使用链地址法处理如下：

1. 创建一个长度为N的数组，N是预估的关键字的最大数量。在本例中，最大的关键字是78，所以可以选择数组长度为80。
2. 将关键字通过哈希函数转化为哈希值，并将哈希值取余N，得到关键字在数组中的索引。
- 假设我们使用简单的哈希函数，将关键字除以N，然后取余。
3. 在数组中，为每个索引位置创建一个链表。
4. 遍历关键字组，对于每个关键字，计算其哈希值，并将其插入到对应索引位置的链表中。

使用链地址法处理给定关键字组(15,28,33,47,52,66,78)的过程如下：

1. 创建一个长度为80的数组。数组的每个元素都是链表的头指针，初始值为null。
2. 遍历关键字组：
- 对于关键字15，计算哈希值为15，将其插入到索引为15的链表中。
- 对于关键字28，计算哈希值为28，将其插入到索引为28的链表中。
- 对于关键字33，计算哈希值为33，将其插入到索引为33的链表中。
- 对于关键字47，计算哈希值为47，将其插入到索引为47的链表中。
- 对于关键字52，计算哈希值为52，将其插入到索引为52的链表中。
- 对于关键字66，计算哈希值为66，将其插入到索引为66的链表中。
- 对于关键字78，计算哈希值为78，将其插入到索引为78的链表中。
3. 最终的数组如下：
- 索引0：
- 索引1：
- 索引2：
- ...
- 索引14：
- 索引15：15 -> null
- 索引16：
- ...
- 索引27：
- 索引28：28 -> null
- ...
- 索引32：
- 索引33：33 -> null
- ...
- 索引46：
- 索引47：47 -> null
- ...
- 索引51：
- 索引52：52 -> null
- ...
- 索引65：
- 索引66：66 -> null
- ...
- 索引77：
- 索引78：78 -> null
- ...
- 索引79：

通过链地址法，我们可以很快地找到给定关键字所对应的链表，从而快速进行查找、插入和删除操作。