题目：关键字序列为：{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= 
链地址法：
 

哈希表查找——成功和不成功时的平均查找长度



以下求解过程是按照“计算机统考的计算方法”，不同的老师、教材在“处理冲突”上可能会有不同的方法，所以最主要的是掌握原理即可，对于考研的朋友最好掌握统考真题的解题方法。
题目
例子：（2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题第一题）


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

1.散列表：
          α = 表中填入的记录数/哈希表长度    ==>  哈希表长度 = 7/0.7 = 10
            H(7) = (7x3) MOD 7 = 0           H(8) = (8x3) MOD 7 = 3           H(30) = (30x3) MOD 7 = 6
            H(11) = (11x3) MOD 7 = 5       H(18) = (18x3) MOD 7 = 5       H(9) = (9x3) MOD 7 = 6
            H(14) = (14x3) MOD 7 = 0
           按关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入。


0
1
2
3
4
5
6
7
8
9
7
14
8
11
30
18
9


2.查找长度：
        2.1 查找成功的平均查找长度
       （待查找的数字肯定在散列表中才会查找成功）
        查找数字A的长度 = 需要和散列表中的数比较的次数；
       步骤：
                比如 查找数字：8
                则  H(8) = (8x3) MOD 7 = 3
                哈希表中地址3处的数字为8，进行了第一次比较：8 = 8，则查找成功，查找长度为1；
                比如查找数字：14
                则 H(14) = (14x3) MOD 7 = 0
                哈希表中地址0处的数字为7，进行第一次比较：7≠14
                哈希表中地址1处的数字为14，进行第二次比较：14=14 ，则查找成功，查找长度为2。                             
由此可得到如下数据：【2016年12月26日修改，多谢@一楼的朋友指正】





0
1
2
3
4
5
6
7
8
9
7
14
8
11
30
18
9
1
2
1
1
1
3
3




所以总的查找成功的平均查找长度= （1+1+1+1+3+3+2）/7 = 12/7
      2.2查找不成功的平均查找长度
             （待查找的数字肯定不在散列表中）    
             【解题的关键之处】根据哈希函数地址为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(比较到地址6，再循环回去)需要比较5次，因此查找不成功的次数为5.


  地址6，到第一个关键字为空的地址2(比较到地址6，再循环回去)需要比较4次，因此查找不成功的次数为4.
于是得到如下数据：





0
1
2
3
4
5
6
7
8
9
7
14
8
11
30
18
9
3
2
1
2
1
5
4
则查找不成功的平均查找长度 = （3+2+1+2+1+5+4）/7 = 18/7










哈希表——线性探测法、链地址法、查找成功、查找不成功的平均长度
            
            
                
四、哈希表的装填因子
装填因子 = （哈希表中的记录数） /  （哈希表的长度）
装填因子是哈希表装满程度的标记因子。值越大，填入表中的数据元素越多，产生冲突的可能性越大。

五、不同处理冲突的平均查找长度
 
例：
假设散列表的长度是13，三列函数为H(K) = k % 13，给定的关键字序列为{32， 14， 23， 01， 42， 20， 45， 27， 55， 24， 10， 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。
（1）线性探测法：
查找成功时的查找次数等于插入元素时的比较次数,查找成功的平均查找长度为：
ASL = （1+2+1+4+3+1+1+3+9+1+1+3)/12 = 2.5
查找成功时的查找次数：第n个位置不成功时的比较次数为：第n个位置到第1个没有数据位置的距离：如第0个位置取值为1，第11个位置取值为3，第12个位置取值2
查找不成功的平均查找次数为：
ASL = （1+13+12+11+10+9+8+7+6+5+4+3 + 2）/ 13 = 91/13

哈希表查找不成功怎么计算？
解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！
例如：散列函数为hash(x)=x MOD 11，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？
       地址：0     1    2    3    4    5    6    7    8    9    10
      数据：33     1    13   12  34    38   27   22   －   －   －
   成功次数：1     1    1    3    4    1    2    8
 不成功次数：9     8    7    6    5    4    3    2    1    1    1
查找成功时的平均查找长度:ASL=(1+1+1+3+4+1+2+8)/8 =47/8
查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+1)/11
说明：
第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。
  如：第0个位置到第1个没有数据位置（8）的距离为9！

（1） 开放定址法
地址： 0   1   2   3   4   5   6   7   8   9   10   11   12      
数据： 39  12  28  15  42  44   6  25  －  －   36   －   38   
成功次数： 1   3   1   2   2   1   1   9                1        1 
不成功次数： 9   8   7   6   5   4   3   2   1   1    2   1    10 
查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2 
查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54


（2）链地址法
java中的hashMap就是这样一种链表+数组的数据结构，查找方法很简单，先利用散列函数（一般是取余数的方法）定位数组具体哪个点，比如1就是余数为1的点的链表中，然后再遍历链表查找具体数值的位置，如,果是53，那就在链表的第四位置，需要查找四次；同理，27就需要查找3次！
查找成功时的平均查找长度：
ASL = (1*6+2*4+3*1+4*1)/12 = 7/4
查找不成功时的平均查找长度：
ASL = (4+2+2+1+2+1)/13
注意：查找成功时，分母为哈希表元素个数，查找不成功时，分母为哈希表长度。