已知一组初始记录关键字序列为（35,20,33,48,59,47,62,50,48)。其哈希函数为H（key)=key%13处理中突的方法为排地址 法。 试求：（1)画出哈希表。 （2)计算等概率查找时查找成功的平均查找长度。

(1) 哈希表：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----- | --- | --- | --- | --- | ----- | --- | --- | ----- |
| | 35 | 33 | 62 | | 47,20 | | | 50,48 |
| | | | 48 | | 59 | | | |

(2) 计算等概率查找时查找成功的平均查找长度：

- 对于已经存储的记录：
- 35：在哈希表的位置0，平均查找长度为1。
- 20、33、47、48、50、59、62：在哈希表的位置5或8，平均查找长度为1。
- 对于不在哈希表中的记录：
- 34：哈希函数为H(34)=34%9=7，但位置7为空，平均查找长度为1。
- 60：哈希函数为H(60)=60%9=6，但位置6为空，平均查找长度为1。

因此，等概率查找时查找成功的平均查找长度为：
$$\frac{1+7\times 1+2\times 1}{9}=1.22$$

相关问题

.已知一组关键字为(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：

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

已知一组关键字序列为{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。