精华内容
下载资源
问答
  • 如何计算哈希表查找失败时的平均查找长度

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

    题目描述:
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算?
    例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
    哈希函数为: H(key)=key MOD 13,哈希表长为m=15,设每个记录的查找概率相等,采用以上两种方法处理冲突,查找失败时的平均查找长度各是多少?

    今天数据结构老师讲的哈希表,留了一个“如何计算哈希表查找失败时的平均查找长度”可是把我给难为住了。(从中午12:00到下午16:00才搞懂,果然还是我太vegetable了

    几个小伙儿伴纷纷查资料,又是计算又是讨论,但是始终没有得到一致的结论。

    纠结的点主要就是:分母应该是哈希表长还是哈希函数里所给的MOD后面的13呢。查了很多资料发现里面的说法不一,而且查到的每一篇博客所给的题目都是除数(MOD后面的那个数)和哈希表长相等。(啊,可能我找的太少啦吧,找啦两三篇都是这样就去问老师啦)

    后来同学告诉我慕课上面讲的就有...anyway~现在是懂了,下面我就用大白话来描述一下我对这个“查找失败时的平均查找长度”的理解

    查找失败的次数就是指:根据哈希函数算出来你所要查找的关键字的位置,如果这个位置存的不是你的目标关键字,那么就按照你所定的存储哈希函数的规则,也就是所在位置+1向后寻找,直到找到你所要的关键字,如果遇到了表中的空位,那么就说明这个表中没有这个关键字,那么查找失败的次数就是你从“通过哈希函数算出的位置”到“表中的第一个遇到的空位”所经过的位数

    也就是说,分母指的是哈希表所给定的长度!!!

    就比如说,你的哈希表如下所示(由上面题目“采用线性探测再散列”生成的哈希表;):

    01234567891011121314
     14168275519208479231110  

    创建过程为:按照关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入

    现在我问你:我想要查找关键字“2”,那么我需要比较多少次才能知道失败了呢?

    答:根据所生成的表可以很容易的看出,关键字“2”不存在于表中。通过题目所给的哈希函数H(key)=key MOD 13可以算出关键字“2”应该在表中序号为2的位置,而如果2的位置所存的数与关键字“2”不相等,那么我需要按照“线性探测”直到找到关键字“2”。如果我没有找到关键字“2”,反而是遇到了空的位置,那么就说明关键字“2”查找失败了,那么我所走的步数就是查找失败的次数。把所有的位置查找失败的次数加起来除以表的总长度,就是“查找失败时的平均查找长度”

    ps:如果有错误欢迎指正,来自一个卑微的计算机大学僧

    答案(以线性探测再散列为例):第一行:序号;第二行:关键字;第三行:查找成功时查找长度;第四行:查找失败时查找长度

    01234567891011121314
     14168275519208479231110  
     121431139113  
    1131211109876543211

    查找失败时的平均查找长度=(1+13+12+11+10+9+8+7+6+5+4+3+2+1+1)/ 15 = 93 / 15

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

    万次阅读 多人点赞 2018-08-11 22:24:55
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (key*3) ...一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经...

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

    一、查找成功平均长度

    • 通过公式计算出存放的位置,如果该位置已经有数字了,往后找到一个空的放下。
    • 存放示意图
    存放位置0123456789
    存放数字714 8 1130189 
    • 查找时候,一次找到的查找长度为1,否则多移动一格查找长度加一。如下表
    存放位置0123456789
    存放数字714 8 1130189 
    查找长度12 1 1133 
    • 由此可得查找成功的平均查找长度为:(1+1+1+1+3+3+2)/7 = 12/7

     

    二、查找不成功平均长度

    存放位置0123456789
    存放数字714 8 1130189 

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

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

    存放位置0123456789
    存放数字714 8 1130189 
    查找不成功长度3212154   
    • 所以查找不成功平均长度:(3+2+1+2+1+5+4)/ 7 = 18/7。
    展开全文
  • 哈希表查找失败平均查找长度

    千次阅读 2019-10-09 18:02:18
    “它是中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。” 理解: 1. 散列表中已经含有之前插入的元素。 即已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。 2. 这...

    “它是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。” 理解:

    1. 散列表中已经含有之前插入的元素。

        即表已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。

    2. 这个位置是散列函数函数可以散列到的位置,不一定是表的总长。

        如:散列函数为H(key) = (keyx3) MOD 10,而表长为15,此时ASLunsucess=..../10 (而不是/15)。

       另外计算总长度时是以初始位置到散列终点位置为范围计算的,即上面这个例子是从0-9插入计算的。

    3. 计算总长度时以计算出来的位置到找到空桶为标准计算。

    展开全文
  • ![图片说明](https://img-ask.csdn.net/upload/201602/09/1455031746_265651.png) 这个失败长度是怎么计算出来的? 分子是怎么来的? 请大家具体讲讲~
  • 对于查找成功时的平均查找长度,书上有明确的定义: ...而查找失败时的平均查找长度,却是针对位置的查找。 为什么呢,因为如果我们要查找中的元素,那么一定可以找到,所以讨论查找失败就没有意义。我们讨论查找失

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

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

    除数也是模的大小

    你学会了吗?

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

    千次阅读 2017-05-27 10:40:52
    1.查找失败的情况:哈希表中不存在这个元素才会查找失败 2.查找失败的判定;见书 3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认...
  • 等概率情况下,查找06位置查找失败的查找次数为: 看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3. 地址1, 到第一个关键为空的地址2的距离为2,因此查找不成功的次数为...
  • 首先,推荐两个写的很好的关于哈希表查找——成功和不成功时的平均查找长度的博客,感谢分享! https://blog.csdn.net/longlovefilm/article/details/78009782 ... 尤其需要注意哈希表查找不成功时的平均查找长度。...
  • 11/2 哈希表查找成败平均次数计算

    千次阅读 2019-11-02 23:17:53
    散列表的装填因子 定义:α= 填入表中的元素个数 / 散列表的长度 ...通常,只要a取的合适(一般取0.7-0.8之间),哈希表平均查找长度就会是常数也就是O(1)级别的。 线性探测和二次探测必须考虑载...
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的ASL 例如: 关键字集合   { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表=11 ) 查找成功次数: 1 ...
  • 哈希表查找不成功时的平均查找长度 哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=...
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...
  • 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的...
  • 题意:给出哈希表的大小size,若不为素数则一直执行size++直至为素数。 给出n个数,进行哈希表的插入...//哈希表查找 平均查找长度 int size,n,m; int has[100005]; void insert(int x) //二次探测正增量方式进行插入
  • 散列表查找失败平均查找长度

    千次阅读 多人点赞 2020-11-01 21:04:40
    要想知道 散列表查找失败平均查找长度,就要知道什么叫做查找失败!举个栗子:8个数字 key%11 如下算好了: 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 33 1 13 12...
  • 它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。 2、散列存储的基本思路  以数据中每个元素的关键字K为自变量,通过散列函数H(k)...
  • 关于什么是哈希表,定义网上太了,大家可以自行搜索,本文主要讲代码的实现 由于网上大部分是采用链地址法处理冲突,所以刚开使代码总卡着没法运行 在与哈希表的初始化 初始化方法可以自行选择,不初始化,没法...
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找
  • 做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来:  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着...
  • 它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。   哈希表存储思路  以数据中每个元素的关键字K为自变量,通过散列函数h(k)...
  • 一、哈希表 1、概念 哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快...3、哈希表查找的时间复杂度 哈希表...

空空如也

空空如也

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

哈希表的查找失败平均长度