将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为： H(key) = (key*3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。
(1) 请画出所构造的散列表；
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

一、查找成功平均长度

• 通过公式计算出存放的位置，如果该位置已经有数字了，往后找到一个空的放下。
• 存放示意图

• 查找时候，一次找到的查找长度为1，否则多移动一格查找长度加一。如下表

• 由此可得查找成功的平均查找长度为：（1+1+1+1+3+3+2）/7 = 12/7

二、查找不成功平均长度

接下来讨论不成功的情况，由上表，计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可， 但根据哈希函数地址为MOD7，因此初始只可能在0_{6的位置。等概率情况下，查找0}6位置查找失败的查找次数为：

看地址0，到第一个关键字为空的地址2的距离为3，因此查找不成功的次数为3.

地址1， 到第一个关键为空的地址2的距离为2，因此查找不成功的次数为2.

地址2， 到第一个关键为空的地址2的距离为1，因此查找不成功的次数为1.

地址3，到第一个关键为空的地址4的距离为2，因此查找不成功的次数为2.

地址4，到第一个关键为空的地址4的距离为1，因此查找不成功的次数为1.

地址5，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间（因为只有7个数），因此循环回去)的距离为5，因此查找不成功的次数为5.

地址6，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为4，因此查找不成功的次数为4.

因此查找不成功的次数表如下表所示

• 所以查找不成功平均长度：（3+2+1+2+1+5+4）/ 7 = 18/7。

个人总结的有关考研数据结构中平均查找长度ASL的三种计算小技巧：

1. 顺序查找法的平均查找长度为：(n+1)/2

2. 散列表的查找成功和查找不成功的平均查找长度
   技巧（线性探测法和链地址法）：
   ① 查找成功时的比较次数是基于关键字计算的；查找不成功时的比较次数是基于Hash函数计算得到的地址计算的。
   ②查找成功的计算只有一种情况；查找不成功的计算有两种情况，关键是看题目中是否含有（只将与关键字的比较计算在内）
   若没有，查找过程中遇到空位置，则证明查找失败；若有，则查找过程中只需比较关键字即可。

   注意：①查找成功是除关键字的个数；②查找不成功是除mod后的数值

3. 折半查找成功和查找不成功的平均查找长度：

   以折半查找的方式，将逐个查找出来的数值建立判定树，根据判定树求查找成功和查找不成功的平均查找长度。

   注意：①查找成功是除关键字个数；②查找不成功是除关键字个数加1

个人的理解就是这样，希望能够帮到部分同在考研的研友们！

线性探测再散列

例如 哈希函数为： H（key） = key %13,key 为关键字，采用开放地址法中的线性探测再散列解决冲突，依次输入

11 个关键字，16，74，60，43，54，90，46，31，29，88，77，构造哈希表

如图，例如 16%13=3，将16放入3号位置，29%13 = 3，将29放入3号位置，而此时3号位已经有元素。

就顺着表往后放，直到6号没有元素，29放入6号。

二次探测再散列

例如 哈希函数为： H（key） = key %13,key 为关键字，采用开放地址法中的二次探测再散列解决冲突，依次输入

10 个关键字，36，21，45，17，29，55，35，61，40，78，构造哈希表

对于29%13=3，将29放入3号位置， 55%13=3，此时3号位置已经有元素，

则查找 3 + 1^2 = 4,有元素

查找 3 - 1^2 = 2 ,没有则放入，如果还有元素则查找3 + 2^2, 3-2^2… 3+k^2, 3 - k^2。

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

它的定义是这样的：

其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。

当然，有查找成功，就有查找不成功，即要查找元素不在查找表中。针对不同查找方式的查找成功与不成功，我接下来会说，这也是一我一开始有点乱的地方。

一个算法的ASL越大，说明时间性能差，反之，时间性能好，这也是显而易见的。

