最近复习数据结构中的哈希表，发现在计算等概率情况下查找不成功的平均查找长度时不太理解，不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了，总结如下。
 
 
 
 
 
例题：
 
 
将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。
 
 
（1）请画出所构造的散列表。
 
 
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
 
 
 
 
（1）首先明确一个概念：装载因子。装载因子是指所有关键子填充哈希表后饱和的程度，它等于 填入表中的关键字总数/哈希表的长度。
 
根据题意，我们可以确定哈希表的长度为 L = 7/0.7 = 10；因此此题需要构建的哈希表是下标为0~9的一维数组。
 
 
 
这里采用线性探测再散列法处理冲突，构造散列表。
 
       H(7) = (7x3) MOD 7 = 0，地址为0，因此放到散列表的数组下表为0的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
 
       H(8) = (8x3) MOD 7 = 3，地址是3，因此放到散列表的数组下表为3的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
 
       H(30) = (30x3) MOD 7 = 6，地址是6，因此放到散列表的数组下表为6的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
 
       H(11) = (11x3) MOD 7 = 5，地址是5，因此放到散列表的数组下表为5的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
 
       H(18) = (18x3) MOD 7 = 5，地址是5，因此放到散列表的数组下表为5的位置，但这个位置上已经有关键字11，遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探测下一个位置6，6这个位置上已经存在关键字30则继续增加1，因此现在的新地址应为7，位置7上没有关键字，放入即可，到此冲突已经解决；
 
       H(9) = (9x3) MOD 7 = 6，地址是6，因此放到散列表的数组下表为6的位置，但这个位置上已经有关键字30，遇到了冲突，探测下一个位置7，7这个位置上已经存在关键字18则继续增加1，因此现在的新地址应为8，位置8上没有关键字，放入即可；   
 
       H(14) = (14x3) MOD 7 = 0，地址是0，因此放到散列表的数组下表为0的位置，但这个位置上已经有关键字7，遇到了冲突，探测下一个位置1，位置1上没有关键字，放入即可；   
 
       到这一步所有关键字均已填入，散列表已经构造完成，如下表所示。
 
地址
0
1
2
3
4
5
6
7
8
9
关键字
7
14
 
8
 
11
30
18
9
 
 
 
（2）等概率情况下查找成功平均查找长度：
 
        这一问可以根据第一问的构造过程求解：
 
        key7 一次就填入了表中，因此查找次数为1，同理8， 30， 11查找次数均为1；
 
        key18 进行了三次探测操作，探测位置分别是5，6，7 ，因此查找次数为3；
 
        key9 也是三次；
 
        key14 进行了两次探测，因此查找次数为2。次数如下表所示：
 
地址
0
1
2
3
4
5
6
7
8
9
关键字
7
14
 
8
 
11
30
18
9
 
 
 
成功次数
1
2
 
1
 
1
1
3
3
 
   
 
        所以ASLsuccess= （1+2+1+1+1+3+3）/ 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，到第三个关键字为空的地址9的距离为5，因此查找不成功的次数为5；
 
        地址6，到第三个关键字为空的地址9的距离为4，因此查找不成功的次数为4；
 
        注意地址7、8、9不用看。
 
        因此查找不成功的次数表如下表所示：
 
地址
0
1
2
3
4
5
6
7
8
9
关键字
7
14
 
8
 
11
30
18
9
 
 
 
失败次数
3
2
1
2
1
5
4
 
 
 

        所以ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7。

哈希表查找不成功时的平均查找长度计算和查找成功时的ASL
 

 例如:  关键字集合 
         { 19, 01, 23, 14, 55, 68, 11, 82, 36 }
 
 
 

 设定哈希函数 H(key) = key MOD 11 ( 表长=11 )
 
 

 
 

  
 
 
 
 
 

  
 
 查找成功次数：    1      1    2     1    3    6     2       5     1
 
 

 查找不成功次数：10    9     8    7    6    5     4       3      2    1    1
 

 
 
 

 查找成功时的平均查找长度：ASL=(1+1+2+1+3+6+2+5+1)/9=22/9
 

 查找不成功时的平均查找长度:ASL=(10+9+8+7+6+5+4+3+2+1+1)/11=56/11
 

 说明：
 第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。
   如：第0个位置到第1个没有数据位置（9）的距离为10！
 
 
 

 
 
 

 
 
 

 
 

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

 
 
 
以下求解过程是按照“计算机统考的计算方法”，不同的老师、教材在“处理冲突”上可能会有不同的方法，所以最主要的是掌握原理即可，对于考研的朋友最好掌握统考真题的解题方法。
 
题目
 
例子：（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
      
注意：查找成功时，分母为哈希表元素个数，查找不成功时，分母为哈希表长度。
     

    
    

     

    
    

     

    
 
  
 
 
 

等概率情况下查找不成功的平均查找长度：
 
 
接下来讨论不成功的情况, 看表2，计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可， 但根据哈希函数地址为MOD7，因此初始只可能在06的位置。等概率情况下，查找06位置查找失败的查找次数为：
 看地址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之间，因此循环回去)的距离为5，因此查找不成功的次数为5.
 地址6，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为4，因此查找不成功的次数为4.
 因此查找不成功的次数表如下表所示
 
 
所以ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7。
 ————————————————
 版权声明：本文为CSDN博主「dancheren」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 原文链接：https://blog.csdn.net/dancheren/article/details/76359424