做到计算查找成功和查找不成功的平均查找长度知识点，王道书上写的参考答案太简陋，没有写具体的过程，然后前面的知识点也没讲解怎么求平均查找长度，一脸懵逼o((⊙﹏⊙))o，于是乎在网上一顿乱搜，看了很多博客，终于理解了。在这个过程中发现很多人和我一样不理解，而且很多文章本身也有错误，所以发表一下自己的理解，希望能帮到大家，欢迎指正。
下图为知识总览：
平均查找长度
考研数据结构之查找 散列表
1.查找成功
查找成功意味着需要查找的元素一定在表中，所以需要计算表中的每个元素通过 散列法&处理冲突的方法 得出的查找次数，求和再除以元素个数。
1.1查询目标
- 散列表中的每个元素
1.2查询过程
1)通过散列函数查询该元素地址;
2).访问地址，此次元素的查找次数+1;
-
3).若地址元素和目标元素不等，通过解决冲突的方法得到下一个地址，并转向2);
(解决冲突的方法 考试常用线性探测法)
4).若地址元素和目标元素相等，停止此元素的查找
1.3计算方法
- 散列表中所有元素的查找次数之和/元素个数
2.查找失败
查找不成功意味着查找的元素一定不在表中，所以与表中元素个数无关。每次查询查到地址为空为止，查到空意味着不需要再查询，也就是失败。
2.1查询目标
- 使用散列函数可能得到的所有地址(数组下标)
假设H(key)=7，则意味着查找失败时可能对应的地址有7个。
2.2查询过程
- 1).访问地址，此次元素的查找次数+1;
- 2).若地址不为空，通过解决冲突的方法得到下一个地址，并转向1);
- 3).若地址为空则停止
2.3计算方法
- 散列函数对应所有地址元素的查找次数之和/散列值
3.易混淆
3.1为何 查找成功 除以 散列表元素个数，而查找失败 除以 散列值呢？
假设把所有元素对应的关键字分为两类，一类是在散列表中的数(查找会成功)，一类是不在散列表中的数(查找会失败)。
要求查找成功的平均查找长度时，意味着这个数一定在散列表中，所以我们只需要考虑散列表中的元素即可。
-
要求查找不成功的平均查找长度时，意味着这个数一定不在散列表中
- 有童鞋可能这时候有疑惑，不在散列表中的数字那么多，我怎么一个一个去求？所以说肯定不会让你一个一个去算查找次数滴。
- 这个时候我们需要将不在散列表中的数再次分类，假设散列值为p，就可以将不在散列表中的数再次分为p 类，每一类分别为地址映射到i(0≤i≤p-1)的数，分别计算p类中每一类的查找次数即可。
3.2 为何查找成功以 地址元素和目标元素相等 为停止, 而查找失败以 地址为空 为停止？
- 注意我们有前提，查找成功意味着目标元素一定在散列表中，即一定会查到。
- 查找失败意味着目标元素不在散列表中，若地址元素不为空，那地址元素肯定和目标元素不等。但只有到地址为空，我们才能断定查找失败。
4.例题
2010统考真题，选自王道数据结构考研复习指导p286
4.1题目【2010统考真题】
将关键字序列{7,8,30,11,18,9,14}散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组，散列函数为H(key)=(key*3) Mod 7，处理冲突采用线性探测再散列法，要求装填因子为0.7.
（1）请画出所构造的散列表。
（2）分别计算等概率情况下，查找成功和查找不成功时的平均查找长度。
4.2 参考答案
考研数据结构之查找（9.8）——练习题之将关键字序列{7,8,30,11,18,9,14}散列存储到散列表中（C表示）_二木成林-CSDN博客
参考答案后面有空会补上
