已知关键字序列（22，41，53，46，30，13，01，67），散列地址空间大小为11，哈希函数H(key)=3*key%11，采用链地址法解决冲突，请给出构造的哈希表。并计算该表在等概率下的平均查找长度。

根据哈希函数H(key)=3*key%11，求出每个关键字的散列地址：

H(22)=3*22%11=6

H(41)=3*41%11=4

H(53)=3*53%11=4

H(46)=3*46%11=10

H(30)=3*30%11=8

H(13)=3*13%11=7

H(01)=3*01%11=3

H(67)=3*67%11=9

根据散列地址将关键字插入哈希表中，发现关键字41和53的散列地址相同，因此采用链地址法，将它们放在同一个链表中。

构造的哈希表如下：

0：

1：

2：

3：01

4：41→53

5：

6：22

7：13

8：30

9：67

10：46

平均查找长度ASL = (1/8)*[1*(1/8)+2*(2/8)+2*(1/8)+1*(2/8)+1*(1/8)+1*(1/8)] + (1/11)*[1*(1/11)+1*(1/11)]

= 0.875 + 0.1818

= 1.0568

因此，在等概率下，该哈希表的平均查找长度为1.0568。

相关问题

已知关键字序列为{17，77，76，66，10 , 98}，采用线性探测再散列解决冲突， 哈希函数为H（K）= K %11，表长为12。 (1)构造哈希表 (2)求出等概率下查找成功时的平均查找长度。

好的，问题已经记录下来了。现在回答你的问题：

(1) 构造哈希表：

首先，我们需要创建一个12个元素的哈希表，初始状态下所有元素都为空。然后，我们按照哈希函数H(K) = K % 11的规则，将关键字序列中的每个关键字插入到哈希表中。

具体的插入过程如下：

- 17 % 11 = 6，将17插入到哈希表的第6个位置；
- 77 % 11 = 0，将77插入到哈希表的第0个位置；
- 76 % 11 = 1，将76插入到哈希表的第1个位置；
- 66 % 11 = 0，发生冲突，采用线性探测再散列的方法，将66插入到哈希表的第1 + 1 = 2个位置；
- 10 % 11 = 10，将10插入到哈希表的第10个位置；
- 98 % 11 = 3，将98插入到哈希表的第3个位置。

最终得到的哈希表为：

|0|1|2|3|4|5|6|7|8|9|10|11|
|---|---|---|---|---|---|---|---|---|---|---|---|
|77|76|66|98|||17||||10|

(2) 求出等概率下查找成功时的平均查找长度：

假设哈希表中有n个关键字，m个哈希桶，平均查找长度为ASL。由于这是等概率的情况，我们可以采用公式ASL = (1 + (1/1-p))/2来计算。

其中，p为填装因子，即哈希表中已有关键字数目n与哈希桶数目m的比值。在这个例子中，n = 6，m = 12，因此p = n/m = 0.5。

带入公式ASL = (1 + (1/1-p))/2，可得ASL = 1.67。因此，等概率下查找成功时的平均查找长度为1.67。

已知关键字序列为：（75, 33, 52, 41, 12, 88, 66, 27）哈希表长为10，哈希函数为： H(k)=K MOD 7, 解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均查找长度。

首先，我们需要用哈希函数将关键字映射到哈希表中的位置。根据题目给定的哈希函数，得到以下结果：

- 75 → H(75) = 75 mod 7 = 3
- 33 → H(33) = 33 mod 7 = 5
- 52 → H(52) = 52 mod 7 = 3 （冲突，需要线性探测）
- 41 → H(41) = 41 mod 7 = 6
- 12 → H(12) = 12 mod 7 = 5 （冲突，需要线性探测）
- 88 → H(88) = 88 mod 7 = 4
- 66 → H(66) = 66 mod 7 = 3 （冲突，需要线性探测）
- 27 → H(27) = 27 mod 7 = 6 （冲突，需要线性探测）

接下来，我们使用线性探测再散列法来解决冲突。具体方法是，当发生冲突时，在哈希表中查找下一个可用位置，直到找到一个空闲位置为止。在这个例子中，我们得到以下哈希表：

| 位置 | 关键字 |
| ---- | ------ |
| 0 | |
| 1 | |
| 2 | |
| 3 | 75 |
| 4 | 88 |
| 5 | 33 |
| 6 | 52 |
| 7 | 41 |
| 8 | 12 |
| 9 | 27 |

接下来，我们可以计算等概率下查找成功的平均查找长度。假设哈希表中有n个关键字，每个位置被查找的概率相等，即为1/n。设查找成功的平均查找长度为ASL，那么：

ASL = (1/n) * (1 + 2 + ... + n-1 + n/m)

其中，m为哈希表长度，n为关键字个数。在这个例子中，m=10，n=8，因此：

ASL = (1/8) * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8/10)
= 4.375

因此，等概率下查找成功的平均查找长度为4.375。