已知关键字序列（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。

相关问题

已知关键字序列为：（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。

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

(1) 构造哈希表过程如下：

| 位置 | 关键字 |
|------|--------|
| 0 | 44 |
| 1 | 54 |
| 2 | 32 |
| 3 | |
| 4 | 87 |
| 5 | 49 |
| 6 | 27 |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
| 11 | |

注意，第一个关键字 32 映射到位置 10，但该位置已经被关键字 87 占用，因此需要线性探测，依次尝试位置 11、0、1，最终插入到位置 1。

(2) 等概率下查找成功时的平均查找长度为 (1/6) * (1 + 2 + 3 + 4 + 5 + 6) = 3.5。其中，1/6 表示每个关键字被查找的概率相等，1、2、3、4、5、6 表示查找成功时需要探测的位置数。