• 在_顺序查找(Sequence Search)_表中，查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。所以说，Ci（第i个元素的比较次数）在于这个元素在查找表中的位置，如第0号元素就需要比较一次，第一号元素比较2次…第n号元素要比较n+1次。所以Ci=i；所以

        可以看出，顺序查找方法查找成功的平均 比较次数约为表长的一半。**当待查找元素不在查找表中时，也就是扫描整个表都没有找到，即比较了n次，查找失败**

• 折半查找(Binary Search)，首先待查找表是有序表，这是折半查找的要求。在折半查找中，用二叉树描述查找过程，查找区间中间位置作为根，左子表为左子树，右子表为右子树，，因为这颗树也被成为判定树(decision tree)或比较树(Comparison tree)。查找方式为(找k)，先与树根结点进行比较，若k小于根，则转向左子树继续比较，若k大于根，则转向右子树，递归进行上述过程，直到查找成功或查找失败。在n个元素的折半查找判定树中，由于关键字序列是用树构建的，所以查找路径实际为树中从根节点到被查结点的一条路径，因为比较次数刚好为该元素在树中的层数。所以Pi为查找k的概率，level(Ki)为k对应内部结点的层次。而在这样的判定树中，会有n+!种查找失败的情况，因为将判定树构建为完全二叉树，又有n+1个外部结点(用Ei(0<=i<=n)表示)，查找失败，即为从根结点到某个外部结点也没有找到，比较次数为该内部结点的结点数个数之和，所以，qi表示查找属于Ei中关键字的概率，level(Ui)表示Ei对应外部结点的层次。所以，在一颗有n个结点判定树中，总数，所以判定树高度为的满二叉树,第i层上结点个数为，查找该层上的结点需要进行i次比较，因此，在等概率情况下ASL为 看个例子会更好理解。

• 例：给11个数据元素有序表（2,3,10,15,20,25,28,29,30,35,40）采用折半查找。则ASL成功和不成功分别是多少？

• 首先画出判定树，

• 查找成功时总会找到途中某个内部结点，所以成功时的平均查找长度为 即25查找一次，成功，10,30要查找2次，成功，2,15,28,35要查找3次，成功，3,20,29,40要查找4次，成功。 而不成功的平均查找长度为 ，为什么这么算呢，因为内部结点都能查找成功，而查找不成功的就是那些空的外部结点，所以到查询到2的左孩子，15的左孩子，28的左孩子，35的左孩子，3的左右孩子，20的左右孩子，29的左右孩子，40的左右孩子时，都是查找不成功的时候。如我要找1，比25小，转向左子树，比较一次，比10小，转左子树，2次，比2 小，转左子树，3次，此时2无左子树，所以失败。所以 。

• 哈希表中的ASL 查找成功的平均查找长度是指查找到哈希表中已有关键字的平均探测次数。而查找不成功的平均查找长度是指在哈希表中找不到待查的元素，最后找到空位置元素的探测次数平均值。

• 例：散列表长度为13，地址空间为0~12，散列函数H(k) =K mod 13,关键字序列{19,14,23,01,68,20,84,27,55,11,10,79} 所以线性探测结果为：

• 

各位可以手动算一下，加深理解～

根据探测次数，

当然成功的很好理解，12个元素，每个元素的探测次数之和除以12就行。而不成功的计算是这样的。散列表长度为13，根据定义，假设待查关键字不在散列表中，要一直找到空元素才算查找失败。

如H[0]为空，与待查找元素不等，不成功，比较一次，H[1]，此时H[1]的元素与原本放在H[1]的元素不等**(假设不在散列表在之中，但也不是空的**)，继续向后比，与H[2]比也不等，继续向后，一直到H[12]，也不等，继续向后时，回到H[0]，为空，也不等，查找失败，总计比较13次，然后计算第二号元素，一样的比较，一直把每个位置都统计一遍，从而得出ASL不成功的.

对于查找成功时的平均查找长度，书上有明确的定义：

而题目设定条件都是在等概率下查找，所以ASL=（C0+C1+...+Cn）*1/n.
这就说明了查找成功是针对关键字查找的，最后除以关键字的总个数。
我们来看一道书上的例题：

