精华内容
下载资源
问答
  • 哈希查找 平均长度

    千次阅读 多人点赞 2018-08-11 22:24:55
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经...

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (key*3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
    (1) 请画出所构造的散列表;
    (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

    一、查找成功平均长度

    • 通过公式计算出存放的位置,如果该位置已经有数字了,往后找到一个空的放下。
    • 存放示意图
    存放位置 0 1 2 3 4 5 6 7 8 9
    存放数字 7 14   8   11 30 18 9  
    • 查找时候,一次找到的查找长度为1,否则多移动一格查找长度加一。如下表
    存放位置 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

     

    二、查找不成功平均长度

    存放位置 0 1 2 3 4 5 6 7 8 9
    存放数字 7 14   8   11 30 18 9  

    接下来讨论不成功的情况,由上表,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为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之间(因为只有7个数),因此循环回去)的距离为5,因此查找不成功的次数为5.

    地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~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。
    展开全文
  • 哈希的平均查找长度

    千次阅读 2017-08-03 15:34:17
    查找成功时的平均查找长度 查找不成功时的平均查找长度 http://www.doc88.com/p-903238204265.html

    查找成功时的平均查找长度

    查找不成功时的平均查找长度

    http://www.doc88.com/p-903238204265.html


    展开全文
  • 哈希表查找 平均查找长度 解析

    万次阅读 2012-05-03 15:23:12
    哈希表的装填因子 α 的定义如下:  α = 哈希表中元素个数 / 哈希表的长度 ...手工计算等概率情况下查找 成功 的平均查找长度公式  规则如下: ASLsucc=   其中 Ci 为置入每

           哈希表的装填因子 α 的定义如下:

                    α = 哈希表中元素个数 / 哈希表的长度

           α 可描述哈希表的装满程度。显然,α 越小,发生冲突的可能性越小,而 α 越大,发生冲突的可能性也越大

    手工计算等概率情况下查找 成功 的平均查找长度公式

           规则如下:

    ASLsucc 

           其中 C为置入每个元素时所需的比较次数
           
    例如:已知一组关键字序列(191423016820842755111079)按哈希函数H(key)=key % 13 和线性探测处理冲突构造所得哈希表ht[0..15],如图1所示

    比较次数1     2      1      4      3      1      1     3     9      1      1     3

           查找19时,通过计算H(19)= 6,ht[6].key非空且值为19查找成功,则查找关键字19 ,仅需要计算1次地址就可以找到;

           查找14时,通过计算H(14)= 1,ht[1].key非空且值为14查找成功,则查找关键字19 ,仅需要计算1次地址就可以找到;

           查找23时,通过计算H(23)=10,ht[10].key非空且值为23查找成功,则查找关键字23 ,仅需要计算1次地址就可以找到;

           同样,查找关键字68,20,11,均需要计算一次地址就可以找到;

           查找关键字01时,通过计算H(01)=1,ht[1].key非空且值为14≠01,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01,查找成功因此查找关键字01时,需要计算2次地址才可以找到;

           查找关键字55时,通过计算H(55)=3,ht[3].key非空且值为68≠55,则找第一次冲突处理后的地址H1=(3+1)% 13=4,此时,ht[4].key非空且值为27≠55,则找第二次冲突后处理地址H2=(3+2)% 13=5, ht[5].key非空且值为55查找成功,因此查找关键字27时,需要计算3次地址才能找到,同理,查找关键字10,84均需要计算3次地址才能找到;

           查找关键字27时,通过计算H(27)=1,ht[1].key非空且值为14≠27,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01≠27,则找第二次冲突后处理地址H2=(1+2)% 13=3, ht[3].key非空且值为68≠27,则找第三次冲突后处理地址H3=(1+3)% 13=4,ht[4].key非空且值为27,查找成功,因此查找关键字27时,需要计算4次地址才可以找到;

           根据上面的方法,查找关键字79时,通过计算H(79)=1,ht[1].key非空且值为14≠79,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01≠79,则找第二次冲突后处理地址H2=(1+2)% 13=3, ht[3].key非空且值为68≠79,则找第三次冲突后处理地址H3=(1+3)% 13=4,ht[4].key非空且值为27≠79,则找第四次冲突后处理地址H4=(1+4)% 13=5,ht[5].key非空且值为55≠79,则找第五次冲突后处理地址H5=(1+5)% 13=6,ht[6].key非空且值为19≠79则找第六次冲突后处理地址H6=(1+6)% 13=7,ht[7].key非空且值为20≠79,则找第七次冲突后处理地址H7=(1+7)% 13=8,ht[8].key非空且值为84≠79,则找第八次冲突后处理地址H8=(1+8)% 13=9,ht[9].key非空且值为79,查找成功,因此查找关键字79时,需要计算9次地址才可以找到。

           据此计算公式,对如图8.27的哈希表,采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找成功的平均查找长度为:

    ASL(12)==2.5

           为便于计算, 在图8.27哈希表下方加注圆圈, 圆圈内表示的是有冲突时的计算次数, 如代表需要一次地址计算就可找到的关键字有6个,依此类推,即可得到计算结果。

    同理据此公式, 对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找成功的平均查找长度为:

    ASL(12)succ=

     

    手工计算在等概率情况下查找 不成功 的平均查找长度公式

    查找不成功的情况:(1)  遇到空单元

                                   (2)  按解决冲突的方法完全探测一遍后仍未找到。0 -> r-1 个不成功查找的入口,从每个入口进入后,直到确定查找不成功为止,其关键字的比较次数就是与该入口对应的不成功查找长度。

           

    规则如下:

    ASLunsucc 

           其中Ci为函数取值为 i 时确定查找不成功时比较次数

           据此计算公式,对如图8.27的哈希表,采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找不成功的平均查找长度为:

    ASL(13)==6

           同理据此公式,对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找不成功的平均查找长度为:

    ASL(13)unsucc=

    链地址法:

     











    展开全文
  • 哈希算法的平均查找长度计算

    万次阅读 多人点赞 2017-07-29 23:21:54
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。  Ans:  (1).首先明确一个概念装载因子,装载因

    将关键字序列(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中的关键字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所示 
    这里写图片描述

    所以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. 
    因此查找不成功的次数表如下表所示

    这里写图片描述

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

    展开全文
  • 哈希平均查找长度

    万次阅读 多人点赞 2017-08-13 10:53:31
    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。注:没给哈希表长度,给出装填因子时,可求哈希...
  • 如何计算哈希表查找失败时的平均查找长度

    千次阅读 多人点赞 2020-04-30 18:20:01
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录...
  • 哈希表查找失败的平均查找长度

    千次阅读 2019-10-09 18:02:18
    “它是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。” 理解: 1. 散列表中已经含有之前插入的元素。 即表已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。 2. 这...
  • 哈希的平均查找长度可以为0吗,老师上课说可以,说是不用比较,但我感觉至少也要1啊
  • 哈希表查找不成功的平均查找长度

    千次阅读 2017-05-27 10:40:52
    1.查找失败的情况:哈希...3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认查找失败; 4.因此哈希函数有多少个取值,查找时就有多少个
  • 哈希表查找——成功和不成功时的平均查找长度

    万次阅读 多人点赞 2017-09-17 13:27:21
    哈希表查找——成功和不成功时的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考...
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的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 ...
  • 哈希表查找不成功时的平均查找长度 哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=...
  • 等概率情况下查找不成功的平均查找长度: 接下来讨论不成功的情况, 看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率...
  • 题意:给出哈希大小size,若不为素数则一直执行size++直至为素数。 给出n个数,进行哈希插入...//哈希表查找 平均查找长度 int size,n,m; int has[100005]; void insert(int x) //二次探测正增量方式进行插入
  • [腾讯]已知一个线性表(38,25,74,63,52,48),假定采用散列函数 h(key)=key%7 计算散列地址,并散列存储在散列表A[0…6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为...
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白平均查找长度是期望,那么你就按照求期望方法来求平均查找长
  • 哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅...
  • 对于查找成功时的平均查找长度,书上有明确的定义: 而题目设定条件都是在等概率下查找,所以ASL=(C0+C1+...+Cn)*1/n. 这就说明了查找成功是针对关键字查找的,最后除以关键字的总个数。 我们来看一道书上的例题...
  • 有多种不同基于哈希的数据结构,但最常用数据结构是哈希表。 哈希表通常使用数组实现。 哈希数据结构性能取决于以下三个因素: 哈希函数 哈希大小 碰撞处理方法 下图展示了如何在数组中映射哈希...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 441
精华内容 176
关键字:

哈希查找的平均查找长度