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

 

以下求解过程是按照“计算机统考的计算方法”，不同的老师、教材在“处理冲突”上可能会有不同的方法，所以最主要的是掌握原理即可，对于考研的朋友最好掌握统考真题的解题方法。

题目

例子：（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

注意：查找成功时，分母为哈希表元素个数，查找不成功时，分母为哈希表长度。

最近刷面试题遇到哈希表求平均查找长度的题，发现已经忘了，查阅网上很多资料，发现关

于求查找不成功的平均查找长度，说法很多，我来借网上一篇的文章，阐述下我自己的

拙见，有什么不对的地方，欢迎大家在评论区指教~讨论

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，其他关键字同理。

(表1)

采用线性探测再散列法处理冲突，所构造的散列表为：

(表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所示

(表3)

        所以ASLsuccess= （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，到第一个关键为空的地址9的距离为5，因此查找不成功的次数为5.

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

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

(表4)

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

 

注意：这里的分母7，网上说法很多，有说关键字个数的，也有说哈希表长度的，但是个人

认为，都不是，这里的7，与散列函数有关，也就是与MOD7有关，也就是查找不成

功时的地址的个数，MOD7，地址区间为0~6，地址数为7。

总结

1. 装填因子 = （哈希表中的记录数） / （哈希表的长度）

2. 查找成功时的ASL计算

   ASL= 插入关键字时的比较次数 / 关键字个数

3. 查找不成功时的ASL计算

   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

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

除数也是模的大小

你学会了吗？