线性探测再散列方法：查找成功平均查找长度实例

线性探测再散列方法是一种解决冲突的方法，当发生冲突时，依次检查下一个位置，直到找到一个空槽或者遍历整个地址空间。

根据题目给出的关键字序列（21, 40, 52, 45, 29, 12, 02, 66）和哈希函数 H(K)=K%11，我们可以将关键字插入到对应的哈希地址中。

第一个关键字 21，通过哈希函数计算得到的哈希地址为 10，该位置为空，插入关键字。

第二个关键字 40，通过哈希函数计算得到的哈希地址为 7，该位置为空，插入关键字。

第三个关键字 52，通过哈希函数计算得到的哈希地址为 8，该位置为空，插入关键字。

第四个关键字 45，通过哈希函数计算得到的哈希地址为 1，该位置为空，插入关键字。

第五个关键字 29，通过哈希函数计算得到的哈希地址为 7，该位置已经被占用，发生冲突。由于线性探测再散列方法，我们需要从下一个位置开始，即哈希地址为 8，该位置为空，插入关键字。

第六个关键字 12，通过哈希函数计算得到的哈希地址为 1，该位置已经被占用，发生冲突。从下一个位置开始，即哈希地址为 2，该位置为空，插入关键字。

第七个关键字 02，通过哈希函数计算得到的哈希地址为 2，该位置已经被占用，发生冲突。从下一个位置开始，即哈希地址为 3，该位置为空，插入关键字。

第八个关键字 66，通过哈希函数计算得到的哈希地址为 0，该位置为空，插入关键字。

最终，关键字序列插入完成后，哈希地址空间如下：

0: 66 1: 45, 12 2: 02 3: 66 4: 5: 6: 7: 40, 29 8: 52 9: 10: 21

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

ASL = (成功查找的平均查找长度 + 失败查找的平均查找长度) / 2

成功查找的平均查找长度 = ∑(查找成功的次数 * 查找成功的步数) / ∑查找成功的次数 失败查找的平均查找长度 = ∑(查找失败的次数 * 查找失败的步数) / ∑查找失败的次数

通过计算可以得到： 查找成功的次数 = 8（关键字序列的长度） 查找失败的次数 = 11（哈希地址空间的大小）- 8（关键字序列的长度）= 3

查找成功的步数 = 1（在插入时已经找到了对应的位置） 查找失败的步数 = 1（在哈希地址空间中遍历一次，直到找到一个空槽）

成功查找的平均查找长度 = (8 * 1) / 8 = 1 失败查找的平均查找长度 = (3 * 1) / 3 = 1

ASL = (1 + 1) / 2 = 1

所以，等概率下查找成功的平均查找长度为 1。