如果你看了很多其他博客然后都看不懂看到了这篇，你一定可以容易懂的！我佛了，这么简单的东西死板地讲题目不讲原理鬼看得懂啊，这种风气真的不行，我忍不住想骂一声垃圾，啥玩意儿，误人子弟！原理懂了啥题不会做？
 
要想知道 散列表查找失败的平均查找长度，就要知道什么叫做查找失败！举个栗子：8个数字  key%11  如下算好了：
 
散列地址
0
1
2
3
4
5
6
7
8
9
10
关键字
33
1
13
12
34
38
27
22
 
 
 
冲突次数
0
0
0
2
3
0
1
7
 
 
 
什么叫做查找失败？比如你要查55这个关键字，你必须%11，等于0，查地址0为33，不对，下一位1，不对，继续往下查找直到出现空的才知道这个关键字一定不存在，否则就放在空着的那个地址。所以以上表，计算地址为0的关键字查了9次才才知道没有这个关键字称为查找失败；计算地址为1的关键字只有探测完1-8号才能确定该元素不存在，以此类推。但是注意了，如果计算地址为8的或者9的、10的，只需要查找一次就知道该地址为空，失败了。因此查找一次就行。而且要知道如果查找成功是除以关键字个数，但是查找失败是除以你要模的数字本题是11，千万记住了，不是地址个数，不是关键字个数。综上所述，查找失败的平均查找长度为（9+8+7+6+5+4+3+2+1+1+1）/11=47/11。放心错不了，书上原题。
 
还要注意，如下题型H(key)=key%7：
 
散列地址
0
1
2
3
4
5
6
7
8
关键字
98
22
30
87
11
40
6
20
 
千万注意，%7只能映射到0-6，散列函数不可能映射7，因此查找失败平均查找长度为（9+8+7+6+5+4+3)/7=6。看到这你可能想骂娘，啥玩意儿，别急。我会让你看懂，因为我最讨厌虾鸡吧写博客的傻逼玩意儿，写的不清楚又不解释，还误人子弟，low咖！！！好了回归正题。首先要知道，我们求平均查找长度其实在求概率，对于成功的平均查找长度，查找每个元素的概率是1/8，这个8就是关键字个数。就是说，查找成功你只能选择8个中的一个，否则成功不了，所以都是在等概率1/8情况下。查找失败也是一样，这里对每个位置的查找概率都是1/7,注意7是你要模的数字，就是说，你随便拿几个数，模7，只能是0、1、2、3、4、5、6，其中一种情况，不可能是7、8以后的数字，所以只需要计算地址在0-6中的概率。如果计算地址后为0，那么需要比较9次，以此类推，所以只能是上面的计算式子，别搞错了噢！还有要注意有些散列表不是完全填满，中间有空位，那相信你看完上面原理就不用我解释了，找到了空位还没有就说明不存在嘛，否则它就占位这个空位了。注意以上所讨论的全部是线性探测，如果是平方探测注意左右跳动，具体问题具体分析，就不展开了。相信你看到这个已经真正明白了什么叫做查找失败平均查找长度。对于垃圾博客需要狠狠骂，对于我也是，我写的烂的大家给我狠狠骂，这样才能少一些误人子弟的渣渣了，只讲怎么怎么操作不讲原理有什么狗屁用，换个方式描述不还是不会。知其然要知其所以然！！！以上如果有错误，还请大家狠狠指出来，谢谢大家！
 
 
比如这篇博客，真佛了，一来就巴拉巴拉在那算算算，好像谁不会计算散列表似的，人家真正不懂的是查找失败的平均查找长度的计算，真正的标题党。垃圾文章！！！
 
 
 
 
 
 
 
 
 
 
 
 

不要记那个近似公式
 参考链接开放定址法和拉链法的平均查找长度

散列表成功的平均查找长度和查找失败的平均长度：
 关于成功的平均查找长度：查找成功的key在于散列表中一定会有关键值，可以直接通过一次散列函数找到的则是一次查找，否则根据线性散列探测去计算
 关于失败的平均查找长度：
 ①失败是由于散列表中没有对应的数值，比如散列函数是 H[key]= key%7，我们要查找 8 这个数字的位置，如果散列表中存在这个数值 8，那么不管查找多少次，有多少次冲突都会找到，而计算失败的次数就是从“假定存在的位置一直查找到第一个空的位置”，如查找8则是从1的位置开始找，找到第一个空的位置
 ②关于除数的数值：知道了总的失败次数，mod7的话只有六种情况，也就是0-6，所以只需要计算0-6分别到第一个空的位置，求和后除以7（也就是可以取到的余数的情况）

顺序查找 折半查找的平均查找长度分析
 
ASL：平均查找长度
 
其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。
 $$ASL=\sum _{i=1}^n{p}_i{c}_i$$
 
一般顺序查找的平均查找长度：
 
因为顺序查找就是顺序存储 一个一个比较，所以如果查找成功的话说明就和之前不相等的元素已经比较过了。
所以第 n 个元素就是比较了 n 次
每个元素都比较了其所在位序的次数
每个元素被查找的概率都是1/n 所以
 
$AS{L}_{成功}=\frac{1}{n}(1+2+3+\dots +n)=\frac{n+1}{2}$
 
$ASL_{成功}=n+1 $
 
有序顺序表的平均查找长度：
 
 
查找成功的 ASL 不影响
 
 
如果查找不成功的话，因为顺序表有序，所以可以提前结束，从而缩短查找失败的比较次数，需要画个简单【判定树】
 
 
举个例子，在[10 20 30 40 50 60]中查找
 
 
 
失败的一共有 n+1个结点，所以每个结点的概率就是$\frac{1}{n+1}$
比较次数是 每个失败结点上一层的层数
 
$AS{L}_{失败}=\frac{1}{n+1}[1+2+3+\dots +n+n]=\frac{n}{2}+\frac{n}{n+1}$
 
折半查找的平均查找长度：
 
 
要涉及到判定树：n 个元素就有n 个【内部结点】 n+1个【外部结点】
 
 
【判定树】一定是【满二叉树】
 
 
根据折半算法画出初级判定树（只有内部结点），其他空位用【查找失败的方框代替】
 
 
算 ASL 直接就是算 [每层结点的个数*层数]➗结点个数
 
 
 
不成功要具体例子具体计算。