计算散列表查找成功和查找不成功的平均查找长度（利用线性探测法处理冲突）

        哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。映射函数叫做散列函数，存放记录的数组叫做散列表。

        关键字个数 / 表长

        一般来说冲突不可避免的，只能尽可能地减少冲突的发生。在建立Hash表的时候必须进行冲突处理。         下面主要介绍线性探测法：也是一种比较常用的处理冲突的方法（但是极易产生堆积问题）

即本文的主要内容，查找成功与查找失败的分析。

直接以题目来理解会比较快些：

        现有长度为11 且初始为空的散列表HT，散列函数H(key) = key % 7，采用线性探查法解决冲突。将关键字序列87，40，30，6，11，22，98，20 依次插入HT后，HT的查找失败的平均长度是多少呢？ 查找成功的平均查找长度又是多少呢？         ① 首先，通过散列函数并且利用线性探测法给他们每个字划分好自己的位置；         ② 记录每个字冲突的次数，后面在计算查找成功的平均长度会用到；         ③ 查找失败计算每个查找失败对应地址的查找次数，即从所查位置开始往后查直至查到空位置位置；         ④ 其实，后面熟悉过程之后，在列出下面的每个关键字对应地址的表格之后就可以秒出答案；

注意事项 查找失败时对应的地址在这个题目，只能是7 即 0~6 ；

ASL 查找失败= （9 + 8 + 7 + 6 + 5 + 4 + 3 ）/ 7 = 6

ASL 查找成功= （1 + 1 + 1 + 1 + 1 + 1 + 1 + 2）/ 8 = 9 / 8

OK，上面把例子说完了，可以再看看下面这个题目，来测试下是否理解了上面的那些需要注意的点。         将关键字序列（7，8，30，11，18，9，14）散列存储到散列表中。散列表的存储空间是从0开始的一维数组，散列函数为H(key) = （3*key）mod 7,处理冲突采用线性探测法，要求装填因子为0.7。         （1）画出所构造的散列表。         （2）分别计算等概率情况下的查找成功和不成功的平均查找长度。（12/7 和 18/7）

（1）数组大小 = 7 / 0.7 = 10

（2）         ①查找成功时

        ASL 查找成功= （1 + 2 + 1 + 1 + 1 + 3 + 3 ）/ 7 = 12 / 7         ②查找失败时

        ASL 查找失败= （3 + 2 + 1 + 2 + 5 + 4）/ 7 = 18 / 7

【总结】简单吧，主要就是查找失败时除以的分母是 mod 后面的那个数，而不是关键字的个数。