精华内容
下载资源
问答
  • 哈希表查找不成功的概率
    万次阅读 多人点赞
    2020-11-28 21:49:49

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

    例题:

    将关键字序列(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
    关键字71481130189

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

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

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

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

            key9 也是三次;

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

    地址0123456789
    关键字71481130189

    成功次数1211133

       

            所以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
    关键字71481130189

    失败次数3212154


           所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。

    更多相关内容
  • 哈希表查找——成功和不成功时的平均查找长度

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

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

     

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

    题目

    例子:(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
    714 8 1130189 

     

    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
    714 8 1130189 
    12 1 1133 
    所以总的查找成功的平均查找长度= (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
    714 8 1130189 
    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

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

    展开全文
  • 最近刷面试题遇到哈希表求平均查找长度的题,已经忘了,来记录下 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明

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

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

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

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

    Key78301118914
    H(Key)0365560

    (表1)

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

    地址0123456789
    关键字714 8 1130189 

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

    Key78301118914
    Count1111332

    (表3)

            所以ASLsuccess= (1+1+1+1+3+3+2)/ 7 = 12/7。  

    等概率情况下查找不成功的平均查找长度:

    地址0123456789
    关键字714 8 1130189 

    (表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.

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

    Key78301118914
    Count3212154
    (表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 = 查找不成功的比较次数 / 查找不成功时的地址个数

    展开全文
  • 构建出来的哈希表有八个元素,针对这八个元素的比较次数,得出ASLsuccess=(1+1+1+2+1+2+1+2)/8=11/8. 而查找失败时的平均查找长度,却是针对位置的查找。 为什么呢,因为如果我们要查找表中的元素,那么一定可以找到...

    对于查找成功时的平均查找长度,书上有明确的定义:
    在这里插入图片描述
    而题目设定条件都是在等概率下查找,所以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

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

    除数也是模的大小

    你学会了吗?

    展开全文
  • 哈希表查找不成功的ASL问题

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

    千次阅读 2021-12-17 02:07:18
    哈希表及其查找哈希表及其查找哈希表哈希函数1. 直接定址法2. 数字分析法3. 平方取中法4. 折叠法5. 除留余数法6. 随机数法哈希处理冲突方法1. 开放定址法线性探测再散列 :二次探测再散列:伪随机探测再散列:2. 再...
  • 哈希表与哈希查找

    2021-08-28 14:07:36
    哈希表(哈希查找) ​ 前面对于顺序表进行查找时,在判断当前数据是否是要查找的数据时,需要去通过“=”来进行判断,直到有了相等的关键字才返回地址。在这种查找方式中,“比较”是必可免的,那么是否有一种...
  • 完整举例: 在地址空间为0~16的散列区中,对以下关键字序列构造两个...求查找成功与查找不成功的平均查找长度。 很据:H(x)=i/2;除不尽的,向下取整即可。如下所示: Jan - 5 Feb - 3 Mar -6 Apr -0 May - 6 June -5
  • //使用哈希函数:H(k)=3*k MOD length,并采用开放定址法处理冲突。试对输入的关键字序列构造哈希表哈希表长度为length, //求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。
  • 给定一组查找关键字(32,15,7,11,4,28,56,61,79),哈希表长为m=12,请按照除留余数法设计一个哈希函数,设每个记录的查找概率相等。 (1)画出按照线性探测再散列处理冲突得到的哈希表(给出求解过程),并计算等...
  • 一、哈希表 1、概念 哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快...3、哈希表查找的时间复杂度 哈希表...
  • 哈希算法 查找失败

    千次阅读 2019-10-08 16:08:07
    step1:先将所有的数据装入哈希表汇总 1%11 = 1,没有冲突 13%11 = 2,没有冲突 12%11 = 1,下标1的位置上放置了数据1,此时冲突了,使用 线性探测法处理冲突,下标1上已经有数据了,所以往后查,此时下标2上也有...
  • 如何计算哈希表查找失败时的平均查找长度

    万次阅读 多人点赞 2020-04-30 18:20:01
    题目描述: ...哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录的查找概率相等,采用以上两种方法处理冲突,查找失败时的平均查找长度各是多少? 今天数据结构老师讲的哈希表,留了一个“...
  • 哈希表查找

    2021-04-14 10:15:34
    【参考】 ...哈希表查找性能分析5.习题 哈希表 1.哈希(hash)表的概念 为了一次存取便能得到所查记录,在记录的存储位置和它的关键字之间建立一个确定的对应关系H,以H(key)作为关键字为key的记录在表中的
  • 哈希表:线性探测法和链地址法求查找成功与不成功的平均查找
  • 哈希表查找---------处理冲突的方法

    千次阅读 2020-05-27 11:29:20
    这类查找表的平均查找长度都是为0的。 所以,对于查找表,希望ASL(平均查找长度) = 0。只有预先知道所查找的关键字在中的位置,即要求:记录在中的位置和其关键字存在一种确定的关系。 关键字(key) ----H--...
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。  下面看下2010年...
  • 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表...
  • C++实现哈希表创建、查找、显示、计算ALS(详细)。针对某个数值序列,设计一个哈希表,完成相应的建表和查表顺序。哈希函数用除留余数法构造,用线性探测再散列的方法处理哈希地址冲突。针对给定的数列:{23,5,17,...
  • 关于什么是哈希表,定义网上太多了,大家可以自行搜索,本文主要讲代码的实现 由于网上大部分是采用链地址法处理冲突,所以刚开使代码总卡着没法运行 在与哈希表的初始化 初始化方法可以自行选择,初始化,没法...
  • 哈希表查找 的 平均长度

    万次阅读 多人点赞 2018-08-11 22:24:55
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经...
  • 1. 哈希表的概念 对于动态查找表而言,1) 表长确定;2)在设计查找表时,只知道关键字所属范围,而知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这个...
  • 哈希表查找不成功平均长度例子

    千次阅读 2020-04-30 16:08:40
    接下来讨论不成功的情况, 看2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率情况下,查找06位置查找失败的查找次数为:...
  • 四、哈希表的装填因子 装填因子 = (哈希表中的记录数) / (哈希表的长度) 装填因子是哈希表装满程度的标记因子。值越大,填入表中的数据元素越多,产生冲突的可能性越大。 五、不同处理冲突的平均查找长度 ...
  • 【算法与数据结构 10】哈希表——高效查找的利器

    千次阅读 多人点赞 2020-09-24 17:03:21
    虽然哈希表查找的细节过程还比较麻烦,但因为一些高级语言的黑盒化处理,开发者并需要实际去开发底层代码,只要调用相关的函数就可以了。 3.2 哈希表的优缺点 优势:它可以提供非常快速的插入-删除-查找操作,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,293
精华内容 12,917
热门标签
关键字:

哈希表查找不成功的概率