线性探测再散列方法处理冲突：查找成功的平均查找长度

线性探测再散列方法是一种处理冲突的方法，当关键字的哈希值发生冲突时，通过依次查找下一个空槽，直到找到一个空槽为止。\n\n首先，根据关键字序列计算哈希值：\nH(21) = 21 % 11 = 10\nH(40) = 40 % 11 = 7\nH(52) = 52 % 11 = 8\nH(45) = 45 % 11 = 1\nH(29) = 29 % 11 = 7\nH(12) = 12 % 11 = 1\nH(02) = 2 % 11 = 2\nH(66) = 66 % 11 = 0\n\n将关键字依次插入哈希表中，如果发生冲突，则使用线性探测再散列方法查找下一个空槽：\nH(21) -> 10\nH(40) -> 7\nH(52) -> 8\nH(45) -> 1 (冲突，查找下一个空槽)\nH(29) -> 2\nH(12) -> 1 (冲突，查找下一个空槽)\nH(02) -> 3\nH(66) -> 0\n\n最终的哈希表如下：\n0: 66\n1: 45\n2: 29\n3: 02\n4: \n5: \n6: \n7: 40\n8: 52\n9: \n10: 21\n\n根据哈希表中的分布，计算等概率下查找成功的平均查找长度：\nL = (1/N) * (Σ(ni*(ni+1)/2))，其中ni表示在第i个槽中的关键字数量，N表示槽的数量。\n\n计算关键字数量：\nn0 = 1\nn1 = 2\nn2 = 1\nn3 = 1\nn4 = 0\nn5 = 0\nn6 = 0\nn7 = 1\nn8 = 1\nn9 = 0\nn10 = 1\n\n代入公式计算平均查找长度：\nL = (1/11) * [(1*(1+1)/2) + (2*(2+1)/2) + (1*(1+1)/2) + (1*(1+1)/2) + (0*(0+1)/2) + (0*(0+1)/2) + (0*(0+1)/2) + (1*(1+1)/2) + (1*(1+1)/2) + (0*(0+1)/2) + (1*(1+1)/2)]\n = (1/11) * [1 + 3 + 1 + 1 + 0 + 0 + 0 + 1 + 1 + 0 + 1]\n = (1/11) * 9\n = 9/11\n ≈ 0.818\n\n所以，等概率下查找成功的平均查找长度为约0.818。