线性探测法在计算等概率情况下查找失败计算公式是什么

线性探测法在计算等概率情况下查找失败时的平均查找长度，可以使用以下公式：

(表长 / 2) * (1 / (1 - α)^2)

其中，表长为散列表的长度，α为填装因子，即已经插入的关键字数目与散列表长度的比值。

这个公式的推导比较复杂，但是可以通过假设每个关键字在散列表中出现的位置是等概率的，并且每个关键字的探测长度也是等概率的来进行推导。最终得到的结果是一个二次函数，与填装因子的平方成正比，这就意味着填装因子越大，查找失败时平均查找长度会增加得更快。

相关问题

设哈希函数h（k）=3 k mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度aslsucc和aslunsucc。 ① 线性探测法； ② 链地址法。

### 回答1：
1. 线性探测法：当哈希函数给出的地址已被占用时，向后依次探测下一个地址是否为空，直到找到空地址或者遍历完整个哈希表。 如果找到空地址，就将该键值存储到该地址；如果遍历完整个哈希表还未找到空地址，则需要重新开始从哈希表的头部开始探测空地址。

2. 链地址法：将哈希表的每个地址看做一个链表，将哈希函数映射到的同一个地址的键值都存储在同一个链表中。当哈希函数给出的地址已被占用时，将新的键值插入到该地址对应的链表尾部即可。

在构造哈希表时，需要根据给定的关键字序列以及哈希函数（h(k)=3k mod 11），依次将关键字映射到哈希表中。对于给定的关键字序列（32，13，49，24，38，21，4，12），可以得到以下哈希表：

0：
1：13，38
2：49
3：21
4：4
5：
6：12，24
7：
8：32
9：
10：

平均查找长度ASL（Average Search Length）指的是在哈希表中查找某个关键字所需要的平均探测次数，ASL可以通过以下公式计算：

ASL = (查找成功时所有关键字探测次数之和 + 查找失败时所有可能查找的探测次数之和) / 关键字总数

对于以上哈希表，ASL为(1 + 2 + 1 + 1 + 1 + 1 + 1 + 2) / 8 = 1.5。

在查找某个关键字时，需要根据哈希函数找到该关键字在哈希表中对应的地址，然后在该地址对应的链表中查找该关键字。如果在链表中找到了该关键字，则查找成功；否则查找失败。

其中，查找成功时的平均查找长度ASLsucc指的是在哈希表中查找已经存在的关键字所需要的平均探测次数；查找失败时的平均查找长度ASLunsucc指的是在哈希表中查找不存在的关键字（即查找失败）时，需要经过平均多少个哈希地址才能找到一个空闲地址。一个成功的查找操作的概率为P，一个查找失败的概率为1-P，平均查找长度可以通过以下公式计算：

ASLsucc = (所有成功的查找操作中所有关键字探测次数之和) / 所有成功的查找次数
ASLunsucc = (所有查找失败的操作中所有可能查找的探测次数之和) / 所有查找失败的次数

其中，一个成功的操作的概率可以通过该关键字在哈希表中出现的频率计算得出，即P=k/n，其中k表示哈希表中该关键字出现的次数，n表示哈希表中关键字的总数。一个失败的操作的概率为1-P。

### 回答2：
哈希表是一种非常常用的数据结构，可用于高效地进行数据的插入、查找和删除等操作。在实际应用中，哈希函数的选取以及冲突解决方式的选择都会对哈希表的性能产生重要影响。

对于给定的哈希函数h(k)=3k mod 11，哈希地址空间为0~10，关键字序列为32、13、49、24、38、21、4、12，我们可以采用两种不同的冲突解决方法来构造哈希表，分别是线性探测法和链地址法。

1. 线性探测法

在线性探测法中，当哈希函数h(k)计算出冲突位置i时，若该位置已被占用，则沿着哈希表依次往后探测，直到找到一个空闲位置j（j≠i）为止。若整张哈希表已被占满，则返回原位置i。

对于给定的关键字序列，我们可以按照如下步骤构造哈希表：

1) 初始化一个大小为11的哈希表，全部赋值为空。
2) 依次插入关键字序列中的每个元素。
3) 对于经过哈希函数h(k)计算出的位置i，若该位置已被占用，则沿着哈希表依次往后探测，直到找到一个空闲位置j（j≠i）为止。若整张哈希表已被占满，则返回原位置i。

根据上述步骤，我们可以得到如下的哈希表：

0 1 2 3 4 5 6 7 8 9 10
13 32 49 21 4 12 24 38

为了求出等概率下查找成功时的平均查找长度aslsucc，我们可以从哈希表中查找每个元素，并求出平均查找长度。由于哈希函数h(k)是等概率的，因此每个元素在哈希表中的等概率位置也是等概率的。因此，对于一个元素，它在哈希表中的查找长度可以看作是一个二项分布的随机变量，平均查找长度aslsucc可以按照如下公式计算：

