精华内容
下载资源
问答
  • 首先,推荐两个写的很好的关于哈希表查找——成功不成功时平均查找长度的博客,感谢分享! https://blog.csdn.net/longlovefilm/article/details/78009782 ... 尤其需要注意哈希表查找不成功时平均查找长度。...

    首先,推荐两个写的很好的关于哈希表查找——成功和不成功时的平均查找长度的博客,感谢分享!

    https://blog.csdn.net/longlovefilm/article/details/78009782

    https://blog.csdn.net/wangran51/article/details/8826633/#commentBox

    尤其需要注意哈希表查找不成功时的平均查找长度。

    注意:查找成功时,分母为哈希表元素个数;

    查找不成功时,分母为哈希表长度。

    计算查找不成功的次数就直接找关键字到

    第一个地址上关键字为空的距离即可;

    哈希表查找不成功怎么计算?

    解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数!

    展开全文
  • 哈希表查找不成功时平均查找长度计算和查找成功时的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!





    展开全文
  • 查找不成功时平均查找长度相当于在表中查找元素不成功时的平均比较次数,可以理解为向表中插入某个元素,该元素在每个位置都有可能,然后计算出在每个位置能够插入需要比较的次数,再除以表长即为查找不成功时的...

    Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。
      查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数
    查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数,可以理解为向表中插入某个元素,该元素在每个位置都有可能,然后计算出在每个位置能够插入时需要比较的次数,再除以表长即为查找不成功时的平均查找长度

    下面举个例子:
    将关键字序列{7, 8, 30, 11, 18, 9, 14}散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,长度为10,即{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。散列函数为: H(key) = (key * 3) % 7,处理冲突采用线性探测再散列法。
    求等概率情况下查找成功和查找不成功的平均查找长度。

    解:

    1 求散列表

    H(7) = (7 * 3) % 7 = 0
    H(8) = (8 * 3) % 7 = 3
    H(30) = 6
    H(11) = 5
    H(18) = 5
    H(9) = 6
    H(14) = 0
    

    按关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入。
    H(7) = 0,key = 7应插在第0个位置,因为第0个位置为空,可以直接插入。
    H(8) = 3,key = 8应插在第3个位置,因为第3个位置为空,可以直接插入。
    H(30) = 6,key = 30应插在第6个位置,因为第6个位置为空,可以直接插入。
    H(11) = 5,key = 11应插在第5个位置,因为第5个位置为空,可以直接插入。
    H(18) = 5,key = 18应插在第5个位置,但是第5个位置已经被key=11占据了,所以往后挪一位到第6个位置,但是第6个位置被key=30占据了,再往后挪一位到第7个位置,这个位置是空的,所以key=18就插到这个位置
    H(9) = 6,key = 9应插在第6个位置,但是第6个位置已经被key = 30占据,所以需要往后挪一位到第7个位置,但是第7个位置已经被key = 18占据,所以再往后挪移到第8个位置,这个位置是空的,所以key = 9就插到这个位置。
    H(14) = 0,key = 14应插在第0个位置,但第0个位置已被key=7占据,所以往后挪移一位到第1个位置,这个位置是空的,所以key=14就插到这个位置。

    最终的插入结果如下表所示:

    address0123456789
    key71481130189

    2 求查找成功的平均查找长度

    查找7,H(7) = 0,在0的位置,一下子就找到了7,查找长度为1。
    查找8,H(8) = 3,在3的位置,一下子就找到了8,查找长度为1。
    查找30,H(30) = 6,在6的位置,一下子就找到了30,查找长度为1。
    查找11,H(11) = 5,在5的位置,一下子就找到了11,查找长度为1。
    查找18,H(18) = 5,第一次在5的位置没有找到18,第二次往后挪移一位到6的位置,仍没有找到,第三次再往后挪移一位到7的位置,找到了,查找长度为3。
    查找9,H(9) = 6,第一次在6的位置没找到9,第二次往后挪移一位到7的位置,仍没有找到,第三次再往后挪移一位到8的位置,找到了,查找长度为3.
    查找14,H(14) = 0,第一次在0的位置没找到14,第二次往后挪移一位到1的位置,找到了,查找长度为2。

    所以,查找成功的平均查找长度为(1 + 1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7。

    3 求查找不成功的平均查找长度

    查找不成功,说明要查找的数字肯定不在上述的散列表中。
    因为这里哈希函数的模为7,所以要查找的数的初始地址只可能位于0~6的位置上。
    地址0,到第一个关键字为空的地址2需要比较3次,因此查找不成功的次数为3。比如要查找的数为28,H(28) = (28 * 3) % 7 = 0。即28对应的地址是0,由于存放在0位置的数是7,所以往后挪移一位,发现在1位置存放的数是14,继续往后挪一位,发现位置2上没有数。至此就知道28不在这个哈希表里,即查找28失败。
    地址1,到第一个关键字为空的地址2需要比较2次,因此查找不成功的次数为2。
    地址2,到第一个关键字为空的地址2需要比较1次,因此查找不成功的次数为1。
    地址3,到第一个关键字为空的地址4需要比较2次,因此查找不成功的次数为2。
    地址4,到第一个关键字为空的地址4需要比较1次,因此查找不成功的次数为1。
    地址5,到第一个关键字为空的地址9需要比较5次,因此查找不成功的次数为5。
    比如要查找的数为4,H(4) = (4 * 3) % 7 = 5,所以从地址5开始查找,最终发现地址5、地址6、地址7、地址8上存放的数都不是5,并且地址9的位置上没放数据,至此可知5不在这个哈希表里。
    地址6,到第一个关键字为空的地址9需要比较4次,因此查找不成功的次数为4。
    所以,查找不成功的平均查找长度为(3 + 2 + 1 + 2 + 1 + 5 + 4)/ 7 = 18 / 7。

    注意

    为了提高阅读和理解的效率,在这边强调一下:

    • 求成功的ASL是针对于每个数字的,即你要把所有数字的查找后的次数做个累加,最后除的数字是元素的个数!这个很好理解,因为我们研究的也是所有元素的查找次数。
    • 求不成功的ASL针对的是每个位置!即每个位置往后找第一个为空的位置所比较的次数,然后累加最后除以哈希表的规模(如果是除留余数法,这个规模就是那个模数)。显然,这里的每个位置是要在哈希表内的位置,即你使用的哈希函数求出的所有可能的位置,对于除留余数法哈希表的大小取决于你选的那个p(大部分情况下是质数),而不是本身数组的大小。具体原因可以看上面那个例子,或者这里再举个例子:假如你模的是2,显然哈希函数算出来的数字非0即1,只有这两个位置,即使你存放的空间由10000,哈希表的大小还是只有2,所以你最后除的分母仍是2而不是10000。

    版权声明:本文为CSDN博主「海天一树」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/haishu_zheng/article/details/77278119

    展开全文
  • 一、链地址法在等概率下查找成功和查找不成功平均查找长度:将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功...

    一、链地址法在等概率下查找成功和查找不成功的平均查找长度:

    题目

    将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功的平均查找长度

    1mod11=1,所以数据1是属于地址1
    13mod11=2,所以数据13是属于地址2
    12mod11=1,所以数据12也是属于地址1(这个数据是数据1指针的另一个新数据)
    34mod11=1,所以数据34是属于地址1(这个数据是数据12指针的另一个新数据)
    38mod11=5,所以数据38是属于地址5
    33mod11=0,所以数据33是属于地址0
    27mod11=5,所以数据27是属于地址5,(这个数据是数据38指针的另一个新数据)
    22mod11=0,所以数据22是属于地址0,(这个数据是数据33指针的另一个新数据)

    链地址法处理冲突构造所得的哈希表如下:
    链地址法

    查找成功时: ASL=(3×1+2×3+1×4)/8=13/8, 其中红色标记为查找次数。也就是说,需查找1次找到的有4个,其它以此类推…

    查找不成功时:ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11;或者 ASL=(7×1+1×2+2×3+1×4 )/11=19/11,其中红色标记为查找次数。以第一个3为例,其对应于0地址位,确定查找不成功需比较3次,其它以此类推…

    原理:

    链地址法插入数据的时候采用采用头插法(插入每个链表的表头),因为习惯默认新插入进来的数据,马上就要访问到。下边是实现的伪代码

    CHAINED-HASH-INSERT(T, x)
        insert x at the head of list T[h(key[x])]
    CHAINED-HASH-SEARCH(T, k)
        search for an element with key k in list T[h(k)]
    CHAINED-HASH-DELETE(T, x)
         delete x from the list T[h(key[x])]
    
    例子

    例如,查找16的时候,根据散列函数在地址为5的链表查找,首先找到27,再找到38,然后找到38的后继节点为空,查找结束。查找结果失败,共查找3次。

    二,线性探测再散列法处理冲突

    对于这部分,个人觉得有人整理的比较好,很有条理,很清晰,可以借鉴一下,链接如下:
    线性探测再散列法处理冲突

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

    千次阅读 2017-05-27 10:40:52
    1.查找失败的情况:哈希...3.因为所查找的数是确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定,确认查找失败; 4.因此哈希函数有多少个取值,查找时就有多少个
  • 【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找的判定树,并指出在等概率查找成功平均查找长度,以及查找失败所需的最多的关键字比较次数。 判定树如下: 图1-1判定树 ...
  • 散列表查找成功不成功时平均查找长度

    万次阅读 多人点赞 2018-09-16 17:27:58
    已知散列表长度为13,散列函数为H(key)=key % 11,处理冲突的方法为线性探测法,请画出依次插入关键字(10,8,40,27,21,57,46,23,19,56)以后的散列表,并计算查找成功不成功时平均查找长度。 解:散列表是哈希表...
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功平均查找长度时不太理解,知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...
  • (1) 输出n=11的判定树并求成功情况下的平均查找长度ASl (2) 通过构造判定树可以求得的成功情况下的平均查找长度ASL1;当把含有n个节点的判定树看成是一棵满二叉树,其成功情况下平均查找长度的人理论值ASL2...
  • 二叉排序树查找不成功平均查找长度

    万次阅读 多人点赞 2016-04-11 20:32:53
    在看二叉排序树查找分析,对“二叉排序树查找不成功平均查找长度”不是很理解,上网查了一下,稍微小结一下:  假如一棵二叉排序树如下:    那么查找不成功平均查找长度是:(2*2+3*3+4*2)/7=21/7  ...
  • 哈希表查找不成功时平均查找长度 哈希表查找不成功时平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=...
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长
  • 做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来:  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着...
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功平均查找长度时比较迷茫,知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。  下面看下2010年...
  • 本文采用线性探测法解决冲突 ...初始化方法可以自行选择,初始化,没法判断该位置是否存有数据,初始为-1,就可以依据num的值判断,该位置是否被存入值 for(i=0;i<13;i++){ h[i].num = -1; ...
  • 求折半查找成功时平均查找长度

    千次阅读 2019-02-14 09:30:30
    * 求折半查找成功时平均查找长度 * 实验目的: * 深入掌握折半查找过程和折半查找算法分析 * 实验内容: * 设计程序,建立有序序列R[0...n-1]进行二分查找产生的判断树, * 在此基础上完成如下功能: * 1、输出n=11...
  • 哈希表:线性探测法和链地址法求查找成功不成功平均查找
  • Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列...(2) 分别计算等概率情况下查找成功和查找不成功平均查找长度。 Ans: (1).首先明

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,025
精华内容 14,810
关键字:

不成功时的平均查找长度