已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17}，哈希表长为13，哈希函数为h(key)=key%13，请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表，并计算查找成功时的平均查找长度。

线性探测再散列：
哈希表长为13，哈希函数为h(key)=key%13。
插入关键字序列{5,88,12,56,71,28,33,43,93,17}，得到哈希表为：
: 71
1: 12
2: 93
3: 33
4: 43
5: 5
6: 56
7: 28
8: 17
9: 88
10:
11:
12:

查找成功时的平均查找长度为(1+2+3+4+5+6+7+8+9+10)/10=5.5。

二次线性探测再散列：
哈希表长为13，哈希函数为h(key)=key%13。
插入关键字序列{5,88,12,56,71,28,33,43,93,17}，得到哈希表为：
: 71
1: 12
2: 93
3: 33
4: 43
5: 5
6: 56
7: 28
8: 17
9: 88
10:
11:
12:

查找成功时的平均查找长度为(1+2+4+7+11+3+8+12+9+5)/10=6。

链地址法：
哈希表长为13，哈希函数为h(key)=key%13。
插入关键字序列{5,88,12,56,71,28,33,43,93,17}，得到哈希表为：
:
1: 71
2: 12
3: 33 -> 93
4: 43
5: 5
6: 56
7: 28
8: 17
9: 88
10:
11:
12:

查找成功时的平均查找长度为(1+1+2+1+1+1+1+1+1+1)/10=1。

相关问题

已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17}，哈希表长为13，哈希函数为H(key)=key%13，请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表，并计算查找成功时的平均查找长度。 ‌

好的，我来回答你的问题。

对于给定的关键字序列{5,88,12,56,71,28,33,43,93,17}，哈希表长为13，哈希函数为H(key)=key%13，我们可以采用以下三种方法解决冲突：

### 线性探测再散列

首先，我们将关键字序列依次插入哈希表中。对于发生冲突的情况，我们采用线性探测再散列的方法，即顺序查找哈希表中下一个空的位置来存储冲突的关键字。

插入后的哈希表如下所示：

| 下标 | 值 |
| ---- | ---- |
| 0 | |
| 1 | 88 |
| 2 | 12 |
| 3 | 56 |
| 4 | 71 |
| 5 | 28 |
| 6 | 33 |
| 7 | 43 |
| 8 | 93 |
| 9 | |
| 10 | 17 |
| 11 | |
| 12 | 5 |

其中，下标为9和11的位置没有存储任何关键字。

接下来，我们计算查找成功时的平均查找长度。假设我们要查找的关键字为28，它的哈希值为H(28)=28%13=2。首先，在下标为2的位置查找，发现存储的是12而不是28，于是继续往后查找，直到找到28为止。假设我们查找了k次，最终查找到了28，那么平均查找长度为：

ASL = (1/10) * (1 + 2 + … + k) = (k+1)/20

其中，10是关键字的个数，k是查找时查找过的位置数。

### 二次线性探测再散列

同样的，我们将关键字序列依次插入哈希表中。对于发生冲突的情况，我们采用二次线性探测再散列的方法，即按照以下公式来查找下一个空的位置：

H(key, i) = (H(key) + c1*i + c2*i^2) % 13

其中，c1和c2是正整数，i表示第几次探测。

插入后的哈希表如下所示：

| 下标 | 值 |
| ---- | ---- |
| 0 | |
| 1 | 88 |
| 2 | 12 |
| 3 | 56 |
| 4 | 71 |
| 5 | 28 |
| 6 | 33 |
| 7 | 43 |
| 8 | 93 |
| 9 | 17 |
| 10 | |
| 11 | |
| 12 | 5 |

其中，下标为10和11的位置没有存储任何关键字。

接下来，我们计算查找成功时的平均查找长度。假设我们要查找的关键字为28，它的哈希值为H(28)=28%13=2。首先，在下标为2的位置查找，发现存储的是12而不是28，于是按照二次线性探测再散列的公式计算下一个探测位置，即：

H(28, 1) = (2 + 1 + 1^2) % 13 = 4

然后，在下标为4的位置查找，发现存储的是71而不是28，于是计算下一个探测位置：

H(28, 2) = (2 + 1*2 + 2^2) % 13 = 9

然后，在下标为9的位置查找，发现存储的是17而不是28，最终在下标为5的位置查找到了28。假设我们查找了k次，最终查找到了28，那么平均查找长度为：

ASL = (1/10) * (1 + 2 + … + k) = (k+1)/20

其中，10是关键字的个数，k是查找时查找过的位置数。

### 链地址法

最后，我们采用链地址法来解决冲突。对于每个哈希值，我们都维护一个链表，将所有哈希值为该值的关键字都存储在该链表中。

插入后的哈希表如下所示：

| 下标 | 值 |
| ---- | --------- |
| 0 | |
| 1 | 88 |
| 2 | 12 |
| 3 | 56 |
| 4 | 71 |
| 5 | 28 -> 93 |
| 6 | 33 |
| 7 | 43 |
| 8 | |
| 9 | 17 |
| 10 | |
| 11 | |
| 12 | 5 |

