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

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

    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。

    注:没给哈希表长度,给出装填因子时,可求哈希表长度,
    可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。

    线性探测法

    这里写图片描述

    由上构造的哈希表如下:
    这里写图片描述

    等概率下查找成功的平均查找长度为:
    ASL=(1+3+1+1+2+4)/6=2

    链地址法
    这里写图片描述

    由上构造的哈希表如下:
    这里写图片描述

    等概率下查找成功的平均查找长度为:
    ASL=(1*4+2*2)/6=1.3

    展开全文
  • 有多种不同基于哈希数据结构,但最常用数据结构是哈希表哈希表通常使用数组实现。 哈希数据结构性能取决于以下三个因素: 哈希函数 哈希表的大小 碰撞处理方法 下图展示了如何在数组中映射哈希...

    哈希表(又名为是散列表)
    散列是一个用于唯一标识对象并在一些预先计算的唯一索引(称为“密钥”)存储每个对象的过程。因此,对象以“键值”对的形式存储,这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构,但最常用的数据结构是哈希表。

    哈希表通常使用数组实现。

    哈希数据结构的性能取决于以下三个因素:

    哈希函数
    哈希表的大小
    碰撞处理方法
    下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。
    在这里插入图片描述
    今天主要讲一下哈希表平均查找长度ASL计算,也是常见面试题之一
    题目:关键字序列为:{30,25,80,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。

    注:没给哈希表长度,给出装填因子时,可求哈希表长度,
    可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。

    线性探测法(通过数组保存)
    H(30)=30%7=2
    H(25)=25%7=4
    H(80)=80%7=3,和30冲突,往后移一位:4,又与25冲突,继续后移一位:5
    H(63)=63%7=0
    H(52)=52%7=3,后移三位为6
    H(48)=48%7=6,与52冲突,后移一位为0,再后移一位为1
    结果为:
    30 ——2
    25——4
    80——5
    63——7
    52——6
    48——1
    平均查找长度:查找次数和/数组个数
    (1+1+3+1+4+3)/6=2.2

    链地址法 (以链表形式存储)
    取模后值相同的在同一个链表中,即
    0——63
    1
    2
    3——30——80——52
    4——25
    5
    6——48
    等概率下查找成功的平均查找长度为:
    ASL=(14+21+3*1)/6=1.5

    展开全文
  • 如何计算哈希表查找失败时的平均查找长度

    千次阅读 多人点赞 2020-04-30 18:20:01
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为: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向后寻找,直到找到你所要的关键字,如果遇到了表中的空位,那么就说明这个表中没有这个关键字,那么查找失败的次数就是你从“通过哈希函数算出的位置”到“表中的第一个遇到的空位”所经过的位数

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

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

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
      14 1 68 27 55 19 20 84 79 23 11 10    

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

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

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

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

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

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
      14 1 68 27 55 19 20 84 79 23 11 10    
      1 2 1 4 3 1 1 3 9 1 1 3    
    1 13 12 11 10 9 8 7 6 5 4 3 2 1 1

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

    展开全文
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(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上没有关键字,放入即可;   

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

    地址 0 1 2 3 4 5 6 7 8 9
    关键字 7 14   8   11 30 18 9  

     

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

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

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

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

            key9 也是三次;

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

    地址 0 1 2 3 4 5 6 7 8 9
    关键字 7 14   8   11 30 18 9

     

    成功次数 1 2   1   1 1 3 3  

       

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

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

    地址 0 1 2 3 4 5 6 7 8 9
    关键字 7 14   8   11 30 18 9

     

    失败次数 3 2 1 2 1 5 4      


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

    展开全文
  • 采用除留余数法实现哈希表的创建,任意采用一种处理冲突方法解决冲突,计算哈希表的平均查找长度。实现以下功能:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数定义为:H(key)=key MOD 13, 哈希...
  • 哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅...
  • 哈希表查找不成功时的平均查找长度计算和查找成功时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 ...
  • Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表存储空间是一个下标从0开始一维数组,散列...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明
  • 题干太长了,这次不写题干了,主要说说散列表,又叫哈希表(hash table) 散列表是一种存储数据方法,通过散列表,可以实现直接用关键字(key)访问数据所在位置。具体实现方法为使用散列函数(哈希函数)H(key),对...
  • 哈希表查找 平均查找长度 解析

    万次阅读 2012-05-03 15:23:12
    哈希表的装填因子 α 定义如下:  α = 哈希表中元素个数 / 哈希表的长度 ...手工计算等概率情况下查找 成功 的平均查找长度公式  规则如下: ASLsucc=   其中 Ci 为置入每
  • ![图片说明](https://img-ask.csdn.net/upload/201602/09/1455031746_265651.png) 这个失败的长度是怎么计算出来? 分子是怎么来? 请大家具体讲讲~
  • 哈希表查找——成功和不成功时的平均查找长度

    万次阅读 多人点赞 2017-09-17 13:27:21
    哈希表查找——成功和不成功时的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考...
  • 哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=x MOD 13,用线性探测,建立了哈希表...
  • https://zhidao.baidu.com/question/214308488.html
  • 哈希表查找 平均长度

    千次阅读 多人点赞 2018-08-11 22:24:55
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放位置,如果该位置已经...
  • 在与哈希表的初始化 初始化方法可以自行选择,不初始化,没法判断该位置是否存有数据,初始为-1,就可以依据num值判断,该位置是否被存入值 for(i=0;i<13;i++){ h[i].num = -1; ...
  • 编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 165
精华内容 66
关键字:

哈希表平均查找长度的计算