设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表。计算查找成功,失败的平均查找长度。 依次给出哈希表地址0--9单元的值

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

首先，按照哈希函数 H(key) = key mod 7，对关键字进行哈希，得到以下结果：

| 关键字 | 哈希值 |
| ------ | ------ |
| 9 | 2 |
| 1 | 1 |
| 23 | 2 |
| 14 | 0 |
| 55 | 6 |
| 20 | 6 |
| 84 | 7 |
| 27 | 6 |

其中，关键字 23 和 27 的哈希值与关键字 9 冲突，因此需要进行解决冲突。

采用开放地址法的线性探测再散列方法，解决冲突的公式为：

Hi = (H(key) + di) mod m

其中，Hi 表示第 i 次探测的地址，di 表示第 i 次探测的增量，m 表示哈希表的长度。

我们从关键字 9 开始插入哈希表。首先，将其插入到地址为 2 的位置。然后，由于关键字 23 的哈希值也为 2，所以需要进行解决冲突。按照上述公式，第一次探测增量为 1，得到地址 3。由于地址 3 已经被占用，所以继续探测，第二次增量为 2，得到地址 5。由于地址 5 也被占用，继续探测，第三次增量为 3，得到地址 1。此时，关键字 23 被插入到地址为 1 的位置。

接下来，按照同样的方式，将其他关键字插入哈希表中。最终，得到的哈希表如下：

| 地址 | 值 |
| ---- | ---- |
| 0 | 14 |
| 1 | 23 |
| 2 | 9 |
| 3 | |
| 4 | 55 |
| 5 | 27 |
| 6 | 20 |
| 7 | 84 |
| 8 | |
| 9 | |

其中，地址为 3 和 8 的位置没有被占用。

接下来，计算查找成功和失败的平均查找长度。

假设要查找的关键字为 key。如果查找成功，平均查找长度为：

ASL = (1/p) * Σni=1(li)

其中，p 表示哈希表中关键字的占有率，即 p = n/m，n 表示哈希表中已有的关键字数量，m 表示哈希表的长度。li 表示查找第 i 个关键字时所需的探测次数。

如果查找失败，平均查找长度为：

ASL = (1/p) * Σni=1(1/2 * (1 + (di/m)))

其中，di 表示第 i 个关键字插入时所探测的距离。

对于本题中的哈希表，已有的关键字数量为 7，长度为 10，因此占有率为 7/10。

我们来计算一下关键字 20 的查找成功长度。根据哈希函数，它的哈希值为 6，因此首先查找地址为 6 的位置。由于该位置已经被占用，因此需要进行探测。第一次探测增量为 1，得到地址 7。由于地址 7 也被占用，继续探测，第二次增量为 2，得到地址 9。此时，找到了关键字 20，共进行了 3 次探测。因此，查找成功的平均查找长度为：

ASL = (1/7) * (3 + 0 + 0 + 0 + 0 + 0 + 0) = 0.4286

接下来，我们来计算一下关键字 15 的查找失败长度。根据哈希函数，它的哈希值为 1，因此首先查找地址为 1 的位置。由于该位置已经被占用，因此需要进行探测。第一次探测增量为 1，得到地址 2。由于地址 2 已经被占用，继续探测，第二次增量为 2，得到地址 4。由于地址 4 已经被占用，继续探测，第三次增量为 3，得到地址 7。此时，发现地址 7 没有被占用，因此认为查找失败。根据公式，查找失败的平均查找长度为：

ASL = (1/7) * (1/2 * (1 + (1/10)) + 1/2 * (1 + (2/10)) + 1/2 * (1 + (3/10))) ≈ 0.2857

最后，依次给出哈希表地址 0--9 单元的值为：

| 地址 | 值 |
| ---- | ---- |
| 0 | 14 |
| 1 | 23 |
| 2 | 9 |
| 3 | |
| 4 | 55 |
| 5 | 27 |
| 6 | 20 |
| 7 | 84 |
| 8 | |
| 9 | |