精华内容
下载资源
问答
  • 等概率情况下查找不成功的平均查找长度: 接下来讨论不成功的情况, 看2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率...

    等概率情况下查找不成功的平均查找长度:
    在这里插入图片描述

    接下来讨论不成功的情况, 看表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

    展开全文
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的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 ...

    哈希表查找不成功时的平均查找长度计算和查找成功时的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!

     

     

     

    展开全文
  • 哈希表查找——成功和不成功的平均查找长度

    万次阅读 多人点赞 2017-09-17 13:27:21
    哈希表查找——成功和不成功的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考...

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


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

    题目

    例子:(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
               按关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入。

    0123456789
    71481130189

    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日修改,多谢@一楼的朋友指正】

    0123456789
    71481130189
    1211133
    所以总的查找成功的平均查找长度= (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.
    于是得到如下数据:
    0123456789
    71481130189
    3212154
    则查找不成功的平均查找长度 = (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

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

    展开全文
  • 哈希表查找成功的平均查找长度

    千次阅读 2017-05-27 10:40:52
    1.查找失败情况:哈希表中不存在这个元素才会查找失败 2.查找失败判定;见书 3.因为所查找的数是不确定,因此可以取遍哈希函数所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认...

    1.查找失败的情况:哈希表中不存在这个元素才会查找失败

    2.查找失败的判定;见书

    3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认查找失败;

    4.因此哈希函数有多少个取值,查找时就有多少个入口

    展开全文
  • 哈希表查找成功的平均查找长度 哈希表查找成功的平均查找长度(zz)哈希表查找成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=...
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...
  • 哈希表查找 平均长度

    千次阅读 多人点赞 2018-08-11 22:24:55
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经...
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白平均查找长度是期望,那么你就按照求期望方法来求平均查找长

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 190
精华内容 76
关键字:

哈希表查找成功的平均查找长度