其中，下标为0、8、10和11的位置没有存储任何关键字。

接下来，我们计算查找成功时的平均查找长度。假设我们要查找的关键字为28，它的哈希值为H(28)=28%13=2。首先，在下标为2的链表中查找，发现存储的是12而不是28，于是继续往后查找，直到找到28为止。假设我们查找了k次，最终查找到了28，那么平均查找长度为：

ASL = (1/10) * (1 + 2 + … + k) = (k+1)/20

其中，10是关键字的个数，k是查找时查找过的位置数。

综上所述，无论采用哪种方法，当查找成功时的平均查找长度都为(k+1)/20，其中k是查找时查找过的位置数。

( 已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17},哈希表长为 13,哈希函数为H(key)=key%13,请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表,并计算查找成功时的平均查找长度。

好的，我会根据你的要求进行计算和构造哈希表。首先，我们可以根据哈希函数H(key)=key%13来确定每个关键字所在的桶号。下面依次介绍三种解决冲突的方法。

1. 线性探测再散列

线性探测再散列是一种常用的解决哈希冲突的方法，具体实现方式是：当插入一个关键字时，如果发现该位置已被占用，则向后依次查找下一个位置，直到找到一个空闲位置为止。这里我们使用线性探测再散列来构造哈希表。

首先，我们可以将每个关键字根据哈希函数H(key)=key%13计算出它所在的桶号，然后将关键字插入到对应的桶中。如果发现该桶已被占用，则向后依次查找下一个位置，直到找到一个空闲位置为止。

经过这样的操作，得到的哈希表如下所示：

桶号    关键字
0      88
1      43
2      93
3      12
4      56
5      71
6      28
7      33
8      5
9      17
10     -
11     -
12     -

其中，"-"表示该位置为空。

为了计算查找成功时的平均查找长度，我们需要先确定各个关键字的查找长度，然后求它们的平均值。对于成功查找的关键字，它的查找长度就是它在哈希表中的位置。因此，可以得到各个关键字的查找长度如下：

88: 1
43: 1
93: 1
12: 1
56: 1
71: 1
28: 1
33: 1
5: 1
17: 1

因此，这组关键字的平均查找长度为1。

2. 二次线性探测再散列

二次线性探测再散列是一种改进的线性探测再散列方法，具体实现方式是：当插入一个关键字时，如果发现该位置已被占用，则向后依次查找下一个位置，直到找到一个空闲位置为止。这里我们使用二次线性探测再散列来构造哈希表。

首先，我们可以将每个关键字根据哈希函数H(key)=key%13计算出它所在的桶号，然后将关键字插入到对应的桶中。如果发现该桶已被占用，则使用二次探测再散列的方法来查找下一个位置。具体来说，如果第i次查找时，发现桶H(key)+i^2已被占用，则继续向后查找，直到找到一个空闲位置为止。

经过这样的操作，得到的哈希表如下所示：

桶号    关键字
0      88
1      43
2      93
3      12
4      56
5      71
6      28
7      33
8      5
9      17
10     -
11     -
12     -

其中，"-"表示该位置为空。

为了计算查找成功时的平均查找长度，我们需要先确定各个关键字的查找长度，然后求它们的平均值。对于成功查找的关键字，它的查找长度就是它在哈希表中的位置。因此，可以得到各个关键字的查找长度如下：

88: 1
43: 1
93: 1
12: 1
56: 1
71: 1
28: 1
33: 1
5: 1
17: 1

因此，这组关键字的平均查找长度为1。

3. 链地址法

链地址法是一种常用的解决哈希冲突的方法，具体实现方式是：当插入一个关键字时，将它插入到对应桶的链表中。如果出现多个关键字映射到同一个桶中，就将它们插入到同一个链表中。

首先，我们可以将每个关键字根据哈希函数H(key)=key%13计算出它所在的桶号，然后将关键字插入到对应的桶中。如果发现该桶已经有关键字了，则将新的关键字插入到该桶对应的链表中。

经过这样的操作，得到的哈希表如下所示：

桶号    关键字
0      88
1      43 -> 71
2      93
3      12 -> 33
4      56
5      -
6      28
7      -
8      5
9      17
10     -
11     -
12     -

其中，"->"表示链表指针。

为了计算查找成功时的平均查找长度，我们需要先确定各个关键字的查找长度，然后求它们的平均值。对于成功查找的关键字，它的查找长度就是它在链表中的位置。因此，可以得到各个关键字的查找长度如下：

88: 1
43: 1
93: 1
12: 1
56: 1
71: 2
28: 1
33: 2
5: 1
17: 1

因此，这组关键字的平均查找长度为1.2。

综上所述，根据这组关键字构造的哈希表中，三种解决冲突的方法中，平均查找长度最短的是线性探测再散列和二次线性探测再散列，它们的平均查找长度均为1，而链地址法的平均查找长度稍长，为1.2。