精华内容
下载资源
问答
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...

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

     

    例题:

    将关键字序列(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上没有关键字,放入即可;   

           到这一步所有关键字均已填入,散列表已经构造完成,如下表所示。

    地址0123456789
    关键字714 8 1130189 

     

    (2)等概率情况下查找成功平均查找长度:

            这一问可以根据第一问的构造过程求解:

            key7 一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1;

            key18 进行了三次探测操作,探测位置分别是5,6,7 ,因此查找次数为3;

            key9 也是三次;

            key14 进行了两次探测,因此查找次数为2。次数如下表所示:

    地址0123456789
    关键字714 8 1130189

     

    成功次数12 1 1133 

       

            所以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不用看。

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

    地址0123456789
    关键字714 8 1130189

     

    失败次数3212154   


           所以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 ...

    哈希表查找不成功时的平均查找长度计算和查找成功时的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           
    不成功次数: 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位置查找失败的查找次数为:...

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

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

    万次阅读 多人点赞 2017-10-24 23:07:31
    哈希表(等概率情况下)查找成功与查找不成功的平均查找长度计算问题,迷惑了好一会,在这里总结下来:  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着...
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长
  • 编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ...
  • 哈希表查找

    2021-04-14 10:15:34
    【参考】 ...哈希表查找性能分析5.习题 哈希表 1.哈希(hash)表的概念 为了一次存取便能得到所查记录,在记录的存储位置和它的关键字之间建立一个确定的对应关系H,以H(key)作为关键字为key的记录在表中的
  • 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表...
  • 哈希表概率情况下查找成功和查找不成功的平均查找长度的计算 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅...
  • 做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来:  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着...
  • 做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来:  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查
  • 构建出来的哈希表有八个元素,针对这八个元素的比较次数,得出ASLsuccess=(1+1+1+2+1+2+1+2)/8=11/8. 而查找失败时的平均查找长度,却是针对位置的查找。 为什么呢,因为如果我们要查找表中的元素,那么一定可以找到...
  • 它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。 2、散列存储的基本思路  以数据中每个元素的关键字K为自变量,通过散列函数H(k)...
  • 关于什么是哈希表,定义网上太多了,大家可以自行搜索,本文主要讲代码的实现 由于网上大部分是采用链地址法处理冲突,所以刚开使代码总卡着没法运行 在与哈希表的初始化 初始化方法可以自行选择,初始化,没法...
  • 哈希表与哈希查找

    2021-08-28 14:07:36
    哈希表(哈希查找) ​ 前面对于顺序表进行查找时,在判断当前数据是否是要查找的数据时,需要去通过“=”来进行判断,直到有了相等的关键字才返回地址。在这种查找方式中,“比较”是必可免的,那么是否有一种...
  • Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明
  • 1. 哈希表的概念  对于动态查找表而言,1) 表长确定;2)在设计查找表时,只知道关键字所属范围,而知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这...
  • 1. 哈希表的概念 对于动态查找表而言,1) 表长确定;2)在设计查找表时,只知道关键字所属范围,而知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,603
精华内容 11,041
关键字:

哈希表查找不成功的概率