选取哈希函数h(k)=(3k)%11

哈希函数h(k)=(3k)%11的意思是将关键字k乘以3，然后对11取余数，得到的余数就是哈希表中的位置。这个哈希函数的特点是简单、快速，适用于关键字分布比较均匀的情况。但是，如果关键字分布不均匀，就可能会出现哈希冲突，影响哈希表的性能。因此，在实际应用中，需要根据具体情况选择合适的哈希函数。

相关问题

选取哈希函数H(k)=(3k)%11,采用开放定址法处理冲突，di=i（(7k)%10+1）,i=1,2,3,4,...在0-10的散列地址空间中，依次存放如下关键字22，41，53，46，30，13，01，67.请画出最后的哈希表。

首先，我们需要对给定的关键字进行哈希，具体方法是将关键字 k 带入哈希函数 H(k)，得到散列地址：

- H(22) = (3 * 22) % 11 = 8
- H(41) = (3 * 41) % 11 = 8
- H(53) = (3 * 53) % 11 = 4
- H(46) = (3 * 46) % 11 = 8
- H(30) = (3 * 30) % 11 = 8
- H(13) = (3 * 13) % 11 = 6
- H(01) = (3 * 1) % 11 = 3
- H(67) = (3 * 67) % 11 = 8

我们可以看到，关键字 41、46、30 和 67 都被哈希到了散列地址 8，发生了冲突。因此，我们需要采用开放定址法来处理冲突，具体方法是根据 di 的值依次查找下一个空闲的散列地址，直到找到一个空闲的地址为止。

根据给定的公式 di = i * ((7k % 10) + 1)，可以计算出每个关键字的 di 值：

- d22 = 1
- d41 = 2
- d53 = 3
- d46 = 4
- d30 = 5
- d13 = 6
- d01 = 7
- d67 = 8

接下来，我们可以依次将关键字存放到散列表中，具体过程如下：

1. 将关键字 22 存放到散列地址 8 中。

2. 将关键字 41 存放到散列地址 9 中。

3. 将关键字 53 存放到散列地址 4 中。

4. 将关键字 46 存放到散列地址 0 中。

5. 将关键字 30 存放到散列地址 2 中。

6. 将关键字 13 存放到散列地址 6 中。

7. 将关键字 01 存放到散列地址 3 中。

8. 将关键字 67 存放到散列地址 1 中。

最终哈希表的状态如下：

|散列地址|关键字|
|--------|------|
|0 |46 |
|1 |67 |
|2 |30 |
|3 |01 |
|4 |53 |
|5 | |
|6 |13 |
|7 | |
|8 |22 |
|9 |41 |
|10 | |

选取哈希函数H(k)=(3k) MOD 11。用开放定址法处理冲突，di= i((7k) MOD 10+1) (i=1,2,3, …)。试在0~10的散列地址空间中对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)造哈希表，并求等概率情况下查找成功时的平均查找长度

按照哈希函数H(k)=(3k) MOD 11，可以得到关键字对应的散列地址如下：

- H(22) = 2
- H(41) = 7
- H(53) = 8
- H(46) = 7（冲突）
- H(30) = 9
- H(13) = 6
- H(01) = 3
- H(67) = 10

由于关键字46和关键字41的散列地址相同，因此需要处理冲突。按照开放定址法，可以得到它们的探测序列如下：

- d1(46) = 8
- d2(46) = 10
- d3(46) = 2
- d4(46) = 4
- d5(46) = 6
- d6(46) = 9
- d7(46) = 1
- d1(41) = 5
- d2(41) = 7
- d3(41) = 9
- d4(41) = 1
- d5(41) = 3
- d6(41) = 6
- d7(41) = 8

最终得到的哈希表如下：

| 散列地址 | 关键字 |
| ------- | ------ |
| 0 | |
| 1 | 67 |
| 2 | 22 |
| 3 | 01 |
| 4 | 46 |
| 5 | 41 |
| 6 | 13 |
| 7 | 41 |
| 8 | 53 |
| 9 | 30 |
| 10 | |

等概率情况下查找成功时的平均查找长度ASL可以通过以下公式计算：

ASL = (p1 * 1) + (p2 * 2) + ... + (pi * i)

其中pi表示表中有i个关键字的概率。在本题中，共有8个关键字，因此pi的取值如下：

- p0 = 0.25（0个关键字的概率）
- p1 = 0.25（1个关键字的概率）
- p2 = 0.25（2个关键字的概率）
- p3 = 0.125（3个关键字的概率）
- p4 = 0.0625（4个关键字的概率）
- p5 = 0.03125（5个关键字的概率）
- p6 = 0.015625（6个关键字的概率）
- p7 = 0.015625（7个关键字的概率）

根据散列表中各关键字的探测序列，可以得到每个关键字在表中的位置和需要比较的次数，如下：

- 22：2（1次比较）
- 41：5（1次比较）
- 53：8（1次比较）
- 46：4（6次比较）
- 30：9（1次比较）
- 13：6（1次比较）
- 01：3（1次比较）
- 67：1（1次比较）

因此，ASL的计算如下：

ASL = (0.25 * 0) + (0.25 * 1) + (0.25 * 2) + (0.125 * 3) + (0.0625 * 4) + (0.03125 * 5) + (0.015625 * 6) + (0.015625 * 7) = 2.546875

因此，等概率情况下查找成功时的平均查找长度ASL为2.546875。