aslsucc = Σi=1n (成功查找到关键字i的次数 × 成功查找到关键字i时的查找长度) / n

其中，n为关键字序列中元素的数量。根据上述公式，我们可以得到如下计算过程：

aslsucc = (1/8×1+1/8×2+1/8×1+1/8×3+1/8×2+1/8×1+1/8×1+1/8×2) = 1.75

即在线性探测法构造的哈希表中，查找成功时平均需要查找1.75个位置。

为了求出等概率下查找失败时的平均查找长度aslunsucc，我们可以从哈希表中查找一些不存在的元素，并求出平均查找长度。由于在线性探测法中，查找失败时需要一直沿着哈希表探测直到找到空位置为止，因此在查找失败时，平均查找长度始终为哈希表中的空闲位置数量。因此，在此例中，查找失败时平均需要查找3个位置。

2. 链地址法

在链地址法中，哈希表中的每个位置都是一个链表的头结点，当哈希函数计算出冲突位置i时，将新元素插入到链表头结点i的后面即可。

对于给定的关键字序列，我们可以按照如下步骤构造哈希表：

1) 初始化一个大小为11的哈希表，全部赋值为空。
2) 依次插入关键字序列中的每个元素，插入时将其添加到哈希表中对应位置的链表中。

根据上述步骤，我们可以得到如下的哈希表：

0 ->
1 -> 13 -> 21 ->
2 ->
3 -> 32 ->
4 -> 4 -> 24 ->
5 -> 38 ->
6 ->
7 ->
8 ->
9 ->
10-> 49 -> 12 ->

为了求出等概率下查找成功时的平均查找长度aslsucc，我们只需要在哈希表中查找每个元素，并求出平均查找长度。由于链地址法可以避免冲突，每个元素在哈希表中只有一个可能位置，因此查找成功时的平均查找长度与哈希表的填装因子有关。在此例中，哈希表的填装因子为8/11。因此，查找成功时平均需要查找1.818个位置。

为了求出等概率下查找失败时的平均查找长度aslunsucc，在链地址法中查找失败时总是查找到链表的末尾，因此平均查找长度为哈希表中每个位置链表的平均长度。在此例中，哈希表中链表的平均长度为8/11，因此查找失败时平均需要查找0.727个位置。

综上所述，对于本文提到的哈希函数h(k)=3k mod 11，哈希地址空间为0~10，关键字序列为32、13、49、24、38、21、4、12，线性探测法和链地址法的查找成功/失败时平均查找长度如下表所示：

| 线性探测法 | 链地址法 |
----|-------------|-----------|
成功 | 1.75 | 1.818 |
失败 | 3 | 0.727 |

### 回答3：
线性探测法的哈希表构造过程如下：

1. 初始化哈希表，将每个位置都设为“空”。

2. 将第一个关键字32插入哈希表中，根据哈希函数h（32）=3*32 mod 11=10，将其直接插入哈希表中的10位置。

3. 将第二个关键字13插入哈希表中，根据哈希函数h（13）=3*13 mod 11=6，将其插入哈希表中的6位置。

4. 将第三个关键字49插入哈希表中，根据哈希函数h（49）=3*49 mod 11=5，该位置已经有关键字13，发生了冲突。由于哈希地址空间为0～10，因此使用“线性探测法”从下一个位置开始查找。

5. 查找下一个位置，即h（49）+1=6+1=7，发现该位置为空，将49插入该位置。

6. 将第四个关键字24插入哈希表中，根据哈希函数h（24）=3*24 mod 11=9，将其直接插入哈希表中的9位置。

7. 将第五个关键字38插入哈希表中，根据哈希函数h（38）=3*38 mod 11=4，该位置已经有关键字13和49，发生了冲突。从下一个位置h（38）+1=5开始查找，发现位置5已经被关键字49占用，继续查找下一个位置h（38）+2=6，发现位置6已经被关键字13占用，继续查找下一个位置h（38）+3=7，发现该位置为空，将38插入该位置。

8. 将第六个关键字21插入哈希表中，根据哈希函数h（21）=3*21 mod 11=8，将其插入哈希表中的8位置。

9. 将第七个关键字4插入哈希表中，根据哈希函数h（4）=3*4 mod 11=1，将其直接插入哈希表中的1位置。

10. 将最后一个关键字12插入哈希表中，根据哈希函数h（12）=3*12 mod 11=3，将其直接插入哈希表中的3位置。

线性探测法的哈希表如下：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| | 4 | |12 |38 |49 |13 |21 |32 |24 | |

等概率下查找成功时的平均查找长度asl_succ计算方法如下：

asl_succ=Σ（di+1）/n

其中，di为第i个关键字所需查找的次数。n为关键字个数。

查找关键字21的过程如下：

