题目：关键字序列为：{38，25，74，63，52，48}，哈希函数为H(k)=k%7,哈希表的长度为7，用线性探测和链地址法处理冲突，分别计算等概率情况下查找成功的平均查找长度。
 
注：没给哈希表长度，给出装填因子时，可求哈希表长度， 
 可根据此公式装填因子=元素个数/表长推：表长=元素个数/装填因子。
 
线性探测法
 
 
由上构造的哈希表如下： 
 
 
等概率下查找成功的平均查找长度为： 
 ASL=(1+3+1+1+2+4)/6=2
 
链地址法 
 
 
由上构造的哈希表如下： 
 
 
等概率下查找成功的平均查找长度为： 
 ASL=(1*4+2*2)/6=1.3

查找成功时的平均查找长度
 
查找不成功时的平均查找长度
 
http://www.doc88.com/p-903238204265.html
 
 

 

       哈希表的装填因子 α 的定义如下：
 
                α = 哈希表中元素个数 / 哈希表的长度
 
       α 可描述哈希表的装满程度。显然，α 越小，发生冲突的可能性越小，而 α 越大，发生冲突的可能性也越大。
 
 
 
手工计算等概率情况下查找 成功 的平均查找长度公式
 
       规则如下：
 
 
 
 
 
ASLsucc＝ 
 
 
 
       其中 Ci 为置入每个元素时所需的比较次数
        例如：已知一组关键字序列（19，14，23，01，68，20，84，27，55，11，10，79）按哈希函数H(key)=key % 13 和线性探测处理冲突构造所得哈希表ht[0..15],如图1所示
 
 
 
比较次数：1     2      1      4      3      1      1     3     9      1      1     3
 
 
       查找19时，通过计算H（19）= 6,ht[6].key非空且值为19查找成功，则查找关键字19 ，仅需要计算1次地址就可以找到；
 
       查找14时，通过计算H（14）= 1,ht[1].key非空且值为14查找成功，则查找关键字19 ，仅需要计算1次地址就可以找到；
 
       查找23时，通过计算H（23）=10，ht[10].key非空且值为23查找成功，则查找关键字23 ，仅需要计算1次地址就可以找到；
 
       同样,查找关键字68，20，11，均需要计算一次地址就可以找到；
 
       查找关键字01时，通过计算H（01）=1，ht[1].key非空且值为14≠01,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时，ht[2].key非空且值为01，查找成功因此查找关键字01时，需要计算2次地址才可以找到；
 
       查找关键字55时，通过计算H（55）=3，ht[3].key非空且值为68≠55,则找第一次冲突处理后的地址H1=(3+1)% 13=4,此时，ht[4].key非空且值为27≠55，则找第二次冲突后处理地址H2=(3+2)% 13=5， ht[5].key非空且值为55查找成功，因此查找关键字27时，需要计算3次地址才能找到，同理，查找关键字10，84均需要计算3次地址才能找到；
 
       查找关键字27时，通过计算H（27）=1，ht[1].key非空且值为14≠27,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时，ht[2].key非空且值为01≠27，则找第二次冲突后处理地址H2=(1+2)% 13=3， ht[3].key非空且值为68≠27，则找第三次冲突后处理地址H3=(1+3)% 13=4，ht[4].key非空且值为27，查找成功，因此查找关键字27时，需要计算4次地址才可以找到；
 
       根据上面的方法，查找关键字79时，通过计算H（79）=1，ht[1].key非空且值为14≠79,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时，ht[2].key非空且值为01≠79，则找第二次冲突后处理地址H2=(1+2)% 13=3， ht[3].key非空且值为68≠79，则找第三次冲突后处理地址H3=(1+3)% 13=4，ht[4].key非空且值为27≠79，则找第四次冲突后处理地址H4=(1+4)% 13=5，ht[5].key非空且值为55≠79，则找第五次冲突后处理地址H5=(1+5)% 13=6，ht[6].key非空且值为19≠79则找第六次冲突后处理地址H6=(1+6)% 13=7，ht[7].key非空且值为20≠79，则找第七次冲突后处理地址H7=(1+7)% 13=8，ht[8].key非空且值为84≠79，则找第八次冲突后处理地址H8=(1+8)% 13=9，ht[9].key非空且值为79，查找成功，因此查找关键字79时，需要计算9次地址才可以找到。
 
 
 
       据此计算公式，对如图8.27的哈希表，采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找成功的平均查找长度为:
 
ASL(12)==2.5
 
       为便于计算, 在图8.27哈希表下方加注圆圈, 圆圈内表示的是有冲突时的计算次数, 如代表需要一次地址计算就可找到的关键字有6个，依此类推，即可得到计算结果。
 
同理据此公式, 对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找成功的平均查找长度为：
 
ASL(12)succ=
 
 
 
手工计算在等概率情况下查找 不成功 的平均查找长度公式
 
 
 
查找不成功的情况：(1)  遇到空单元
 
                               (2)  按解决冲突的方法完全探测一遍后仍未找到。0 -> r-1 个不成功查找的入口，从每个入口进入后，直到确定查找不成功为止，其关键字的比较次数就是与该入口对应的不成功查找长度。
 
       
 
规则如下：
 
ASLunsucc＝ 
 
       其中Ci为函数取值为 i 时确定查找不成功时比较次数
 
       据此计算公式，对如图8.27的哈希表，采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找不成功的平均查找长度为:
 
ASL(13)==6
 
       同理据此公式,对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找不成功的平均查找长度为：
 
ASL(13)unsucc= 
 
链地址法：
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 

 

 

 

 

 

 

 

首先，推荐两个写的很好的关于哈希表查找——成功和不成功时的平均查找长度的博客，感谢分享！
 
https://blog.csdn.net/longlovefilm/article/details/78009782
 
https://blog.csdn.net/wangran51/article/details/8826633/#commentBox
 
尤其需要注意哈希表查找不成功时的平均查找长度。
 
注意：查找成功时，分母为哈希表元素个数；
 
查找不成功时，分母为哈希表长度。
 
计算查找不成功的次数就直接找关键字到
 
第一个地址上关键字为空的距离即可；
 
哈希表查找不成功怎么计算？ 
 
解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！