哈希表二次探测法平均查找长度

根据引用[2]中提到的哈希表的线性探测法和链地址法求查找成功与不成功的平均查找长度，我们可以推导出哈希表二次探测法的平均查找长度。

哈希表二次探测法是一种解决哈希冲突的方法，当发生冲突时，它会通过计算一个二次探测序列来寻找下一个可用的位置。

假设哈希表的大小为m，其中n个元素被插入到哈希表中。当哈希表的负载因子（load factor）为α = n/m 时，平均查找长度ASL可以通过以下公式计算：

ASL = (1 + (1/1-α)) / 2

其中，α表示负载因子。

因此，哈希表二次探测法的平均查找长度可以通过上述公式计算得出。

相关问题

设有一组关键字(9,01,23,14,55, 20,84,27),采用哈希函数:H(key)=k ey%7,表长为10，用开放地址法的二次探测法处理冲突。要求:对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

1. 构造哈希表，采用二次探测法处理冲突。

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

2. 计算查找成功的平均查找长度。

对于每个关键字，它要么在哈希表中，要么不在哈希表中。如果它在哈希表中，那么它肯定是在哈希表的某个位置上；如果它不在哈希表中，那么最终会找到一个空位置。因此，查找成功的平均查找长度ASL = (1/8)*(1+1+1+1+1+1+2+1) = 1.125。其中，8表示关键字的个数，1/8表示每个关键字被查找到的概率相等。

设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

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

首先，我们按照哈希函数 H（key）=key %7 将关键字序列映射到哈希表中：

| 索引 | 哈希值 | 关键字 |
| ---- | ------ | ------ |
| 0 | 9 | |
| 1 | 1 | 01 |
| 2 | 2 | 23 |
| 3 | 3 | 14 |
| 4 | 6 | 20 |
| 5 | 5 | 55 |
| 6 | 0 | |
| 7 | 4 | 27 |
| 8 | 0 | |
| 9 | 4 | 84 |

可以看到，有些索引位置出现了冲突，我们需要使用开放地址法的二次探测法来解决。

对于冲突的关键字 9，我们从索引位置 0 开始探测，发现位置 0 已经被占用，于是我们按照二次探测法的公式，依次探测位置 1、4、2、9，最终在位置 9 找到了一个空闲位置，将关键字 9 存储在该位置。

对于冲突的关键字 20，我们从索引位置 6 开始探测，发现位置 6 已经被占用，于是我们按照二次探测法的公式，依次探测位置 9、4、0、8，最终在位置 8 找到了一个空闲位置，将关键字 20 存储在该位置。

最终哈希表的结果如下：

| 索引 | 哈希值 | 关键字 |
| ---- | ------ | ------ |
| 0 | 9 | 9 |
| 1 | 1 | 01 |
| 2 | 2 | 23 |
| 3 | 3 | 14 |
| 4 | 6 | 20 |
| 5 | 5 | 55 |
| 6 | 0 | |
| 7 | 4 | 27 |
| 8 | 0 | 84 |
| 9 | 4 | |

接下来计算查找成功的平均查找长度。我们假设要查找的关键字为 x，它在哈希表中的位置为 i。

如果 x 存在于表中，则查找成功，平均查找长度为：

ASL = (1 * P1 + 2 * P2 + 3 * P3 + ... + k * Pk) / n

其中，P1、P2、P3 等是查找 x 时经过 1、2、3 次探测的概率，k 是查找 x 时最终经过的探测次数，n 是表中关键字的总数。

根据题目中给出的哈希函数和关键字序列构造哈希表后的结果，我们可以得到以下概率：

P1 = 4/10 = 0.4
P2 = 3/10 = 0.3
P3 = 2/10 = 0.2
P4 = 1/10 = 0.1

如果要查找关键字 23，它的哈希值为 2，经过一次探测就找到了，平均查找长度为 1。

如果要查找关键字 84，它的哈希值为 0，但是位置 0 和位置 8 都存储了关键字，因此需要进行二次探测，最终经过 4 次探测找到了关键字，平均查找长度为：

ASL = (1 * 0.4 + 2 * 0.3 + 3 * 0.2 + 4 * 0.1) / 8 = 1.9 / 8 = 0.2375

因此，查找成功的平均查找长度为 0.2375。