1. 根据哈希函数h（21）=3*21 mod 11=8，查找哈希表的第8个位置，发现关键字21就在该位置。

2. 所需查找次数为1。

由于共有8个关键字，因此asl_succ=(1+1+4+1+3+1+2+1)/8=1.875。

等概率下查找失败时的平均查找长度asl_unsucc计算方法如下：

asl_unsucc=Σ（di+1）/n

其中，di为第i个关键字所需查找的次数。n为哈希地址空间的大小。

根据哈希函数h（k），可以发现同一关键字在哈希表中可能出现的位置数最多为哈希地址空间的大小n。因此，当查找失败时，最多需要查找n次。因此，asl_unsucc=(0+1+2+3+4+5+6+7+8+9+10)/11=5。

链地址法的哈希表构造过程如下：

1. 初始化哈希表，将每个位置都设为“空”。

2. 将第一个关键字32插入哈希表中，根据哈希函数h（32）=3*32 mod 11=10，将其插入哈希表中的第10个位置。

3. 将第二个关键字13插入哈希表中，根据哈希函数h（13）=3*13 mod 11=6，将其插入哈希表中的第6个位置。

4. 将第三个关键字49插入哈希表中，根据哈希函数h（49）=3*49 mod 11=5，将其插入哈希表中的第5个位置。

5. 将第四个关键字24插入哈希表中，根据哈希函数h（24）=3*24 mod 11=9，将其插入哈希表中的第9个位置。

6. 将第五个关键字38插入哈希表中，根据哈希函数h（38）=3*38 mod 11=4，将其插入哈希表中的第4个位置。

7. 将第六个关键字21插入哈希表中，根据哈希函数h（21）=3*21 mod 11=8，将其插入哈希表中的第8个位置。

8. 将第七个关键字4插入哈希表中，根据哈希函数h（4）=3*4 mod 11=1，将其插入哈希表中的第1个位置。

9. 将最后一个关键字12插入哈希表中，根据哈希函数h（12）=3*12 mod 11=3，将其插入哈希表中的第3个位置。

链地址法的哈希表如下：

| 0 | | | 1 | | 5 | 6 | 8 |10 | 9 | |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| | |12 | 4 | |38 |13 |21 |32 |24 |49 |

等概率下查找成功时的平均查找长度asl_succ计算方法如下：

使用链地址法查找关键字21的过程如下：

1. 根据哈希函数h（21）=3*21 mod 11=8，查找哈希表中第8个位置对应的链表，发现关键字21在该链表中。

2. 所需查找次数为1。

由于共有8个关键字，因此asl_succ=(1+1+2+1+1+1+1+1)/8=1.25。

等概率下查找失败时的平均查找长度asl_unsucc计算方法与线性探测法相同，因此为5。

已知有长度为9的表 (16， 29， 32， 5， 89，41， 14， 65, 34)，它们存储在一个哈希表中，利用线性探测再散列法，要求它在等概率情况下查找成功的平均查找长度不超过了。 口(1）该哈希表的长度m应设计成多大？ 口 （2）设计相应的哈希函数 口（3） 将数据填入到哈希表中 口（4) 计算查找成功时的平均查找长度

(1) 根据装填因子α=9/m，我们希望平均查找长度不超过5，则根据公式：

E(n) = (1 + 1/(1-α))/2 <= 5

解得 m >= 14.25，因此哈希表的长度至少应该为15。

(2) 一个简单的哈希函数可以是取模函数，即 h(k) = k mod m，其中k为关键字，m为哈希表长度。

(3) 将数据填入哈希表中，可以按照以下步骤进行：

- 初始化哈希表，将所有位置都赋初值为空。
- 对于表中的每个元素，计算其哈希值h(k)，并将其插入哈希表中。
- 如果哈希表中h(k)位置已经被占用，则使用线性探测再散列法，查找下一个空位插入元素。

根据取模函数，可以将表中的元素插入到哈希表中的位置：

h(16) = 1， h(29) = 14， h(32) = 2， h(5) = 5， h(89) = 14， h(41) = 11， h(14) = 14， h(65) = 5， h(34) = 4

由于哈希表长度为15，因此哈希值相同的元素需要使用线性探测再散列法插入到下一个空位。

(4) 计算查找成功时的平均查找长度，可以使用公式：

ASL = Σ(di+1)/n

其中di为查找成功时需要查找的次数。我们可以使用线性探测的方法来查找元素，因此di最大为哈希表长度m，平均查找长度ASL不超过5，则可得到以下不等式：

Σ(m+1)/9 <= 5

解得 m >= 52.5，因此哈希表的长度至少应该为53。

将表中的元素插入到哈希表中后，可以计算出查找成功时的平均查找长度：

ASL = (1+2+1+1+3+1+1+2+1)/9 = 1.44

因此，在等概率情况下，查找成功的平均查找长度不超过1.44。