构建出来的哈希表有八个元素，针对这八个元素的比较次数，得出ASLsuccess=(1+1+1+2+1+2+1+2)/8=11/8.

而查找失败时的平均查找长度，却是针对位置的查找。
为什么呢，因为如果我们要查找表中的元素，那么一定可以找到，所以讨论查找失败就没有意义。我们讨论查找失败，一定是针对表中没有的元素在这张表中查找，才有查找失败的意义。

所以，针对上图的哈希表，我们将待查找关键字X代入哈希函数，我们设定X与这张表中的关键字都不相同：
当H(X)=3X mod 11=0时，因为散列地址为0的位置没有关键字，所以查找1次就失败了；
当H(X)=3X mod 11=1时，因为散列地址为1的位置有关键字4，X与4不等，所以按照线性探测法向后探测1，散列地址为2的位置没有关键字，所以查找失败，一共查找了2次；
当H(X)=3X mod 11=2时，同0；
当H(X)=3X mod 11=3时，因为散列地址为3的位置有关键字12，X与12不等，所以向后线性探测，散列地址为4的位置有关键字49，还不等，继续探测，因为X与表中的关键字都不等，所以直到散列地址为10没有关键字，才查找失败，这次一共查找了8次；
…以此类推

综上所述，我们可以得出结论：

失败查找次数就是该位置向后探测到第一个没有关键字的地址位置之间的距离

而求平均数的除数，是模的大小

因为失败查找次数是针对位置查找，因为模为11，所以查找的位置(哈希函数的值)为0-10(共11个),针对这11个位置进行查找，而与表的长度无关。

理清了思路，我们来看看链地址法表示的哈希表：

成功时的平均查找长度很好求，针对表中的每个关键字：有五个关键字找一次：4,12,49,13,32；三个关键字找两次：38,24,21.

失败时的平均查找长度针对位置来查找：
等于0时，只有空指针域，查找1次；
等于1时，带一个结点，所以查找2次找到空指针；
…
等于4时，带两个节点，所以查找3次找到空指针；
…
综上所述，我们可以总结：

失败查找次数就是当前位置所带的结点个数+1

使用链地址法查找时无二次聚集现象(二次聚集：处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象)

除数也是模的大小

你学会了吗？

哈希表（又名为是散列表）
散列是一个用于唯一标识对象并在一些预先计算的唯一索引（称为“密钥”）存储每个对象的过程。因此，对象以“键值”对的形式存储，这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构，但最常用的数据结构是哈希表。

哈希表通常使用数组实现。

哈希数据结构的性能取决于以下三个因素：

哈希函数
哈希表的大小
碰撞处理方法
下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。

今天主要讲一下哈希表平均查找长度ASL计算，也是常见面试题之一
题目：关键字序列为：{30，25，80，63，52，48}，哈希函数为H(k)=k%7,哈希表的长度为7，用线性探测和链地址法处理冲突，分别计算等概率情况下查找成功的平均查找长度。

注：没给哈希表长度，给出装填因子时，可求哈希表长度，
可根据此公式装填因子=元素个数/表长推：表长=元素个数/装填因子。

线性探测法（通过数组保存）
H(30)=30%7=2
H(25)=25%7=4
H(80)=80%7=3,和30冲突，往后移一位：4，又与25冲突，继续后移一位：5
H(63)=63%7=0
H(52)=52%7=3，后移三位为6
H(48)=48%7=6，与52冲突，后移一位为0，再后移一位为1
结果为：
30 ——2
25——4
80——5
63——7
52——6
48——1
平均查找长度：查找次数和/数组个数
（1+1+3+1+4+3）/6=2.2

链地址法 (以链表形式存储）
取模后值相同的在同一个链表中，即
0——63
1
2
3——30——80——52
4——25
5
6——48
等概率下查找成功的平均查找长度为：
ASL=(14+21+3*1)/6=1.5