最近复习数据结构中的哈希表，发现在计算等概率情况下查找不成功的平均查找长度时不太理解，不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了，总结如下。

 


例题：

将关键字序列（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。

哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算


最近复习了下数据结构中的哈希表，发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫，不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了，所以记录下来以供以后查阅。
   下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。
Question1:
将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：      H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。
(1) 请画出所构造的散列表。
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
Ans：
(1).首先明确一个概念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等于 关键字总数/哈希表的长度。 根据题意，我们可以确定哈希表的长度为 L = 7/0.7 = 10；因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。
H(Key) = (keyx3) MOD 7, 例如key=7时， H(7) = (7x3）%7 = 21%7=0，其他关键字同理。
Key
7
8
30
11
18
9
14
H(Key)
0
3
6
5
5
6
0
(表1)
采用线性探测再散列法处理冲突，所构造的散列表为：
地址
0
1
2
3
4
5
6
7
8
9
关键字
7
14


8


11
30
18
9


(表2)
下面对散列表的构造方式加以说明，注意表1中的关键字7和14，30和9， 11和18，这三组关键子的H(Key)值相同，这在构建散列表时就会产生冲突，因为他们的地址相同，所以要通过一定的冲突处理方法来解决这个问题。依题，采用线性探测再散列法处理冲突。下面详细介绍如何构建散列表：
       第一个key 7，它的地址是0，因此放到散列表的数组下表为0的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
       第二个key 8，它的地址是3，因此放到散列表的数组下表为3的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
       第三个key 30，它的地址是6，因此放到散列表的数组下表为6的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
       第四个key 11，它的地址是5，因此放到散列表的数组下表为5的位置，这个位置上没有关键字，因此没有冲突可以直接填入；
       第五个key 18，它的地址是5，因此放到散列表的数组下表为5的位置，但这个位置上已经有关键字11，遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探测下一个位置6, 6这个位置上已经存在关键字30则继续增加步长1，因此现在的新地址应为7，位置7上没有关键字，放入即可，到此冲突已经解决；
       第六个key 9，它的地址是6，因此放到散列表的数组下表为6的位置，但这个位置上已经有关键字30，遇到了冲突，探测下一个位置7, 7这个位置上已经存在关键字18则继续增加步长1，因此现在的新地址应为8，位置8上没有关键字，放入即可；   
       第七个key 14，它的地址是0，因此放到散列表的数组下表为0的位置，但这个位置上已经有关键字7，遇到了冲突，探测下一个位置1, 位置1上没有关键字，放入即可；   
       到这一步所有关键字均已填入，散列表已经构造完成，如表2所示。
（2）等概率情况下查找成功平均查找长度：
        这一问可以根据第一问的构造过程求解：
        key7一次就填入了表中，因此查找次数为1，同理8， 30， 11查找次数均为1； key18 进行了3次放入操作，探测位置分别是5，6，7 ，因此查找次数为3；key9也是3次；key14 进行了两次探测，因此查找次数为2。次数表如表3所示
Key
7
8
30
11
18
9
14
Count
1
1
1
1
3
3
2
(表3)
        所以ASLsuccess= （1+1+1+1+3+3+2）/ 7 = 12/7。  
        等概率情况下查找不成功的平均查找长度：
        接下来讨论不成功的情况, 看表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(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为5，因此查找不成功的次数为5.
        地址6，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为4，因此查找不成功的次数为4.
        因此查找不成功的次数表如下表所示
Key
7
8
30
11
18
9
14
Count
3
2
1
2
1
5
4
(表4)


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

哈希表查找不成功时的平均查找长度
哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算？解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！

例如：散列函数为hash(x)=x MOD 13，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？

     地址： 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
说明：
查找成功代表找到KEY所在位置所用的次数
第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。
至少要查询多少次才能确认没有这个值。
（1） 查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失败。
（2） 查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失败。
（3） 查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失败。
（4） 查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失败。
（5） 查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失败。
（6） 查询hash(x)=5,至少要查询4次遇到表值为空的时候，才能确认查询失败。
（7） 查询hash(x)=6,至少要查询3次遇到表值为空的时候，才能确认查询失败。
（8） 查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失败。
（9） 查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失败。
（10）查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失败。
（11）查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失败。
（12）查询hash(x)=11,至少要查询1次遇到表值为空的时候，才能确认查询失败。


（13）查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候，才能确认查询失败。
 
http://hi.baidu.com/dfsfsdfwe/item/35f8f1c79e91f26389ad9e53

继续小结，做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题，迷惑了好一会，在这里总结下来：
  首先，你要明白的是平均查找长度求的是期望，那么你就按照求期望的方法来求平均查找长度吧，千万记着期望怎么求平均查找长度就怎么求啊。
  题目：
在地址空间为0~16的散列区中，对以下关键字序列构造两个哈希表：

{Jan, Feb, Mar, Apr, May,  June, July, Aug, Sep, Oct, Nov, Dec}

（1） 用线性探测开放地址法处理冲突；

（2） 用链地址法（开散列存储）处理冲突 

并分别求这两个哈希表在等概率情况下查找成功和查找不成功时的平均查找长度。设哈希函数为 

H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下：

A B C D E F G H I  J    K   L  M  N  O   P   Q   R  S  T   U   V   W  X  Y   Z

1 2 3 4  5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
  解决如下：
(1) 线性探测进入散列区的次序如下，X 代表冲突，要找下一个空格

Jan -> 5

Feb -> 3

Mar -> 6

Apr -> 0

May -> 6X -> 7

June -> 5X -> 6X -> 7X -> 8

July -> 5X -> 6X -> 7X -> 8X -> 9

Aug -> 0X -> 1

Sep -> 9X -> 10

Oct -> 7X -> 8X -> 9X -> 10X -> 11

Nov -> 7X -> 8X -> 9X -> 10X -> 11X -> 12

Dec -> 2

0


1


2


3


4


5


6


7


8


9


10


11


12


13


14


15


Apr


Aug


Dec


Feb


 


Jan


Mar


May


Jun


July


Sep


OCt


Nov


 


 


 




  很明显，查找成功时，查找Jan、Feb、Mar等仅需要一次，其余的也可以由上面看出来

  所以查找成功时平均查找长度 (ASL) = (1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 2 + 5 + 6 + 1) / 12 = 31/12 = 2.58 为什么是除以12呢？因为查找成功的情况总共有12种啊
  查找不成功时呢？什么是查找不成功呢？查找不成功就是从查找位置开始直到一个位置为空需要比较的次数。
  首先，26/2=13，也就是说查找不成功的情况也只能出现在0~13之间，只有这14种情况。
  举个例子来说，查找Aay吧，根据hash表，与Apr比较不匹配，接着与Aug比较又是不匹配，接着与Dec比较又是不匹配，又与Feb比较又是不匹配，到了4位置的时候为空了，即4上内容与nullkey比较，结果为空，所以查找Aay失败，查找长度为5。同理也能计算其他的。
  最终平均查找失败时平均查找长度为（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14=60/14。注意啊，这里是除以14啊。（这是求期望的方法啊）


(2) 链地址法

0 之下有 Apr, Aug

2 之下有 Dec

3 之下有 Feb

5 之下有 Jan, June, July

6 之下有 Mar, May

7 之下有 Oct, Nov

9 之下有 Sep

查找成功时候，查 Apr, Dec, Feb, Jan, Mar, Oct, Sep 各需 1 次，查 Aug, June, May, Nov 各需 2 次，查 July 需 3 次。


所以查找成功时平均查找长度 (ASL) = (1 * 7 + 2 * 4 + 3 * 1) / 12 = 18/12 = 1.5
查找失败时平均查找长度：举个例子吧，查找Boy,2/2=1，而1的地方的指针为空，就不用比较就可以知道不存在，查找产度为0。查找Aay，与Apr比较不匹配，与Aug比较不匹配，同时，Aug指向下一个节点的指针为空，就可以知道查找失败，查找长度为2。
 所以查找失败的平均查找长度：（2+1+1+3+2+2+1）/14=12/14。