线性探测再散列方法处理冲突 - 平均查找长度计算

线性探测再散列方法中，当发生冲突时，依次向后查找空闲的地址空间，直到找到合适的位置插入或者遍历整个地址空间都没有找到合适位置。\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) = 02 % 11 = 2\nH(66) = 66 % 11 = 0\n\n冲突的关键字为：29、12。\n\n使用线性探测再散列方法处理冲突，将冲突的关键字依次向后查找空闲的地址空间：\nH(29) = 7\nH(12) = 1\nH(29) = 2\nH(12) = 3\nH(29) = 4\nH(12) = 5\nH(29) = 6\nH(12) = 9\nH(29) = 0\nH(12) = 10\n\n最终的散列结果为：\nH(21) = 10\nH(40) = 7\nH(52) = 8\nH(45) = 1\nH(29) = 0\nH(12) = 2\nH(02) = 2\nH(66) = 0\n\n等概率下查找成功的平均查找长度（ASL）的计算公式为：\nASL = (n + 1) / 2\n\n其中，n为关键字的个数。\n\n根据上述散列结果，共有8个关键字，所以n = 8。\n\n将n带入公式，得到：\nASL = (8 + 1) / 2 = 9 / 2 = 4.5\n\n所以，等概率下查找成功的平均查找长度为4.5。